Eight coins are arranged in a circle heads up. A move consists of flipping over two adjacent coins. How many different sequences of six moves leave the coins alternating heads up and tails up?

I need help finding where I went wrong; I know there is another way to do this, but I want to know where this is wrong! Here is my approach:

Label the 8 coins from 1 to 8. Either the even coins will be all tails or the odd coins will be all tails. We'll find the answer for the even coins being all tails, and then double our answer.

There are 2 cases:

  1. One of the even coins is flipped 3x (turns to tails, heads, then back to tails), and the other 3 even coins is flipped 1x (turn to tails). There are 4 choices for which flip is done 3x. We can arrange the sequence in 6!/3! = 120 ways. So 120x4 = 480 sequences.

  2. All even coins are flipped 1x (turn to tails), and one odd coin is flipped 2x (such that it remains a heads). There are 4 choices for which coin is flipped twice. We can arrange sequence in 6!/2! = 360 ways. So 360x4 = 1440.

Add up both cases: 1440 + 480 = 1920. Double our answer to count the ways that the odd coins end up tails, and we get 1920x2 = 3840.

The correct answer however, is 2 times this, or 7680. What am I missing?

  • 1
    $\begingroup$ In your case 1, when you flip even coins, you also flip odd coins. And for a given pattern of even flips, there is more than one possible pattern for odd flips. Something similar in case 2. $\endgroup$ – Henry Jun 26 '20 at 18:54
  • 1
    $\begingroup$ You seem to be missing the fact that each move flips over two adjacent coins. $\endgroup$ – Mike Earnest Jun 26 '20 at 20:31

As already noted in comments you seem to miss the fact that each move flips over two adjacent coins.

Since each moves flips over two adjacent coins the total number of flips of the odd- and even-flipped is equal to 6. For odd-flipped coins it means that the only possible combination of flips is $1113$. For even-flipped coins the sequences are $0222$, $0024$, and $0006$. The latter sequence is however excluded since no matter how one of its adjacent coins is chosen to flip over together two other "odd" coins remain unflipped.

By similar argument in the sequence $0024$ the 2- and 4-coins should be opposite, the both neighbors of the 2-coin being flipped once. That means that the 4-coin is flipped 3 times in a pair with one adjacent coin and 1 time with the other one. Altogether there are $8\cdot2=16$ possible arrangements of the coins (8 ways to choose the 4-coin, and 2 ways to choose 3-coin among its neighbors).

For the sequence $0222$ each of the neighbors of the 0-coin can be flipped only together with adjacent 2-coin. The other flip of the two 2-coins flips over once the odd coins adjacent to the remaining 2-coin (which is opposite to the 0-coin). This means that the latter coin have to be flipped over twice with the same neighbor. Altogether there are $8\cdot2=16$ possible arrangements (8 ways to choose 0-coin, and 2 ways to choose the 3-coin among the neighbors of the opposite 2-coin).

It remains only to order the flips. In the case $0024$ we flip over one pair 3 times and 3 pairs 1 time. So we can permute them in $\frac{6!}{3!1!1!1!}=120$ ways. In the case $0222$ we flip over one pair 2 times and 4 pairs 1 time. So we can permute them in $\frac{6!}{2!1!1!1!1!}=360$ ways.

Hence the overall number to arrange the flips is: $$ 16\cdot120+16\cdot360=7680. $$


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.