# Second 4x4 Coloring Problem, Solution

We are concerned with the problem of getting on black-white pattern from another on a $4\times 4$ board by certain moves related to the Merlin Magic Squares game. The game lives in the $16$-dimensional boolean space. The previous variant of the problem had only $13$ moves and, for this reason, there were patterns not obtainable from other patterns. To complicate matters, we intoduced additional moves. Here's the whole list:

• four $3\times 3$-square moves
• nine $2\times 2$-square moves
• four $1$-row moves
• four $1$-column moves
• two $4$-diagonal moves
• four $3$-diagonal moves
• four $2$-diagonal moves
• four $1$-corner-square moves

with the total of $35$ different moves in a $16$-dimensional game! Interestingly, the answer to the extended problem is still in the negative. Now we have

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.$

The argument can be framed as suggesting a counterexample: i.e., an example of a board that could not be obtained by the stipulated moves from, say, the above one. Here's one such example

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