Problem 63. 0-1 Table
We have a \(5 \times 5\) table which is initially filled with 0s. Each time, we can choose either a \(2 \times 2\) or a \(3 \times 3\) subtable and toggle all of its numbers (replace 0 by 1 and replace 1 by 0). Can we generate all \(2^{25}\) different tables with a sequence of such moves? If we can, how? otherwise, why?
The answer is negative.
Assume that we color the first and fourth rows of the table in gray as shown below:
Notice that any \(2 \times 2\) or \(3 \times 3\) subtable contains an even number of white cells. Therefore, each move will toggle an even number of white cells, and the parity of the sum of the numbers of white squares will always remain even. Thus we can never turn the table into a configuration in which the number of 1s in the white cells is odd.