IMO 2019 Problem 5

The Bank of Bath issues coins with an $H$ on one side and a $T$ on the other. Harry has $n$ of these coins arranged in a line from left to right. He repeatedly performs the following operation: if there are exactly $k>0$ coins showing $H$, then he turns over the $k$th coin from the left; otherwise, all coins show $T$ and he stops. For example, if $n=3$ the process starting with the configuration $THT$ would be $THT \to HHT  \to HTT \to TTT$, which stops after three operations.

(a) Show that, for each initial configuration, Harry stops after a finite number of operations.

(b) For each initial configuration $C$, let $L(C)$ be the number of operations before Harry stops. For example, $L(THT) = 3$ and $L(TTT) = 0$. Determine the average value of $L(C)$ over all $2^n$ possible initial configurations $C$.

Proposed by David Altizio, USA

=========================================

Solution:
This problem can be analyzed by induction.

(a)
If the first coin is $H$, then it won't be flipped until all coins to its right are $T$. And note the process towards it is exactly that of bringing $n-1$ coins to $T$. Then the first coin turns to $T$ and Harry stops.

If the first coin is $T$, say the rightmost $H$ is at position $k$. It is not hard to see all coins to its right will remain $T$ forever, so we only care about coins at positions $[1,k]$. Similarly, the first coin remains $T$ until all coins in $[2,k-1]$ are $T$, which is exactly the process of turning all $k-2$ coins to $T$. Then, the first coin becomes $H$, then the second, then the third, etc. till all coins at $[1,k]$ are $H$. Then the $k$-th coin flips to $T$, then $(k-1)$-th, etc. and eventually Harry stops when the first coin also turns to $T$.

(b)
Let $f(n)$ be the average number of $L(C)$ for $|C|=n$. By the induction above and some calculation, we have $f(n)=f(n-1)+n/2$. Therefore $f(n)=n(n+1)/4$.