# There are eight coins in a row, all showing heads.

There are eight coins in a row, all showing heads. In each move, we can flip over two adjacent coins provided that they are both showing heads or both showing tails. How many different patterns of heads and tails can we obtain after a number of moves?

My solution: We can replace each head with the number '1', and each tail with the number '0', we will then end up with a binary sequence with a starting decimal value of 255. Each move will add or subtract $$3*2^n$$, $$(6 \geq n \geq 0)$$, thus there will be $$255 / 3 + 1 = 86$$ solutions.

There is already a solution on StackExchange here: How many different patterns of heads and tails can we obtain after a number of moves?

Although I understand the accepted solution for the above link, I still don't understand why my solution is wrong, can anyone help continue my solution or give me a hint?

## 2 Answers

You are suggesting that you can reach any multiple of 3. But you can't reach, for instance, $$21$$, that is $$00010101$$.

• This is true, and I have already noted it, but then is there a pattern to the numbers that I cant reach with my method? – ilikecats Nov 23 '20 at 6:57
• You certainly can't reach any multiple of three with an odd number of $1$s in its binary representation. You may also want to consider that the binary place values alternate between being congruent to $1$ and $2$ mod $3$. – paw88789 Nov 23 '20 at 9:59
• Ok thanks for the hint. – ilikecats Nov 23 '20 at 10:05

I wrote a python script to count them by brute force. It turns out that there are $$70$$ strings, and they are exactly the nonnegative multiples of $$3$$ less than $$256$$ with an even number of $$1$$ bits in their binary representation.

Before trying to prove this, I tested the hypothesis, that if their are $$n$$ coins, and $$n$$ is even, then the reachable positions are the nonnegative multiples of $$3$$ less than $$2^n$$ with an even number of $$1$$ bits, and if $$n$$ is odd, the then the reachable positions are the nonnegative numbers less than $$2^n$$ and $$\equiv1\text{mod } 3$$ with an odd number of $$1$$ bits.

This turned out to be true for $$n=2,3,...,10$$ but false for $$n=11,12,13,14,15,16$$. It appears likely then, that some ad hoc argument is required for the $$n=8$$ case, which will essentially come down to brute force.