第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

第 4/6 步：从全为的状态结束

上一步下一步

通俗地说

所有会从右向左依次翻转。

E_{n-1}+n

详细分析

变换后的过程与枚硬币过程的操作次数分布相同，所以会终止，达到全为平均需要次。从全为的状态开始，原规则依次翻转第枚，恰好再需次即可全为。故最后为的分支平均为，也会终止。 $(n-1)$ $E_{n-1}$ $n,n-1,\ldots,1$ $n$ $E_{n-1}+n$