Given a board consists of $n \times n$ unit squares ($n \ge 3$). Each unit square is colored black and white, resembling a chessboard. In each step, TOMI can choose any $2 \times 2$ square and change the color of every unit square chosen with the other color (white becomes black and black becomes white). Find every $n$ such that after a finite number of moves, every unit square on the board has a same color.
Problem
Source: 2011 Indonesia TST stage 2 test 3 p3
Tags: combinatorics, Coloring
17.12.2020 22:49
Solved with one other (who does not have an AoPS account). The answer is $\boxed{n = 4k, \forall k \in \mathbb{Z}^+}$. Let the chessboard operate in $\mathbb{F}_2$, with the squares alternatively labeled $0$ and $1$. Thus, the step given corresponds to adding $1$ to each unit square in the selected $2 \times 2$ square (or a bitwise XOR operation). Let $A$ be the set of columns on a given board. Consider the sum of the numbers in an arbitrary $a \in A$ to be $S(a)$. We use the following claims. Claim 1. There does not exist a step that can change $S(a)$ for an arbitrary $a \in A$. Proof. The given step adds $1$ to each of two unit squares in a column that the move affects. However, $S(a) + 1 + 1 = S(a)$ because the chessboard operates in $\mathbb{F}_2$, so it is impossible to change the sum of the numbers in a column under the given conditions. $\square$ Claim 2. In order for all squares to be labeled with the same number, $S(a) = S(b)$ must be true for all choices of $a, b \in A$. Proof. This is obvious, because if every column is identical, their sums will also be identical. $\square$ Claim 3. If $n$ is even, in order for all of the unit squares to be labeled the same number, $S(a) = 0$ must be true for all $a \in A$. Proof. If $n$ is even, there are an even number of numbers in each column. Thus, for any $a \in A$, it must be true that $S(a) = 0$ if all squares have the same number (note that this is true in both cases; where all the squares are labeled with $0$ or all the squares are labeled with $1$). $\square$ Assume that $n$ is odd. By (1), if $b \in A$ is adjacent to any $a \in A$, $S(a) = S(b) + 1$ always holds after any number and choice of steps. However, this contradicts (2), so $n$ must be even. Assume that $n \equiv 2 \pmod 4$. Then, $S(a) = 1$ for any $a \in A$. However, due to (1), this contradicts (3). So it is only possible that $n \equiv 0 \pmod 4$. It now suffices to provide a construction for $n=4$, as any chessboard with $n=4k$ for all $k \in \mathbb{Z}, k \geq 2$ can be subdivided into $4 \times 4$ squares with the same orientation. The moves are shown two at a time by the bolded $2 \times 2$ sets of numbers. $$ \begin{array}{ |c|c|c|c| } \hline \mathbf{0} & \mathbf{1} & \color[rgb]{0.5, 0.5, 0.5} 0 & \color[rgb]{0.5, 0.5, 0.5} 1 \\ \hline \mathbf{1} & \mathbf{0} & \color[rgb]{0.5, 0.5, 0.5} 1 & \color[rgb]{0.5, 0.5, 0.5} 0 \\ \hline \color[rgb]{0.5, 0.5, 0.5} 0 & \color[rgb]{0.5, 0.5, 0.5} 1 & \mathbf{0} & \mathbf{1} \\ \hline \color[rgb]{0.5, 0.5, 0.5} 1 & \color[rgb]{0.5, 0.5, 0.5} 0 & \mathbf{1} & \mathbf{0} \\ \hline \end{array} \rightarrow \begin{array}{ |c|c|c|c| } \hline \color[rgb]{0.5, 0.5, 0.5} 1 & \color[rgb]{0.5, 0.5, 0.5} 0 & \color[rgb]{0.5, 0.5, 0.5} 0 & \color[rgb]{0.5, 0.5, 0.5} 1 \\ \hline \mathbf{0} & \mathbf{1} & \mathbf{1} & \mathbf{0} \\ \hline \mathbf{0} & \mathbf{1} & \mathbf{1} & \mathbf{0} \\ \hline \color[rgb]{0.5, 0.5, 0.5} 1 & \color[rgb]{0.5, 0.5, 0.5} 0 & \color[rgb]{0.5, 0.5, 0.5} 0 & \color[rgb]{0.5, 0.5, 0.5} 1 \\ \hline \end{array} \rightarrow \begin{array}{ |c|c|c|c| } \hline \color[rgb]{0.5, 0.5, 0.5} 1 & \mathbf{0} & \mathbf{0} & \color[rgb]{0.5, 0.5, 0.5} 1 \\ \hline \color[rgb]{0.5, 0.5, 0.5} 1 & \mathbf{0} & \mathbf{0} & \color[rgb]{0.5, 0.5, 0.5} 1 \\ \hline \color[rgb]{0.5, 0.5, 0.5} 1 & \mathbf{0} & \mathbf{0} & \color[rgb]{0.5, 0.5, 0.5} 1 \\ \hline \color[rgb]{0.5, 0.5, 0.5} 1 & \mathbf{0} & \mathbf{0} & \color[rgb]{0.5, 0.5, 0.5} 1 \\ \hline \end{array} \rightarrow \begin{array}{ |c|c|c|c| } \hline 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 1 & 1 \\ \hline \end{array} $$Thus, $n=4k$ works for all $k \in \mathbb{Z}^+$. $\blacksquare$