40th IMO 1999 shortlist Problem A2 The numbers 1 to n 2 are arranged in the squares of an n x n board (1 per square). There are n 2 (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 2 and n 2 - 1 were in the same row, then the minrat would be n 2 /(n 2 - 1). What is the largest possible minrat? Solution
: (n+1)/n. The subset {n 2 , n 2 - 1, ... , n 2 - (n-1) } has n members. If any two lie in the same row or column, then their ratio is at most n 2 /(n 2 - n + 1)  (n+1)/n. The numbers if the first column are a decreasing arithmetic progression, so the smallest ratio between the first two terms: (n 2 - n + 1)/(n 2 - 2n + 2) ≥ (n+1)/n. The numbers in the nth column are n 2 and an arithmetic progression n-1, 2(n-1), ... , (n-1) 2 , 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 2 -n+j)/(n 2 -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 © John Scholes jscholes@kalva.demon.co.uk 10 Oct 2002