16. A2 (RUS) The numbers from 1 to $n^{2}$ are randomly arranged in the cells of a $n \times n$ square $(n \geq 2)$. 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 $n^{2}(n-1)$ fractions. What is the highest possible value of the characteristic?
16. Let $C(A)$ denote the characteristic of an arrangement $A$. We shall prove that $\max C(A)=\frac{n+1}{n}$.
Let us prove first $C(A) \leq \frac{n+1}{n}$ for all $A$. Among elements $\left\{n^{2}-n, n^{2}-\right.$ $\left.n+1, \ldots, n^{2}\right\}$, 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 $\left(n^{2}-n, n^{2}\right)$. Hence
$$
C(A) \leq \max \left\{\frac{n^{2}}{n^{2}-n+1}, \frac{n^{2}-1}{n^{2}-n}\right\}=\frac{n^{2}-1}{n^{2}-n}=\frac{n+1}{n} .
$$

We now consider the following arrangement:
$$
a_{i j}=\left\{\begin{array}{ll}
i+n(j-i-1) & \text { if } i<j \\
i+n(n-i+j-1) & \text { if } i \geq j .
\end{array}\right.
$$

We claim that $C(a)=\frac{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, $n^{2}$ and $n^{2}-n+1$ are in different rows and columns, and hence
$$
C(A) \geq \frac{n^{2}-1}{n^{2}-n}=\frac{n+1}{n} .
$$