The Bank of Bath has issued coins, one side of which bears the letter $H$ and the other side bears the letter $T$. Morgane has lined up $n$ of these coins from left to right. She then performs the following operation repeatedly: if the letter $H$ is visible on exactly $k$ coins, with $k \geqslant 1$, then Morgane flips the $k^{\text{th}}$ coin from the left; if $k=0$, she stops. For example, if $n=3$, the process starting from the configuration $T H T$ will be $T H T \rightarrow H H T \rightarrow H T T \rightarrow T T T$: Morgane therefore stops after 3 operations.

(a) Prove that, regardless of the initial configuration, Morgane must stop after a finite number of operations.

(b) For each initial configuration $C$, we denote $L(C)$ as the number of operations Morgane will perform before stopping. For example, $L(T H T)=3$ and $L(T T T)=0$. Find the average value of the numbers $L(C)$ obtained when $C$ runs through the set of all $2^{n}$ possible initial configurations.
To answer question (a), we can proceed as in the exercises above and assume that there is an initial configuration from which Morgane will continue ad vitam æternam. Under these conditions, let $k$ be the largest integer such that Morgane will flip the $k^{\text{th}}$ coin infinitely many times. There will come a time when this coin shows the letter $T$, and no coin to the right of our $k^{\text{th}}$ coin will be flipped again. But then, if Morgane flips this $k^{\text{th}}$ coin again, it means we had $k$ letters $H$ visible, and now we have $k+1$, which is impossible.

Another way to proceed is to look for a monovariant that will decrease by 1 with each operation and will be 0 for the configuration containing only $T$s: indeed, we will then know the value of $L(C)$ for any configuration $C$.

During each operation, two parameters change obviously: the number of $H$s, which varies from $k$ to $k \pm 1$, and the face visible on the $k^{\text{th}}$ coin. To construct our monovariant, a first idea is to assign a score to each coin depending on the face it shows, plus a collective score depending on the number of visible $H$s: the score of each coin should be 0 if the coin shows its $T$ face, and the collective score should be 0 if all the coins show their $T$ face. We are thus looking for a cumulative score of the form

$$
\mathcal{S}=f(|\Omega|)+\sum_{k \in \Omega} x_{k}
$$

where $k \in \Omega$ if the $k$-th coin shows its $H$ face, and where the $x_{i}$ are real numbers and $f$ is a function such that $f(0)=0$.

When the cardinality of $\Omega$ changes from $k$ to $k-1$, it means the $k^{\text{th}}$ coin has changed from the $H$ face to the $T$ face; when it changes from $k$ to $k+1$, the $k^{\text{th}}$ coin has changed from the $T$ face to the $H$ face. To ensure that $\mathcal{S}$ decreases by 1 in both cases, we want

$$
f(k-1)-f(k)-x_{k}=f(k+1)-f(k)+x_{k}=-1
$$

for all $k \geqslant 0$. We deduce that $x_{k}=f(k-1)-f(k)+1=x_{k-1}+2$ and, by setting $x_{0}=0$, that $x_{k}=2k$ and $f(k)=-k^2$.

Once this choice is made, the cumulative score $\mathcal{S}$ decreases by 1 with each operation, and it is clearly bounded below by $-n^2$, so our sequence of operations is finite.

Let's use this monovariant to answer question (b). Once the operations are performed, we know that $\mathcal{S}=0$. Thus, denoting $\mathcal{S}(C)$ the cumulative score of a configuration $C$, we observe that $L(C)=\mathcal{S}(C)$. We will therefore calculate the average value of these cumulative scores.

First, the average score of the $k^{\text{th}}$ coin is of course $(0+2k)/2=k$. Moreover, the collective score of a configuration is equal, in sign, to the number of pairs (ordered) of coins showing their $H$ face. Thus, every pair of distinct coins will contribute an average of $-1/4$ to the collective score, while every pair formed by the same coin twice will contribute an average of $-1/2$. In conclusion, the average value of $L(C)$ is equal to

$$
(1+2+\ldots+n)-n(n-1)/4-n/2=n(n+1)/2-n(n-1)/4-n/2=n(n+1)/4
$$