Estonian Mathematical Olympiad

The least and the largest among the sums of two natural numbers from $1$ through $k$ are $1+1=2$ and $k+k=2k$, respectively. Thus there can be at most $2k-1$ distinct sums. The number of distinct pairs of cells with a common side is $n-1$ in every row and column. As the total number of rows and columns is $2n$, the number of such pairs is $2n(n-1)=2n^2-2n$. Hence $2k-1\ge 2n^2-2n$ which implies $$k\ge \frac{2n^2-2n+1}{2}=n^2-n+\frac{1}{2}.$$ As $k$ is an integer, we have $k\ge n^2-n+1$.

Now we show that $k=n^2-n+1$ is achievable. To this end, partition the $n\times n$ table into $2n-1$ diagonals (directed from top right to bottom left; see Fig. 37). We fill the diagonals starting from the top left corner with consecutive integers $1,2,\dots$, but whenever switching from a diagonal with an odd number to the next diagonal with an even number, we repeat the number just written. This repetition happens $n-1$ times. Hence the last

Fig. 37 Fig. 38 number written into the bottom right cell is $n^2-n+1$ as desired. Figure 38 depicts the situation for $n=4,k=13$. We show that the sum of every two cells with a common side is unique. Each sum under consideration is obtained by adding numbers in cells of two consecutive diagonals. All sums of cells of the same two diagonals are obviously distinct, because when moving from the top right end to the bottom left end, the sum strictly increases at every step. When considering distinct pairs of consecutive diagonals, the sums must also be distinct. Indeed, let one pair under consideration contain diagonals No $a$ and $a+1$ and let the other pair contain diagonals No $b$ and $b+1$, where $a<b$. Then numbers in the first diagonal of the first pair do not exceed numbers in the first diagonal of the second pair, whereas numbers in the second diagonal of the first pair do not exceed numbers in the second diagonal of the second pair. In either case, equality can hold only if $b=a+1$. But the equality cannot hold for both cases simultaneously, because $a$ and $a+1$ have distinct parities, implying that, by construction, when switching either from the diagonal No $a$ to the diagonal No $a+1$ or from the diagonal No $b$ to the diagonal No $b+1$, the last number is not repeated.