Let be a positive integer. In each cell of an 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 coins that lie in the same row or the same column as this cell. Find all 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 th cell (the cell in the th row and the th column) means to perform an operation by selecting the th cell in the operation.
* When , it is clear that the goal can always be met.
* When 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 th cell (called ), we simply operate on every cell that lies in the same row or the same column as .
- The coin in is flipped times, which is odd.
- Each coin in the same row or the same column as other than the coin in is flipped times, which is even.
- Every other coin is flipped times, which is even.
Therefore, we see that only the coin in is flipped after these operations.
* When is odd and greater than , 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 possible configurations since there are two possibilities for each of the 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 or time. This leads to 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 th cell.
- The coin in the th cell is flipped times, which is even.
- Each coin in the first row or the first column other than the coin in the th cell is flipped times, which is even.
- Every other coin is flipped 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 sets of operations). This completes the proof.