Problem 2053

It is clear that whether the number inserted at every turn matters for the point(s) earned or not depends only on the remainder obtained when that number is divided by $n$. Therefore, we may assume that every integer $k$ satisfying $0 \le k \le n - 1$ will be inserted into squares exactly $n$ times.

Let us show that the value we seek as the answer to the problem is $n(n+1)$. We first exhibit a method of inserting numbers for which the total number of points earned at the end of the game is exactly $n(n+1)$. This method tells us to insert into the square located at the $i$-th row from the top and $j$-th column from the left the number obtained as the remainder when $i+j$ is divided by $n$. If $0$ is inserted $n$ times, $1$ is inserted $n$ times, $n-1$ is inserted $n$ times, $2$ is inserted $n$ times, $n-2$ is inserted $n$ times, ..., then, whenever $0, n-1, n-2, \dots, \frac{n+1}{2}$ are inserted, $2$ points are earned so that the total of $n(n+1)$ points will be earned at the end.

Next, let us show that the total number of points earned by the end of the game can be at most $n(n+1)$. Let $A_0 = B_0 = 0$. For any $i$ satisfying $1 \le i \le n^2$, let $A_i = A_{i-1} + 1$ if the sum of the numbers written into the squares lying on the same row of the grid as the square into which a number is inserted at the $i$-th turn (which is included in the sum) is a multiple of $n$, and $A_i = A_{i-1}$ otherwise. We define $B_i$'s for columns in the same way. Then, the total sum of the points earned at the end of the game is given by $A_{n^2} + B_{n^2}$.

Let us consider the maximum value that $A_{n^2}$ can take. For every $i$ satisfying $0 \le i \le n^2$, let us denote by $C_i$ the number of columns for which the column-sum of the numbers inserted into the squares is not a multiple of $n$ right after the end of $i$-th turn. We also let $C_0 = 0$. Then, we see that $A_i + \frac{1}{2}C_i$ increases, in comparison with $A_{i-1} + \frac{1}{2}C_{i-1}$ at most by $1$ if $0$ is the number inserted at the $i$-th turn, and at most by $\frac{1}{2}$ otherwise. Since $0$ is inserted $n$ times and non-zero $n$ is inserted $n^2 - n = n(n - 1)$ times, we see that
$$A_{n^2} + \frac{1}{2}C_{n^2} \le n + \frac{n(n-1)}{2} = \frac{n(n+1)}{2}$$
must hold. Since $C_{n^2}$ is a non-negative integer, we conclude that $A_{n^2} \le \frac{n(n+1)}{2}$ must be satisfied. By the same argument we obtain $B_{n^2} \le \frac{n(n+1)}{2}$. Therefore, the maximum of the total points we obtain at the end of the game is $n(n+1)$.