$4\times 4$ Chessboard Colorings

230 Views Asked by At

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×3$ or $2×2$ sub-board.

Is it possible to get every possible recoloring of the board from the "all-white" coloring by applying some number of these "sub-board re-colorings"?

1

There are 1 best solutions below

3
On

One can view this problem as choosing a vector in $\mathbb{F}_2^{16}$ where each coordinate corresponds to a square on your board. The coordinate equaling 0 corresponds to white and 1 corresponds to black. Then your legal moves can be viewed as vectors $v_i \in \mathbb{F}_2^{16}$ in the vector space.

The question of whether all coloring can be obtained by your moves is equivalent to asking whether their exist scalars $a_i = 0, 1$ such that you can reach every possible vector (gamestate) by the following: $$\sum a_i v_i$$

In linear algebra this is equivalent to asking whether the $v_i$ span our vector space. There are 4 legal moves for flipping $3 \times 3$ subboards and 9 legal moves for $2 \times 2$. Thus in total we have 13 legal moves. We know that the span of 13 vectors is at most 13 dimensional, and hence cannot be the full gamestate space.

Note this method only generically shows obstructions. If we have a $5 \times 5$ Chessboard and allow all $4 \times 4$ and $3 \times 3$ boards to be flipped, then we have 25 legal moves and a 25 dimensional state space. One would need to argue differently to handle this case.