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

73366915