Second 4x4 Coloring Problem, Solution

Interestingly, the answer to the extended problem is still in the negative. Now we have

4 3x3-square moves
9 2x2-square moves
4 1-row moves
4 1-column moves
2 4-diagonal moves
4 3-diagonal moves
4 2-diagonal moves
4 1-corner-square moves

with the total of 35 different moves in a 16-dimensional game!

To understand why all this abundance of moves is not sufficient to attain every possible coloring consider the coloring on the right. The region of interest consists of the red squares. For a given coloring, let N_b and N_w be the numbers of black and white squares, respectively, in the red region. Both (N_b mod 2) and (N_w mod 2) can easily be shown to be invariant under any of the legal moves. In other words, N_b will be even after any of the legal moves if and only if it was even before that move. The same is true for N_w. Since for the all-white coloring N_w = 0 (mod 2), it is impossible, starting with this coloring, to obtain any coloring for which N_w = 1 (mod 2).

Martin Gardner discusses the problem (with no 2x2- and 3x3-square moves) in his Puzzles from Other Worlds, #30.

40612321

Supported by