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$.

[i]Proposed by David Altizio, USA[/i]
### Part (a)

We need to show that for each initial configuration, Harry stops after a finite number of operations.

1. **Base Case:**
   - For \( n = 1 \), there are two possible configurations: \( H \) and \( T \).
   - If the coin shows \( T \), the process stops immediately.
   - If the coin shows \( H \), Harry flips it to \( T \) in one operation, and the process stops.
   - Thus, for \( n = 1 \), the process stops after a finite number of operations.

2. **Inductive Step:**
   - Assume that for \( n-1 \) coins, the process stops after a finite number of operations for any initial configuration.
   - We need to show that the process also stops for \( n \) coins.

   **Case 1:** The last coin is \( T \).
   - The configuration looks like \( \underbrace{\boxed{.................}}_{\text{A configuration of } n-1 \text{ coins}} T \).
   - Since there are at most \( n-1 \) coins showing \( H \), the last coin will never be touched.
   - The process inside the box is the same as the process with \( n-1 \) coins, which stops after a finite number of operations by the induction hypothesis.

   **Case 2:** The last coin is \( H \).
   - The configuration looks like \( \underbrace{\boxed{.................}}_{\text{A configuration of } n-1 \text{ coins}} H \).
   - As long as not all coins inside the box are \( H \), the last coin will not be touched.
   - Let \( k \) be the number of \( H \) coins inside the box. There are \( n-k \) coins showing \( T \).
   - Flipping the \( k \)-th coin from the left inside the box is equivalent to flipping the \( (n-k) \)-th coin from the right inside the box.
   - The process inside the box is equivalent to the original process with \( n-1 \) coins, which stops after a finite number of operations by the induction hypothesis.
   - Once all coins inside the box are \( H \), the configuration is \( \underbrace{\boxed{HH\dots HH}}_{\text{n-1 coins}} H \).
   - In \( n \) steps, Harry will flip each coin from \( H \) to \( T \), and the process stops.

By induction, the process stops after a finite number of operations for any initial configuration of \( n \) coins.

\(\blacksquare\)

### Part (b)

We need to determine the average value of \( L(C) \) over all \( 2^n \) possible initial configurations \( C \).

1. **Base Case:**
   - For \( n = 1 \), there are two configurations: \( H \) and \( T \).
   - \( L(H) = 1 \) and \( L(T) = 0 \).
   - The average value is \( \frac{1 + 0}{2} = \frac{1}{2} = \frac{1(1+1)}{4} \).

2. **Inductive Step:**
   - Assume that for \( n-1 \) coins, the average number of steps is \( A(n-1) = \frac{(n-1)n}{4} \).
   - We need to show that for \( n \) coins, the average number of steps is \( A(n) = \frac{n(n+1)}{4} \).

   **Case 1:** The last coin is \( T \).
   - The average number of steps is \( A(n-1) \) since we are only working with \( n-1 \) coins.

   **Case 2:** The last coin is \( H \).
   - To get an all \( H \) configuration, we need an average of \( A(n-1) \) steps, followed by \( n \) steps to accomplish the process.
   - The total average for both cases is:
     \[
     A(n) = \frac{A(n-1) + A(n-1) + n}{2} = \frac{2A(n-1) + n}{2}
     \]
     Substituting \( A(n-1) = \frac{(n-1)n}{4} \):
     \[
     A(n) = \frac{2 \cdot \frac{(n-1)n}{4} + n}{2} = \frac{\frac{(n-1)n}{2} + n}{2} = \frac{(n-1)n + 2n}{4} = \frac{n(n+1)}{4}
     \]

By induction, the average value of \( L(C) \) over all \( 2^n \) possible initial configurations \( C \) is \( \frac{n(n+1)}{4} \).

\(\blacksquare\)