IMO 1999 SL A2

Origin: RUS | Category: Algebra

Problem

The numbers from 1 to n2 are randomly arranged in the cells of a n \times n square (n \geq2). For any pair of numbers situated in the same row or in the same column, the ratio of the greater number to the smaller one is calculated. Let us call the characteristic of the arrangement the smallest of these n2(n−1) fractions. What is the highest possible value of the characteristic?

Solution

Let C(A) denote the characteristic of an arrangement A. We shall prove that max C(A) = n+1 n . Let us prove first C(A) \leqn+1 n for all A. Among elements {n2 −n, n2 − n+1, . . . , n2}, by the pigeonhole principle, in at least one row and at least one column there exist two elements, and hence one pair in the same row or column that is not (n2 −n, n2). Hence C(A) \leqmax . n2 n2 −n + 1, n2 −1 n2 −n ; = n2 −1 n2 −n = n + 1 n . We now consider the following arrangement: aij = . i + n(j −i −1) if i < j, i + n(n −i + j −1) if i \geqj. We claim that C(a) = n+1 n . Indeed, in this arrangement no two numbers in the same row or column differ by less than n −1, and in addition, n2 and n2 −n + 1 are in different rows and columns, and hence C(A) \geqn2 −1 n2 −n = n + 1 n .