# 4x4 Coloring Problem, Solution

In a $4\times 4$ chessboard, all squares are colored white or black. Given an initial coloring of the board, we are allowed to recolor it by changing the color of all squares in any $3\times 3$ or $2\times 2$ subboard. Is it possible to get every possible recoloring of the board from the "all-white" coloring by applying some number of these "subboard recolorings"?

### Solution

Coloring of a $4\times 4$ board can be associated with selecting a vector in a $16$-dimensional binary space. As in the Magic Squares game, start with ordering the small squares from left to right and from the top down. Next assign every such square a vector with all components 0 except for the coordinate corresponding to the square according to the ordering. Thus, you'll get

$(1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)$ for the top leftmost square

$(0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)$ the one next to it

and so on,

$(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1)$ will be the last, bottom right square

As in the game, there exist many different bases. Each of them consists of exactly $16$ tuples. Now, let us count the number of $2\times 2$ and $3\times 3$ regions. Obviously, there are four $3\times 3$ regions and nine $2\times 2$ regions. In all, there are $13$ of them. $13$ is not enough to form a basis in a $16$-dimensional space. Therefore, there bound to exist colorings that could not be obtained as described in the Problem. Can you find one such coloring?

### Follow up

In the previous problem, where the number of legal moves was limited to $13,$ it was easy to show that the problem of getting an arbitrary coloring does not, in general, have a solution. Now, let us enlarge the set of allowable moves. Let us agree that a player, in addition to the moves already defined, can simultaneously reverse the colors of

- a single row, or
- a single column, or
- any $2$-,$3$-, or $4$-square diagonal
- any corner square

Is it now possible, starting with all white squares, to obtain an arbitrary coloring?

Solution

|Merlin Magic Square| |Front page| |Up|

Copyright © 1996-2018 Alexander Bogomolny

72012678