Selection Examinations for the IMO

When $n$ is divisible by $3$, $n = 3k$. The array can be divided into $k^2$ $3 \times 3$ squares. The sum of the numbers inside each square is negative, so the sum of all these sums, which is the sum of all the numbers in the array, is negative as well.

If $n$ is not divisible by $3$, the numbers can be inscribed as required. To make things easier let us assume that all positive numbers in the array are equal and all negative numbers in the array are equal.

The cases $n = 4$ and $n = 5$ are represented in the top two figures. Each $3 \times 3$ square contains eight ones and one $-9$, so the sum is $-1$, while the sum of all the numbers in the array is $8$ and $13$, respectively.

<table>
<tr><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><td>1</td><td>1</td><td>-9</td><td>1</td></tr>
<tr><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><td>1</td><td>1</td><td>1</td><td>1</td></tr>
</table>

<table>
<tr><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><td>1</td><td>1</td><td>-9</td><td>1</td><td>1</td></tr>
<tr><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
</table>

Now, let us choose an arbitrary $k$ and consider the $(3k-1) \times (3k+1)$ array and the $(3k+2) \times (3k+2)$ array. Cover the $3k \times 3k$ array in the upper left corner with $k^2$ $3 \times 3$ squares as shown. For each of these $3 \times 3$ squares put $-b$ into the lower right corner and $a$ into the other eight squares as well as into all the remaining squares in the array.

<table>
<tr><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>-b</td><td>a</td><td>a</td><td>-b</td><td>a</td><td>a</td><td>-b</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>-b</td><td>a</td><td>a</td><td>-b</td><td>a</td><td>a</td><td>-b</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>-b</td><td>a</td><td>a</td><td>-b</td><td>a</td><td>a</td><td>-b</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td></tr>
</table>

The sum inside each $3 \times 3$ square is $8a - b$ and the sum of all numbers in the array is $-k^2 \cdot b + ((3k + 1)^2 - k^2)a$ or $-k^2 \cdot b + ((3k + 2)^2 - k^2)a$. Since $8a - b < 0$, we can write $b = 8a + c$, where $c$ is a positive integer. Then $-k^2 \cdot b + ((3k+2)^2-k^2)a > -k^2 \cdot b + ((3k+1)^2-k^2)a = ((3k+1)^2-9k^2)a-k^2c > 0$ implies
$$\frac{6k+1}{k^2} > \frac{c}{a}.$$
If we set $a = k$ and $c = 1$, we get $b = 8k + 1$.

Hence, for $(3k + 1) \times (3k + 1)$ or $(3k + 2) \times (3k + 2)$ arrays we can arrange the numbers $k$ and $-8k - 1$ as described above. Then the sum of the numbers inside each $3 \times 3$ square is equal to $-1$, while the sum of all the numbers in the array is $5k^2 + k$ or $11k^2 + 4k$, and thus positive.