n 枚を移すには、まず上の n − 1 枚をどかし、最大の円盤を一度移し、それからその n − 1 枚を戻します。だから M(n) = 2M(n − 1) + 1、M(1) = 1 が成り立ち、解は 2ⁿ − 1 です。八枚なら 255 手、三枚なら 7 手で、最初の二つのリンクがそれです。255 はメモリ容量を読む人にはおなじみの数でしょう——符号なしバイトに入る最大の値であり、理由はまさにこれです。
リュカ版は六十四枚の金の円盤と、積み替えが終わると世界が終わるという予言付きでした。一秒に一手なら 2⁶⁴ − 1 = 1.844674407371⋅10+19 手(3 番目のリンク)、およそ 5850 億年、宇宙の年齢の四十倍以上です。目の前の八枚のパズルは一分半で終わるのに。小さな場合を自明にするのと同じ倍増が、大きな場合を地質学的な規模にします。指数関数の意味はそれだけで、255 と 1.844674407371⋅10+19 は六十歩離れた同じ規則なのです。
答え
255
読み方
計算機での 2⁸ − 1 です。2 番目のリンクは三枚、3 番目は世界を終わらせる六十四枚の手数です。
出典
Édouard Lucas marketed the Tower of Hanoi in 1883 as the towers of Brahma at Benares; the minimum for n disks is 2ⁿ − 1, forced by the recurrence M(n) = 2M(n − 1) + 1
電卓で解いてみる
これらのリンクは、この問題の数値が入力済みの状態で適切な電卓を開きます。上の行は画面に表示されるはずの内容です。ぜひ自分で確認してください。