Squares of an $n \times n$ table ($n \ge 3$) are painted black and white as in a chessboard. A move allows one to choose any $2 \times 2$ square and change all of its squares to the opposite color. Find all such n that there is a finite number of the moves described after which all squares are the same color.
Problem
Source: MOP 2005 Homework - Black Group #10
Tags: induction, geometry, rectangle, combinatorics unsolved, combinatorics
23.05.2014 22:47
Claim: If $4|n$, then we can turn all cells of the grid into the same color. Proof: It is sufficient to show that we can do this when $n=4$, since we can divide larger squares into non-overlapping $4$ by $4$ squares.
Now we show that we cannot do this for all other $n$. We prove using induction that if $n$ is not divisible by 4, then we cannot turn all the cells of the first two rows into one color. Some observations: Each rectangle should be changed 0 times or 1 time. (Changing a rectangle twice is equivalent to no change.) The order of the operations does not matter. Case 1: $n\equiv 1\mod 4$. Base case is trivial. Without loss of generality, let the cell in the top-right corner start as black. Note that the parities of the number of black cells and the number of white cells do not change after each operation. Since there are an even number of white cells, we must turn the whole grid black. We claim that if we turn the top row black (and only do operations on the top row), then the next row will be completely white. Assume that the claim holds for $n-4$. To turn the top row black, we must change the bolded rectangle: BWBW... WBWB... Then we must change the next bolded rectangle: BBWW... WWBB... Thus we obtain: BBBB... WWWW... And by induction, the claim is true. Since the second row has an odd number of white cells, we cannot turn all of them black. Thus we cannot finish when $n\equiv1\mod4$. The other cases follow similarly, by reducing the case of $n$ to the case of $n-4$, yielding our desired result.