2
$\begingroup$

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"?

$\endgroup$
  • 3
    $\begingroup$ Wlecome to MathSE! What are your thoughts on the question and what did you try so far? $\endgroup$ – user409521 Mar 18 '17 at 18:33
  • 3
    $\begingroup$ A broad hint: what is the dimension of the 'space' of colorings? How many different subboard-recolorings do you have available? $\endgroup$ – Steven Stadnicki Mar 18 '17 at 18:41
  • $\begingroup$ It is considered bad form to change a question when there is already a valid answer. If you want to know about the $5\times5$ case, please ask a new question. (It would be appropriate to link to this question there, to help supply some context.) $\endgroup$ – Barry Cipra Apr 2 '17 at 14:27
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Here's a paraphrase of this excellent solution: There are $2^{16}$ colorings. Flipping the colors of a sub-board can be done in $13$ ways. Flipping the same sub-board twice is like not flipping it at all. Hence there are at most $2^{13}$ different colorings reachable from any initial coloring. $\endgroup$ – Fabio Somenzi Mar 18 '17 at 20:26
  • 1
    $\begingroup$ Yeah. I suppose you are implicitly using the fact that two legal moves always commute. $\endgroup$ – Nick R Mar 19 '17 at 1:05
  • 1
    $\begingroup$ Yes, these are exclusive OR operations and they are associative and commutative. $\endgroup$ – Fabio Somenzi Mar 19 '17 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.