第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

ステップ 2/6: 最後のは影響しない

前のステップ次のステップ

ざっくり言うと

最後の位置がの間、その位置は決して選ばれない。

C=C'T\Longrightarrow L(C)=L(C')

詳しい解説

最後の硬貨がなら、の枚数は高々なので枚目は選ばれない。従って最初の枚は独立な枚の配置と全く同じに変化し、である。帰納法によりこの場合は停止し、平均はとなる。 $T$ $n-1$ $n$ $n-1$ $(n-1)$ $C'$ $L(C)=L(C')$ $E_{n-1}$