第5問

Bath 銀行は片面が、もう片面がの硬貨を発行している。Harry はこの硬貨を枚、左から右へ一列に並べる。を示す硬貨がちょうど枚なら、左から枚目の硬貨を裏返す、という操作を繰り返す。それ以外、すなわち全てがのとき停止する。例えばでから始めるととなり、3 回の操作で停止する。(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$