第5题

Bath 银行发行一面为、另一面为的硬币。Harry 有枚这样的硬币，从左到右排成一列。他反复进行如下操作：若恰有枚硬币显示，就翻转从左数第枚硬币；否则所有硬币都显示，他便停止。例如当且从开始时，过程为，三次操作后停止。(a) 证明对每个初始配置，Harry 都会在有限次操作后停止。(b) 对每个初始配置，令为停止前的操作次数。求所有个初始配置的的平均值。

H

T

n

k>0

H

k

T

n=3

THT

THT\to HHT\to HTT\to TTT

C

L(C)

L(C)

2^n

第 3/6 步：变换最后为的情形

上一步下一步

通俗地说

从左数等价于从右数。

k-1\text{ heads in the first }n-1\text{ coins }\Longrightarrow\text{flip the }k\text{th left coin}=\text{the }(n-k)\text{th right tail}

详细分析

现在设最后一枚为。若前枚中有枚显示，总数就是，所以规则翻转从左数第枚；它位于前枚中。这些硬币中有枚显示，所选位置就是从右数第枚。因此倒转前个位置并交换后，操作正好变为原规则，只是目标由全为变为全为。 $H$ $n-1$ $k-1$ $k$ $k$ $n-1$ $n-k$ $(n-k)$ $n-1$ $H$ $T$