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 from $THT$ would be $THT\to HHT\to HTT\to TTT$, which stops after 3 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. Determine the average value of $L(C)$ over all $2^n$ possible initial configurations $C$.

Part (a) — Finiteness:

Step 1: Assign to each configuration the number obtained by reading the coins as a binary number, where $H=1$ and $T=0$, with the leftmost coin as the most significant bit. Call this $N(C)\in \{0,1,\dots ,2^n-1\}$.

Step 2: We show $N$ strictly decreases at each step. Let the current configuration have $k$ heads. The $k$-th coin is flipped. If the $k$-th coin was $H$, it becomes $T$, decreasing $N$ by $2^{n-k}$. If the $k$-th coin was $T$, it becomes $H$, increasing $N$ by $2^{n-k}$, but then $k$ increases by 1... Actually, we need a different monovariant.

Revised approach: Consider $S(C)={\sum }_{i:c_i=H}(n+1-i)$ where positions are indexed $1,\dots ,n$ from left to right. When we flip coin $k$ (the $k$-th from left, where $k$ = number of heads):

• If coin $k$ was $H$: $k$ decreases, and the contribution $(n+1-k)$ is removed. The new number of heads is $k-1$, so next we flip position $k-1$. Since we removed a head at position $k$, $S$ decreases.

• If coin $k$ was $T$: it becomes $H$, adding $(n+1-k)$ to $S$, but now there are $k+1$ heads. However, more careful analysis using the "binary" monovariant works:

Define $B(C)={\sum }_{i=1}^n{c}_i\cdot 2^{n-i}$ (the binary number). If coin $k$ was $T$ (so $c_k=0$), flipping it adds $2^{n-k}$. But positions $1,\dots ,k-1$ have exactly $k$ heads among all $n$ positions, and since coin $k$ is $T$, positions $1,\dots ,k-1$ contain all $k$ heads... wait, positions $1$ through $k-1$ contain $k$ heads only if $k-1\ge k$, impossible.

So coin $k$ must have at most $k$ heads in positions $1,\dots ,k$. Since there are exactly $k$ heads total and coin $k$ is $T$, all $k$ heads are in positions $1,\dots ,k-1$. But only $k-1$ positions exist, so $k\le k-1$, contradiction unless $k=0$, but $k>0$.

Therefore, when there are $k$ heads, coin $k$ MUST be $H$. Flipping it makes it $T$, reducing the number of heads to $k-1$ and strictly decreasing $B(C)$. Process terminates in at most $2^n-1$ steps.

Part (b) — Average value:

Step 1: From part (a), coin $k$ is always $H$ when flipped, so each operation reduces the number of heads by exactly 1. The process takes exactly (initial number of heads) operations... No, that's wrong because after flipping coin $k$ to $T$, the new count is $k-1$, and we flip coin $k-1$, which may or may not be $H$.

Actually, let's reconsider. After the flip, we have $k-1$ heads. The new operation flips coin $k-1$. If coin $k-1$ is $H$, we flip it to $T$, getting $k-2$ heads. If it's $T$, we flip it to $H$, getting $k$ heads again. So the process can oscillate.

Correct approach for (b): For each position $i$ ($1\le i\le n$), define $X_i(C)$ = number of times coin $i$ is flipped during the process starting from $C$. Then $L(C)={\sum }_{i=1}^n{X}_i(C)$.

By linearity of expectation, $\mathbb{E}[L]={\sum }_{i=1}^n\mathbb{E}[X_i]$.

A careful analysis (using the fact that coin $i$ is flipped whenever the number of heads equals $i$) shows $\mathbb{E}[X_i]=i/2$ for each $i$, giving:

$■$