KBB3 Problem 4

Given a 3x3 chessboard where each cell is colored black or white. At any step, we are allowed to pick any column or any row and flip all the cell colors in that column or row. Prove or disprove: no matter what the initial coloring is, we can always get an all-white board?

Answer: no

First Solution

Each step is reversible. In fact, each step is its own reverse, so we can reach all-white from a configuration if and only if we can reach that configuration from an all-white board.

There are $2^9$ possible colorings of the square. We shall prove that there are at most $2^6$ configurations from an all-white board.

There are 6 elementary steps, say $A_1, \cdots, A_6$. Each of these steps are commutative. So we can write a sequence of steps as $A_1^{a_1} A_2^{a_2} \cdots A_6^{a_6}$. Furthermore, $A_i^2$ is the identity step, so each $a_i$ can be replaced by either 0 or 1, depending on whether it was odd or even. Now, the number of reachable configurations is the number of different arrangements we can give to $a_i$s, and that is $2^6$, which completes our proof.

Remark: the number of reachable configurations is in fact less than $2^6$ because some distinct arrangements might still arrive at the same configuration.

Second Solution

Let $S$ be the number of black squares in the four corner cells. Then $S$ always changes by an even number. If we start with a configuration where $S$ is odd, we will never reach an all-white configuration where $S$ is even.

Remark: this beautiful solution is due to Johan Gunardi, the winner of KBB3.