2
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – ilikecats Nov 23 '20 at 6:57
  • 1
    $\begingroup$ 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$. $\endgroup$ – paw88789 Nov 23 '20 at 9:59
  • $\begingroup$ Ok thanks for the hint. $\endgroup$ – ilikecats Nov 23 '20 at 10:05
0
$\begingroup$

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.

$\endgroup$

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.