
Problem I-2. Let $n$ be a positive integer. On a board consisting of $4 n \times 4 n$ squares, exactly $4 n$ tokens are placed so that each row and each column contains one token. In a step, a token is moved horizontally or vertically to a neighbouring square. Several tokens may occupy the same square at the same time. The tokens are to be moved to occupy all the squares of one of the two diagonals.

Determine the smallest number $k(n)$ such that for any initial situation, we can do it in at most $k(n)$ steps.


Solution. We shall prove that $k(n)=6 n^{2}$.

We define the distance from a given square to a given diagonal to be the minimal number of steps needed to get from the square to the diagonal. This equals the minimal number of horizontal steps needed to do that. It also equals the minimal number of vertical steps needed to do that.

Given a configuration of tokens, we define the distance from this configuration to a given diagonal to be the sum of distances of the tokens to that diagonal.

Choose the coordinate system so that the vertices of the board have coordinates $\pm 2 n$. Place a token on each of the $n$ squares the coordinates of whose centres satisfy $x>0$ and $y-x=n$. Now complete this configuration of tokens so that it has a rotational symmetry of $90^{\circ}$ about the origin. Then we have $4 n$ tokens, one in each row, one in each column. The distance from this configuration to either diagonal is $2 n \cdot n+2 n \cdot 2 n=6 n^{2}$. Therefore, $k(n) \geq 6 n^{2}$.

Now consider any configuration satisfying the conditions of the problem. We prove that $\leq 6 n^{2}$ steps suffice even if we only allow horizontal moves. I.e., the smallest of the
two distances from the given configuration to the diagonals is $\leq 6 n^{2}$. It suffices to prove that the sum of the two distances from the given configuration to the diagonals is $\leq 12 n^{2}$.

Observe that the sum of the two distances from the square with center $(x, y)$ to the two diagonals is $2 \max (|x|,|y|)$. This number can take values $1,3, \ldots, 4 n-1$. The squares where it takes a given value can be covered by two columns and two rows, so we can place at most four tokens there. Thus, the sum of the values for the $4 n$ tokens is $\leq 4((4 n-1)+(4 n-3)+\cdots+(2 n+1))=4 n \cdot 3 n=12 n^{2}$.
