This question already has an answer here:

64 coins are placed on a chessboard; coins on black squares are heads up, coins on white squares are tails up. In each step, you are allowed to choose three consecutive coins in the same row or column, and flip these three coins. Is it possible to get all heads up?

I managed to end up with one tail and 63 heads. I kind of believe that the answer is negative, but didn't manage to find an easy invariant.


marked as duplicate by Gerry Myerson, Amzoti, mrf, Micah, Asaf Karagila Mar 7 '13 at 6:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I'm sure this question was asked and answered here very recently, but I can't find it. EDIT: found it! 313499 $\endgroup$ – Gerry Myerson Mar 7 '13 at 5:11

The idea behind this, as OP suggested, is to find an invariant. What this means, is that you need to find a way to express the sum on the board, and show that any step you take doesn't change the sum.
Sometimes (like in this case), the invariant that you chose doesn't work, as the steps keep on changing the sum. If so, look at how the steps change the sum, and use a further argument like parity (which is generalized by modulo arithmetic).
The hard part of the question tends to be figuring out what invariant to use, or why that would likely work.

Hint: Since your moves are only 3 consecutive coins in a row or column, a good thing to use is the cube root of unity, since $\omega^2 + \omega + 1 = 0$.

Hint: Define the sum of the board to be $\sum f_{(a, b)} \omega^{a + b }$, where $f_{(a, b)} = 1 $ if the coin shows a head, -1 if the coin shows a tail. This is going to be our invariant as mentioned above. The motivation for it is from the previous hint, and we need to understand how this invariant changes.

Hint: How does this sum change when you do any move? (This is the key observation that you must make.)

Elaboration: For a coin on square $(a, b)$, we simply care about the value of $a+b \pmod{3}$. For each flip (of 3 consecutive coins), the coins are in distinct residue classes.

If we flip coins which are (head, head, head) in residue classes 0, 1, 2, they are now (tail, tail, tail), and the difference in the sum is $+1 + \omega + \omega^2 = 0$ to $-1 - \omega - \omega^2 = 0$, so nothing changes.

If the coins were (head, head, tail) in residue classes 0, 1, 2, then they are now (tail, tail, head). The sum of the board changes from $+1 + \omega - \omega^2 = -2 \omega^2 $ to $-1 -\omega + \omega^2 = 2 \omega^2$. This sum changes by $+4 \omega^2$, so we don't have an exact invariant, but hopefully we are lucky and can use a further parity argument.

Look at the other 6 cases (some of which are reflections). Check how the sum changes. I claim that the sum changes by $ \pm 4, \pm 4\omega, \pm 4\omega^2, 0$.

Hint: Let (1, 1) be a black square. In the original configuration, the sum of the board is $ - 3$. You can check this by looking a corner 2 by 2 square since any 6 consecutive squares cancel out. We get $\omega^2 - 2 + \omega = -3$.

Hint: If we get all heads, then the sum of the board is $+3$. You can check this by looking at a corner 2 by 2 square, since any 3 consecutive squares cancel out. We get $ \omega^2 + 1 +1 + \omega = +3$.

Now, convince yourself there there is no way to get from $- 3$ to $+3$, if we can change the values only by $ \pm 4, \pm 4\omega, \pm 4\omega^2, 0$ each time. This should be obvious.

  • $\begingroup$ Will be good if you post the full answer for the ppl who are not very familiar with combinatorics for these kind of puzzle. $\endgroup$ – Learner Mar 7 '13 at 4:18
  • $\begingroup$ Thanks! I think we can translate it in terms of coloring: color the board in red, blue, white (in the obvious way). Then in each step, count the number of heads in red, blue, and white squares, modulo 2. $\endgroup$ – name Mar 7 '13 at 4:26
  • $\begingroup$ @name That is similar, but I'm not sure if it will work out nicely. I've included a bunch more details now. Modulo 2 doesn't work for what I'm doing, but modulo 4 does :) It's a nice problem. $\endgroup$ – Calvin Lin Mar 7 '13 at 4:29
  • $\begingroup$ It looks like you mean $f_{(a,b)} = 1$ for heads, $-1$ for tails. $\endgroup$ – Jair Taylor Mar 7 '13 at 4:32
  • $\begingroup$ @JairTaylor yes I do. Thanks. $\endgroup$ – Calvin Lin Mar 7 '13 at 4:36

This is essentially just a more elementary version of Calvin Lim’s argument. Color the board by diagonals in three colors as shown below:

$$\begin{array}{|c|c|} \hline 2&\color{red}{0}&1&\color{red}{2}&0&\color{red}{1}&2&\color{red}{0}\\ \hline \color{red}{0}&1&\color{red}{2}&0&\color{red}{1}&2&\color{red}{0}&1\\ \hline 1&\color{red}{2}&0&\color{red}{1}&2&\color{red}{0}&1&\color{red}{2}\\ \hline \color{red}{2}&0&\color{red}{1}&2&\color{red}{0}&1&\color{red}{2}&0\\ \hline 0&\color{red}{1}&2&\color{red}{0}&1&\color{red}{2}&0&\color{red}{1}\\ \hline \color{red}{1}&2&\color{red}{0}&1&\color{red}{2}&0&\color{red}{1}&2\\ \hline 2&\color{red}{0}&1&\color{red}{2}&0&\color{red}{1}&2&\color{red}{0}\\ \hline \color{red}{0}&1&\color{red}{2}&0&\color{red}{1}&2&\color{red}{0}&1\\ \hline \end{array}$$

The red numbers mark the squares initially occupied by coins showing heads; $12$ of the heads are on color $0$, $10$ are on color $1$, and $10$ are on color $2$. Of the $32$ coins showing tails, $10$ are on color $0$, $11$ are on color $1$, and $11$ are on color $2$. Thus, to get heads on all $64$ squares, we must change the parity of the number of heads on colors $1$ and $2$ without changing the parity of the number of heads on color $0$. However, this is impossible: each move changes the parity of the number of heads on each color, so the number of moves must be odd to take care of colors $1$ and $2$ and even to take care of color $0$.

  • $\begingroup$ This is pretty much Chris Hartman's answer to the duplicate question, but with more attention to aesthetics. $\endgroup$ – Gerry Myerson Mar 7 '13 at 5:59
  • $\begingroup$ @Gerry: So I discovered after I posted it; at the time I didn’t even know that there was a duplicate. $\endgroup$ – Brian M. Scott Mar 7 '13 at 6:02

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