2019 IMO 第 5 题

Let $n$ be a positive integer. Harry has $n$ coins lined up on his desk, which can show either heads or tails. He does the following operation: if there are $k$ coins which show heads and $k > 0$ , then he flips the $k$ 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.)

Prove the process will always terminate, and determine the average number of steps this takes over all $2^{n}$ configurations.

令 $n$ 为正整数。哈利的桌子上排列着 $n$ 硬币，这些硬币可以显示正面或反面。他执行以下操作：如果有 $k$ 个硬币正面朝上且 $k > 0$ ，则将第 $k$ 个硬币翻转过来；否则他会停止该过程。 (例如，以 $TH T$ 开头的过程将为 $TH T\rightarrow H H T\rightarrow H T T\rightarrow T T T$ ，这需要三个步骤。)

证明该过程始终会终止，并确定该过程在所有 $2^{n}$ 配置上执行的平均步骤数。