40th IMO shortlist 1999/A2 solution

40th IMO 1999 shortlist

Problem A2

The numbers 1 to n² are arranged in the squares of an n x n board (1 per square). There are n² (n-1) pairs of numbers in the same row or column. For each such pair take the larger number divided by the smaller. Then take the smallest such ratio and call it the minrat of the arrangement. So, for example, if n² and n² - 1 were in the same row, then the minrat would be n²/(n² - 1). What is the largest possible minrat?

Solution

Answer: (n+1)/n.

The subset {n², n² - 1, ... , n² - (n-1) } has n members. If any two lie in the same row or column, then their ratio is at most n²/(n² - n + 1) < (n+1)/n. So the minrat < (n+1)/n. If they all lie in different rows and columns then the number n² - n must lie in the same row as one of them and the same column as another, so that gives a ratio at most (n² - 1)/(n² - n) = (n+1)/n. So in any case the minrat must be ≤ (n+1)/n.

We now have to show that this value can be achieved. Take the number at (i, j) to be a_ij = i + n(j - i - 1) for i < j, and i + n(n - i + j - 1) for i ≥ j. For example,

21   1   6  11  16
17  22   2   7  12
13  18  23   3   8
 9  14  19  24   4
 5  10  15  20  25

The numbers in the same row differ by multiples of n, so their ratio is at least n²/(n² - n) > (n+1)/n. The numbers if the first column are a decreasing arithmetic progression, so the smallest ratio between the first two terms: (n² - n + 1)/(n² - 2n + 2) ≥ (n+1)/n. The numbers in the nth column are n² and an arithmetic progression n-1, 2(n-1), ... , (n-1)², so the smallest ratio is (n-1)/(n-2) > (n+1)/n. For the other columns the numbers form two arithmetic progressions, each with difference n-1 and the smallest ratio is (n²-n+j)/(n²-2n+j+1) ≥ (n+1)/n (the ratio of the number on the diagonal and the number just below it), with equality if j = n-1.

40th IMO shortlist 1999