Question 75
Let $n$ be a positive integer. Harry has $n$ coins lined up on his desk, each showing heads or tails. He repeatedly does the following operation: if there are $k$ coins showing heads and $k\gt 0$, then he flips the $k^{\text{th}}$ coin over; otherwise he stops the process. (For example, the process starting with $T H T$ would be $T H T \rightarrow H H T \rightarrow H T T \rightarrow T T T$, which takes three steps.)
Letting $C$ denote the initial configuration (a sequence of $n$ $H$'s and $T$'s), write $\ell(C)$ for the number of steps needed before all coins show $T$. Show that this number $\ell(C)$ is finite, and determine its average value over all $2^{n}$ possible initial configurations $C$.
Letting $C$ denote the initial configuration (a sequence of $n$ $H$'s and $T$'s), write $\ell(C)$ for the number of steps needed before all coins show $T$. Show that this number $\ell(C)$ is finite, and determine its average value over all $2^{n}$ possible initial configurations $C$.