Problem
COM-B2-M05-P018 A Criterion for \(2\times2\) Blocks
On an \(m\times n\) board, where \(m,n\ge2\), all cells are white. In one move, choose a contiguous \(2\times2\) block and change the colours of all four of its cells. Prove that a colouring is reachable if and only if every row and every column contains an even number of black cells.
Necessity follows from row and column parity. For sufficiency, fix cells from left to right and top to bottom.
Necessity: one move changes two cells in each of two neighbouring rows and two cells in each of two neighbouring columns. Therefore the parity of the number of black cells in every row and every column is preserved. Initially all these parities are \(0\).
For sufficiency, let the target colouring have even rows and columns. We construct it from the white board. For \(i=1,\ldots,m-1\) and \(j=1,\ldots,n-1\), scan cells from left to right and top to bottom. If the current cell \((i,j)\) differs from the target, apply the move to the \(2\times2\) block with top-left corner \((i,j)\). After that, cell \((i,j)\) matches the target, and later moves will not affect it, because they start no higher and no further left.
After this procedure, all cells outside the last row and last column match the target. It remains to check the last row and last column. In every row and column, the current board has even black parity, and so does the target board. Therefore in each almost completed row, the last cell is forced to match the target. Similarly, the cells of the last row match. Hence the whole colouring is reachable.
The difficulty is that one needs not only an invariant, but also a construction algorithm.