Coloring of a 4x4 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 2x2 and 3x3 regions. Obviously, there are 4 3x3 regions and 9 2x2 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?

Copyright © 1996-2009 Alexander Bogomolny