Maths Olympiad Prep

Library / /4 of 4

Combinatorics Difficulty 8.9 Shortlist Prove it Hong Kong

Let nn be a positive integer. In each cell of an n×nn \times n grid, we place a coin with either the head or the tail facing upwards. Each time we can select one cell, and flip all the 2n12^n - 1 coins that lie in the same row or the same column as this cell. Find all nn such that it is always possible to have all the coins with the heads facing upwards after finitely many moves, no matter how we place the coins initially.

Solution

Answer: 1 and all positive even numbers.

In the following, to operate on the (i,j)(i, j)th cell (the cell in the iith row and the jjth column) means to perform an operation by selecting the (i,j)(i, j)th cell in the operation.

* When n=1n = 1, it is clear that the goal can always be met.

* When nn is even, it suffices to show that it is possible to flip any arbitrary coin only in some moves. Indeed, if we want to flip the coin in the (i,j)(i, j)th cell (called CC), we simply operate on every cell that lies in the same row or the same column as CC.

- The coin in CC is flipped 2n12n - 1 times, which is odd.
- Each coin in the same row or the same column as CC other than the coin in CC is flipped nn times, which is even.
- Every other coin is flipped 22 times, which is even.

Therefore, we see that only the coin in CC is flipped after these operations.

* When nn is odd and greater than 11, it suffices to consider the reverse process, i.e. starting with all coins with the heads facing upwards, we cannot obtain all possible configurations after finitely many moves. Note that there are 2n22^{n^2} possible configurations since there are two possibilities for each of the n2n^2 cells. On the other hand, note that the order of operations does not affect the result, and operating the same cell twice does not change the result. Therefore, we may assume each cell is operated 00 or 11 time. This leads to 2n22^{n^2} different sets of operations. Thus, it suffices to show that there are two different sets of operations that lead to the same configuration.

Indeed, we simply operate on every cell in the first row and the first column except the (1,1)(1, 1)th cell.
- The coin in the (1,1)(1, 1)th cell is flipped 2(n1)2(n-1) times, which is even.
- Each coin in the first row or the first column other than the coin in the (1,1)(1, 1)th cell is flipped n1n-1 times, which is even.
- Every other coin is flipped 22 times, which is even.

Therefore, we see that no coin is flipped after these operations, which means this has the same effect as not performing any operation at all (which is also one of the 2n22^{n^2} sets of operations). This completes the proof.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.