ハノイの塔：漸化式が解けると「世界の寿命」がわかる!?

2026年度中3発展2026年10月6日11分で読めます塾講師木下数列

1. 漸化式を立てる：大きい1枚を動かすには
2. 解く：習った二項間漸化式の手順がそのまま使える
3. 伝説：「ハノイの塔」と世界の寿命

$3$ 本の杭 A・B・C があり、A に大きさの違う $n$ 枚の円盤が「大きいものほど下」に積んである。これを全部 C へ移したい。ルールは2つ。ひとつは、一度に動かせるのは各杭のいちばん上の $1$ 枚だけ。そしてもうひとつがこの問題でいちばん大事なルールで、

どの瞬間も、小さい円盤の上に大きい円盤を載せてはいけない

（言いかえれば、どの杭もつねに「大きいものほど下」を保っていなければならない）。この制約があるからこそ手数がふくらみ、あとで見るように漸化式がそのからくりを解き明かす。最小で何手かかるだろうか。

図1　3本の杭と、杭 A に積まれた4枚の円盤

1. 漸化式を立てる：大きい1枚を動かすには

$n$ 枚を A から C へ移す最小手数を $a_n$ とする。着目するのはいちばん下の最大円盤だ。これをA から C へ動かせるのは、その上の $n{-}1$ 枚がすべてどいて最大円盤がむき出しになり、しかも移動先の C が空になった瞬間しかない。そこで手順を次の3段に分ける：

まず上の $n{-}1$ 枚を、ルールを守って $1$ 枚ずつ動かし、いったん空いている杭 B へ移しておく。
むき出しになった最大円盤を A から C へ動かす（ $1$ 手）。
B に集まった $n{-}1$ 枚を、最後に（やはり $1$ 枚ずつ）C へ移す。

真ん中の②は $1$ 手。残る問題は、①と③がそれぞれ何手かということだ。結論から言うと①も③もちょうど $a_{n-1}$ 手になる。「 $a_{n-1}$ 」とは $n{-}1$ 枚を別の杭へ移す最小手数のことだから、これは①③がどちらも円盤 $n{-}1$ 枚のハノイの塔そのものだと言っているに等しい。なぜそう言い切れるのか。鍵は次の一点にある。

最大円盤は「床」とみなせる

最大円盤はどの円盤よりも大きいので、その上にはどんな円盤を載せてもルール違反にならない。だから最大円盤がある杭に置かれているあいだは、それをその杭にくっついた床の一部と思ってよい。残りの円盤をどう動かすうえでも、最大円盤は制約を一切生まないからだ。

これを使うと①③の中身がはっきりする。①では、A の底に最大円盤があるが、いま見たとおりこれは床とみなせるので、実際に相手にするのは上の $n{-}1$ 枚だけ。つまり①は「 $n{-}1$ 枚を A から B へ移す」という一回り小さい同じ問題である。空いている C を作業に使ってよい点まで込めて、条件はもとの問題の杭の名前を取り替えただけだから、手数は $a_{n-1}$ 。

③も同じ構図だ。このとき C の底にはすでに最大円盤が置かれているが、これも床とみなせるので、動かすのはB にある $n{-}1$ 枚だけ。すなわち③は「 $n{-}1$ 枚を B から C へ移す」というやはり $n{-}1$ 枚の問題で、手数は $a_{n-1}$ 。しかも③に入る時点で、B の $n{-}1$ 枚は①でルールを守って動かした結果大きいものほど下に正しく積まれており、そのまま次の問題の初期配置になっている。

こうして $n$ 枚の問題は、同じ形の $n{-}1$ 枚の問題2回ぶんと、最大円盤の $1$ 手にきれいに分解できた。合わせて、 $a_1=1$ と

$a_n=2\,a_{n-1}+1$

という漸化式が立つ。あとはこれを解くだけで、最小手数がぴたりと分かる。

立ちどまって振り返ると、私たちは最大円盤の $1$ 手のまわりで「 $n$ 枚を $n{-}1$ 枚2つに置きかえる」という一段の分解をしただけで、実際の手順を一手ずつ具体的にたどってはいない。同じ形の一回り小さい問題に帰着させ、その関係を式にしたものが漸化式である。この「自分より小さい同じ問題に投げてしまう」考え方（再帰）のおかげで、あとで見る $2^{64}-1$ という天文学的な手数さえ、頭の中で操作を全部並べることなく求められる。ここにこの問題の難しさと、それを飼いならす漸化式の強さがある。裏を返せば、この分解が一通りに定まるからこそきれいに解けたのであって、分解の仕方に選択肢が生まれたとたんに問題は難しくなる（最後のコラムで触れる杭 $4$ 本以上が、まさにその例である）。

2. 解く：習った二項間漸化式の手順がそのまま使える

$a_n=2a_{n-1}+1$ は、隣り合う2項を結ぶ二項間漸化式である。授業で習った特性方程式1漸化式 $a_n=pa_{n-1}+q$ の $a_n,\ a_{n-1}$ をともに $\alpha$ に置きかえた方程式 $\alpha=p\alpha+q$ のこと。高校数学で、この型の漸化式を等比数列に直すときに使う。下の脚注へを使う手順をそのままなぞろう。まず、漸化式の $a_n$ と $a_{n-1}$ をともに $\alpha$ に置きかえた方程式 $\alpha=2\alpha+1$ を解くと $\alpha=-1$ 。この $\alpha$ を代入した式

$-1 = 2\cdot(-1)+1$

を、もとの漸化式 $a_n=2a_{n-1}+1$ から辺々引くと、じゃまな定数 $+1$ が消えて

$\begin{aligned}a_n-(-1)&= 2\{a_{n-1}-(-1)\},\\\text{すなわち}\ a_n+1&= 2\,(a_{n-1}+1)\end{aligned}$

となる。ここで $b_n:=a_n+1$ とおくと $b_n=2\,b_{n-1}$ 、つまり数列 $\{b_n\}$ は公比 $2$ の等比数列をなす。初項は $b_1=a_1+1=2$ だから $b_n=2\cdot 2^{\,n-1}=2^{\,n}$ 、よって $a_n+1=2^{\,n}$ 、すなわち

$a_n=2^{\,n}-1$

試しに漸化式 $a_n=2a_{n-1}+1$ を、 $a_1=1$ から手でたどってみよう：

$\begin{aligned}&a_2=2\cdot1+1=3,\quad a_3=2\cdot3+1=7,\quad a_4=2\cdot7+1=15,\\&a_5=2\cdot15+1=31,\ \dots\end{aligned}$

たしかに $2^n-1$ （ $1,3,7,15,31,\dots$ ）とぴたり一致する。図の $4$ 枚なら $2^4-1=15$ 手だ。

コラム：これは「最小」なのか

$2^n-1$ 手で移せるのは上で示したとおり。実はこれが最小でもある。最大円盤はどこかで必ず最低1回は動かねばならず、その瞬間には残り $n{-}1$ 枚が1本の杭に退避しきっていなければならない。最大円盤を初めて動かすまでに「 $n{-}1$ 枚を1本の杭へどける」のに最低 $a_{n-1}$ 手、最後に動かして C に置いた瞬間にも残り $n{-}1$ 枚は1本の杭に集まっているので、そこから「 $n{-}1$ 枚を C へ戻す」のにまた最低 $a_{n-1}$ 手が要る（前者は初めて動かす前、後者は最後に動かした後なので重ならない）。だから $a_n\ge 2a_{n-1}+1$ 。到達可能な $2^n-1$ が、同時に下限でもある。

3. 伝説：「ハノイの塔」と世界の寿命

ここまで「 $3$ 本の杭に円盤を積みかえるパズル」と呼んできたが、これにはハノイの塔という名前がある。 $1883$ 年にフランスの数学者リュカ（É. Lucas）が考案して玩具として売り出したもので2リュカは「 $N.$ Claus（de Siam）＝シャムのクラウス教授」という偽名で発売した。これは本名Lucas d'Amiens（アミアンのリュカ）などのアナグラムである。下に述べる「ベナレスの寺院で $64$ 枚の黄金円盤を移し終えると世界が終わる」という伝説は、この玩具に同梱されたリーフレットに記されていたものである。出典：ウィキペディア日本語版「ハノイの塔」（ $2026$ 年 $7$ 月 $22$ 日閲覧）。下の脚注へ、その商品には次の言い伝えが添えられていた。ある寺院で僧たちが $64$ 枚の黄金円盤を（このパズルと同じ規則で）休みなく移し続けており、それを移し終えたとき世界が終わる、というのである。必要な手数は

$\begin{aligned}a_{64}&=2^{64}-1\\&=18{,}446{,}744{,}073{,}709{,}551{,}615\\&\approx 1.8\times10^{19}\ (\text{手}).\end{aligned}$

毎秒 $1$ 手で休まず動かしても約 $\mathbf{5850}$ 億年。宇宙の年齢（約 $138$ 億年）の40倍以上かかる。つまり、たとえ僧が一手も休まず動かし続けても、私たちが生きているあいだに終わってしまう心配はまずない。円盤が $1$ 枚増えるたびに手数が約2倍になる（指数の爆発）のが、この途方もない大きさを生んでいる。

枚数 $n$	$1$	$2$	$3$	$5$	$10$	$20$	$30$	$64$
手数 $2^n-1$	$1$	$3$	$7$	$31$	$1023$	約 $10^6$	約 $10^9$	約 $1.8\times10^{19}$

まとめ：ハノイの塔

「上の $n{-}1$ 枚を避難 → 最大を移動 → $n{-}1$ 枚を戻す」で漸化式 $a_n=2a_{n-1}+1$ 。
$a_n+1$ が公比 $2$ の等比数列 → $a_n=2^n-1$ 。これは達成値かつ最小。
$1$ 枚増えると手数は約2倍（指数爆発）。 $64$ 枚で $\approx1.8\times10^{19}$ 手＝宇宙年齢の40倍超。

コラム：杭を増やすと？（4本以上のハノイの塔）

杭が $3$ 本だと最小 $2^n-1$ 手だった。杭を増やすと、よけておく円盤を複数の杭に分散できるぶん、もっと少ない手数で済む。とくに杭が $n{+}1$ 本以上あれば、上の $n{-}1$ 枚を $1$ 枚ずつ別々の空き杭にのけられるので、「 $n{-}1$ 枚をのける（ $n{-}1$ 手）→ 最大円盤を移す（ $1$ 手）→ $n{-}1$ 枚を戻す（ $n{-}1$ 手）」で、合わせて $2n-1$ 手で完成する（たとえば杭 $4$ 本・円盤 $3$ 枚なら $2\cdot3-1=5$ 手）。指数の $2^n-1$ が一気に $1$ 次式 $2n-1$ まで小さくなるのは劇的だ。

では、杭 $4$ 本で円盤がもっと多いときの最小手数は？じつはこれは $3$ 本のときのようなきれいな公式にはならず、最小手数を求める問題はずっと難しくなる。退避先が複数あると、さきほどの「小さい問題への分解」が一通りに決まらず、上の何枚を・どの空き杭へ・どうよけるかに選択肢が生まれて、どの分け方が最短かを別に探さねばならないからだ（ $3$ 本のとき再帰がそのまま最小手数を与えたのは、分解が一意だったからにほかならない）。実際、杭 $4$ 本の最小手数がようやく証明されたのは $2014$ 年のことで3 $4$ 本以上での最短手順の候補は $1941$ 年に J. S. Frame と B. M. Stewart が独立に与えたが（Frame–Stewart のアルゴリズム）、それが本当に最小だという証明は長く未解決だった。杭 $4$ 本についてはT. Bousch が $2014$ 年に解決した（“La quatrième tour de Hanoï,” Bull. Belg. Math. Soc. Simon Stevin 21 (2014), 895–912）。 $5$ 本以上での最適性はいまも未解決である（Frame–Stewart 予想）。下の脚注へ、 $5$ 本以上ではいまも完全には決着していない。身近なパズルの一歩先に、まだ研究されている問題が広がっている。

1　漸化式 $a_n=pa_{n-1}+q$ の $a_n,\ a_{n-1}$ をともに $\alpha$ に置きかえた方程式 $\alpha=p\alpha+q$ のこと。高校数学で、この型の漸化式を等比数列に直すときに使う。

2　リュカは「 $N.$ Claus（de Siam）＝シャムのクラウス教授」という偽名で発売した。これは本名Lucas d'Amiens（アミアンのリュカ）などのアナグラムである。下に述べる「ベナレスの寺院で $64$ 枚の黄金円盤を移し終えると世界が終わる」という伝説は、この玩具に同梱されたリーフレットに記されていたものである。出典：ウィキペディア日本語版「ハノイの塔」（ $2026$ 年 $7$ 月 $22$ 日閲覧）。

3　 $4$ 本以上での最短手順の候補は $1941$ 年に J. S. Frame と B. M. Stewart が独立に与えたが（Frame–Stewart のアルゴリズム）、それが本当に最小だという証明は長く未解決だった。杭 $4$ 本についてはT. Bousch が $2014$ 年に解決した（“La quatrième tour de Hanoï,” Bull. Belg. Math. Soc. Simon Stevin 21 (2014), 895–912）。 $5$ 本以上での最適性はいまも未解決である（Frame–Stewart 予想）。

塾の授業で配った補足資料をもとに書き直しました。

目次 PDFPDF

この記事が含まれている連載

連載塾講師木下木下が作成して塾で配布した補足プリントを公開用にちょっと書き直して置いていきます。結構面白いっしょ。46本の記事・木下智貴

← 塾講師木下の記事一覧へ