2019 IMO Shortlist C3

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

令 $n$ 为正整数。哈利的桌子上排列着 $n$ 硬币，每枚硬币都是正面或反面。他重复执行以下操作：如果有 $k$ 硬币正面朝上且 $k>0$，则将 $k^{\text {th }}$ 硬币翻转过来；否则他会停止该过程。 (例如，以 THT 开始的过程将是 THT $\rightarrow H H T \rightarrow H T T \rightarrow T T T$，这需要三个步骤。)让 $C$ 表示初始配置($n H$ 和 $T$ 的序列)，写 $\ell(C)$ 表示所有硬币显示 $T$ 之前所需的步骤数。证明这个数字 $\ell(C)$ 是有限的，并确定它在所有 $2^{n}$ 可能的初始配置 $C$ 上的平均值。