OlympiadBench / 1914 / Let n be a positive integer. Harry has n coins lined up on his desk, each…

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>0, then he flips the k^(th ) coin over; otherwise he stops the process. (For example, the process starting with THT would be THT →HHT→HTT→TTT, which takes three steps.)

Letting C denote the initial configuration (a sequence of nH 's and T 's), write ℓ(C) for the number of steps needed before all coins show T. Show that this number ℓ(C) is finite, and determine its average value over all 2^(n) possible initial configurations C.

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