Question 10
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 THT would be THT $\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$.
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 THT would be THT $\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$.