# maximum possible number of turns for a coin flipping game

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

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