Maths Olympiad Prep

Library / /48 of 54

Combinatorics Difficulty 7.2 National olympiad, round 2 Prove it China

Given an n×nn \times n grid, we call two cells in it adjacent if they have a common side. At the beginning, each cell is assigned number +1+1. An operation on the grid is defined as follows: one chooses a cell, and then changes the signs of every number in its adjacent cells (but does not change the sign of the number in itself). Find all the integers n2n \ge 2, such that after a finite number of operations, all the numbers in the cells of the grid are changed to 1-1. (posed by Shen Huyue)

Solution

We denote the cell in the ii-row and jj-column of the grid as AijA_{ij} (i,j{1,2,,n}i, j \in \{1, 2, \dots, n\}).

When n=2kn = 2k, kNk \in \mathbb{N}^*, we mark each AijA_{ij} satisfying i+j0(mod2)i + j \equiv 0 \pmod{2} with color red (presented by shaded areas), and that satisfying ji3(mod4)j - i \equiv 3 \pmod{4} and ji≢j+i(mod4)j - i \not\equiv j + i \pmod{4} with blue (presented by oblique line areas) (see Fig. 7.1).

Figure 1
Fig. 7.1
Figure 2
Fig. 7.2

In this way, we can see that every cell adjacent to a blue one is red, and there is exactly one blue cell around each red one.

Now we do the operation on each blue cell. The number in each red cell is then changed from +1+1 to 1-1, while the numbers in the remaining cells are unchanged.

Since nn is an even number, we can rotate the grid around its center OO anticlockwise by 9090^\circ. Then all the red cells of the rotated grid cover exactly all the cells that are not red in the original grid (see Fig. 7.2).

We do the operations again for the original grid on all the cells that are covered by blue cells of the rotated grid. Then we see that all the numbers with value +1+1 in the remaining cells of the original grid are changed to 1-1, while the numbers in the other cells are unchanged.

Therefore, when nn is an even number, all the numbers in the cells of the grid can be changed to 1-1 by a finite number of operations.

When nn is odd, we denote the number in cell AiiA_{ii} as MiM_i (i=1,2,,ni = 1, 2, \dots, n), and denote the number of operations on each of their adjacent cells as x1,x2,,xn1,y1,y2,,yn1x_1, x_2, \dots, x_{n-1}, y_1, y_2, \dots, y_{n-1}, respectively (see Fig. 7.3).

After finite operations, it is easy to see that:

Figure 3
Fig. 7.3

M1M_1 is changed from +1+1 to 1-1 if and only if x1+y1x_1 + y_1 is odd;

M2M_2 is changed from +1+1 to 1-1 if and only if x1+y1+x2+y2x_1 + y_1 + x_2 + y_2 is odd;

M3M_3 is changed from +1+1 to 1-1 if and only if x2+y2+x3+y3x_2 + y_2 + x_3 + y_3 is odd;

\vdots

Mn1M_{n-1} is changed from +1+1 to 1-1 if and only if xn2+yn2+xn1+yn1x_{n-2} + y_{n-2} + x_{n-1} + y_{n-1} is odd, and

MnM_n is changed from +1+1 to 1-1 if and only if xn1+yn1x_{n-1} + y_{n-1} is odd.

Since nn is odd, the sum of nn odd numbers is still odd. Then,

(x1+y1)+(x1+y1+x2+y2)+(x2+y2+x3+y3)++(xn2+yn2+xn1+yn1)+(xn1+yn1)=2(x1+x2++xn1+y1+y2++yn1) \begin{align*} & (x_1 + y_1) + (x_1 + y_1 + x_2 + y_2) + (x_2 + y_2 + x_3 + y_3) \\ & \quad + \dots + (x_{n-2} + y_{n-2} + x_{n-1} + y_{n-1}) + (x_{n-1} + y_{n-1}) \\ & = 2(x_1 + x_2 + \dots + x_{n-1} + y_1 + y_2 + \dots + y_{n-1}) \end{align*}

is odd. It is impossible!

Therefore, all the numbers in the cells of a given n×nn \times n grid can be changed from +1+1 to 1-1 after a finite number of operations if and only if nn is an even number. \boxed{}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.