Francois Flip Frenzy

Let's imagine we have 40 spaces and each space could contain a head. Instead of tails I'll use blank space , this makes the language a bit simpler.

The effect of one of Francois's flip is either: (a) Remove two heads, or (b) Move a head to the right.

If a maximal sequence contains a move of type (a), then it must be removing two heads from the two right-hand spaces. Because if it were removing any other two heads, we could replace that by the longer sequence of moving the heads to the right and then removing them.

If a maximal sequence contains a move of type (b) then it must be moving a head one space to the right. Otherwise we could replace that move by a series of moves of a head one space to the right.

So the longest possible sequence is, starting from $n=0$

Step $n$ part 1: Move the right-most two heads to the far right

Step $n$ part 2: Remove two heads from the right

and we repeat this until all heads are gone.

Now, part 1 requires $4n$ moves: we're moving two coins and each coin has to go as many spaces over as coins we've removed so far.

Part 2 is just $1$ move of course.

And we make $20$ steps in total because each step removes $2$ coins and there are $2\times20$ coins to remove.

So the value we want is $20\times1 + 4(0 + 1 + 2 + ... + 19) = 20 + 4 \times 190 = \boxed{780}$

Here's an informal solution based on pattern-matching. We'll simulate the optimal (longest) sequence of coin flips for 2, 3, 4 and 5 coins based on the principle that we always want to pick the rightmost heads and the leftmost tails, since once there are no heads to the left of a tails it's "stuck".

H H
T T  ->  2 coins, 1 flip

H H H
H T T
T H T
T T H  ->  3 coins, 3 flips

H H H H
H H T T
H T H T
H T T H
T H T H
T T H H
T T T T  ->  4 coins, 6 flips

H H H H H
H H H T T
H H T H T
H H T T H
H T H T H
H T T H H
H T T T T
T H T T T
T T H T T
T T T H T
T T T T H  ->  5 coins, 10 flips

The pattern seems clear: $f(n) = \frac{n(n-1)}{2}$ , and $f(40) = 780$ . Not a proof of course but sometimes a good guess is good enough.

We prove that the answer is $1 + 2 + ... + 39 = \boxed{780}$ .

Clearly we can manage this, by flipping the rightmost pair, then the rightmost two pairs from left to right, then the rightmost three pairs from left to right, and so on (so flip pairs 39, 38, 39, 37, 38, 39, ...).

Conversely, we prove that the pair whose left coin is coin $n$ can be flipped at most n times (giving rise to an upper bound of the sum above). We prove this inductively - clearly pair 1 can be flipped only once, and pair $n-1$ must be flipped between each flip of pair $n$ , so there can be at most one more flip of pair $n$ , as required.

It uses simple Combination. We have 40 coins and choose 2 coins. So, $\left(\! \begin{array}{c} 40 \\ 2 \end{array} \!\right) = \frac{40!}{2!(40-2)!}$ = 780

Assuming we can flip a maximum of N times for A coins. So after flipping N times the sequence would be TTTTTTTTT (A-1 times) with H or T in end.

For A+1 coins after flipping pair of coins N times we get to a situation like H TTTTTTT (H/T). We can make another A flips in this sequence by flipping the coins (1,2),(2,3),(3,4)...(A,A+1) in order. so if we can flip N times for A coins we can flip N+A times for A+1 coins.

A=2 N=1

A=3 N=3

A=4 N=6 so

A=40 N=39*40/2=780

Let $a_n$ be the maximum number of flips possible with $n$ coins. Note that $a_2=1$ , because when there are $2$ coins, a single operation exhausts all the coins showing heads. Now we shall determine a relationship between $a_{n+1}$ and $a_n$ .

Label the $n+1$ coins $1$ , $2$ , $\cdots$ , $n+1$ from left to right. We first ignore coin $1$ , and consider the set $\{2, 3, ..., n+1 \}$ . We can flip these coins in at most $a_n$ ways. Note that after these coins are flipped, coin $1$ will show head, and all coins from the set $\{2, 3, ..., n\}$ will show tails. The $(n+1)^{th}$ coin will either show head or tails (depending on the parity of $n$ ). After we have applied the operation $a_n$ times on the set $\{2, 3, ..., n+1\}$ , we take the set $\{1, 2\}$ and flip them. Then coin $2$ will show heads, and we do the same for $3$ . We then keep on doing this until we reach the set $(n, n+1)$ . Note that this is the optimal strategy here, since this keeps the left-most coin showing heads for the longest number of operations. Hence we obtain the recurrence relation $a_{n+1}= a_n + n$ . We can easily solve this recurrence relation using the fact that $a_2= 1$ : $a_n= 1+2+...+(n-1)= \frac{n(n-1)}{2}$ At $n=40$ , it equals to $\frac{39*40}{2} = 780$ .

Assign each coin a value equal to its distance from the rightmost coin. (Thus, for 40 coins, the values assigned will be 39,...,0.) The problem specifies that the setup is all-coins-showing-heads, but we can prove by induction that for any setup the maximum number of flips that can be performed is equal to the sum of the values of all coins that show heads, which we designate $V$ .

First note that it is irrelevant whether the rightmost coin shows heads or tails (i.e. it doesn't affect the value of $V$ and it will never affect whether a particular flip is legal or not), so WOLOG we can assume it shows tails. (Alternately put, we can replace it with a two-tailed coin.)

Now $V=0$ if and only if all coins show tails, in which case no flips are possible. For the inductive step, $V>0$ means that one or more coins (not the rightmost one) show heads. Francois can choose the rightmost out of those coins, together with the coin (showing tails) to its immediate right. Then the new sum of head-values is $V -1$ as desired, which completes the proof (since any other flip he could choose would also decrease the sum by at least $1$ ).

Let $c(n)$ be the number of turns of n coins when only the left most coin is heads and all the other coins are tails with the right most coin being optionally heads or tails (does not matter). Then $c(1)=0, c(2)=1$ . $c(n)=1+c(n-1)$ . This is because in the c(n) configuration, only the left most coin is heads and all the others are tails and in choosing the two coins, the most number of turns is obtained when we choose the left most coin (forced) and the coin immediately right of it. Any other choice of the second coin will result in lesser number of overall turns. But in the $c(n)$ configuration, when we flip the coin immediately right of the left most coin, the configuration of the second to last from the left coins is exactly the $c(n-1)$ configuration.

Let $t(n)$ be the total number of turns when we start with all heads. Then $t(n)=c(n) + c(n-1) .. + c(1)$ . Applying $c(n)=1+c(n-1)$ recursively, we get, $t(n) = (n-1) + (n-2) + .. + 1$ . So $t(n) = {(n-1)n \over 2}$ . For $n=40$ , we have $t(n) = 780$ .