8 coins are in a row and numbered from left to right.

For each turn, we count number of heads. If see k heads among these 8 coins, we flip the k-th coin (H to T, vice versa).

We stop until we see 8 tails and no heads.

What's the maximal number of turns until we stop?

My thoughts: say it's all tails first and the 8th one is head, then we flip from 1 to 7, change them all to heads. Then we change them back to tails. But how do I prove this is maximum?

My thoughts 2: TTTTHHHH will take 36 flips apparently

  • $\begingroup$ What have you tried? $\endgroup$ – Calvin Lin Nov 11 '19 at 1:32
  • $\begingroup$ @CalvinLin added $\endgroup$ – Matt Frank Nov 11 '19 at 1:33
  • $\begingroup$ Try induction on the number of coins $n$. When do you flip the $n$th coin? $\endgroup$ – Brian Tung Nov 11 '19 at 1:35
  • $\begingroup$ Your guess is not maximum. E.g. $THTHTHTH$ takes 17 flips. $\endgroup$ – Calvin Lin Nov 11 '19 at 1:48
  • $\begingroup$ @CalvinLin TTTTHHHH will take 36 flips apparently $\endgroup$ – Matt Frank Nov 11 '19 at 1:53

This is actually interesting.

Let's say there are $n$ coins, and we want to find the maximum flips.

It turns out that,

for $n$ even, the maximum is attained at TT...THH..H, with $n/2$ T and $n/2$ H;

for $n$ odd, the maximum is attained at T...THH...H, with $(n - 1)/2$ T and $(n + 1)/2$ H.

In both cases, the maximun number of flips is $n(n+1)/2$, and the configuration attaining the max is unique.

I'll leave the proof to others, because it's time for bed...

Seems nobody else wants to give a proof ...

OK here we go.

Let $M(n)$ be the maximum number of flips among all configurations of $n$ coins. For such a configuration, there are two possibilities:

  1. The $n$-th coin is T. Then the $n$-th coin will always remain T, until the end of the game. Hence it is essentially a game with $n - 1$ coins and the maximum number of flips is no more than $M(n - 1)$.

  2. The $n$-th coin is H. Then the $n$-th coin will still remain H, until the configuration HH...H is reached. After that, it's easy to see that $n$ more flips leads to the final configuration TT...T.

    Therefore it suffices to consider the number of flips until the configuration HH...H.

    Now we reindex the coins: previously they were indexed $1, 2, \dotsc, n$, and now we index them as $n - 1, \dotsc, 1, 0$. Under this new index system, the rule of flipping becomes: if there are $k$ tails among the first $n - 1$ coins, then we flip the coin with new index $k$. The procedure continues until all the first $n - 1$ coins are H, i.e. we reach the configuration HH...H.

    This is then exactly the same game with $n - 1$ coins, and with heads and tails exchanged. Thus the maximum number of flips until the configuration HH...H is $M(n - 1)$, and hence the total maximum number of flips (until the configuration TT...T) is $M(n - 1) + n$.

Combining 1. and 2., we get $M(n) = M(n - 1) + n$, and the maximum is attained only when the last coin is H, and the first $n - 1$ coins attain the maximum for the game with $n - 1$ coins, with H and T switched and order inversed.

By induction on $n$, this proves exactly our claims.


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.