tecktom.com

ハノイの塔と2進法：どの円盤が、いつ動くか

2026年度 中3詳説2026年10月6日14分で読めます塾講師木下数列
目次
  1. 1. 最適解の再帰構造をもう一度
  2. 2. 背景：2 進法と 2 進付値
  3. 3. 主結果：第 手で動く円盤は
  4. 4. 移動回数と総手数を数え直す
  5. 5. グレイコード：配置そのものを 進で読む
  6. 6. 応用：目隠しでも解ける反復アルゴリズム

前の記事「ハノイの塔：漸化式が解けると「世界の寿命」がわかる!?」では、円盤 nn 枚を 33 本の杭 A・B・C の間で動かす最小手数が an=2 n−1a_n=2^{\,n}-1 手であることを、漸化式an=2an−1+1a_n=2a_{n-1}+1 から導いた。その導出の要は再帰であった。すなわち「nn 枚を動かす」を「n−1n{-}1 枚を動かす」に帰着させ、実際の手順を一手ずつ具体的に追うことは一切しなかった。ではその具体的な手順のほうは、どんな構造をしているのか。じつは最適解は2 進法で完全に符号化されている。第 mm 手でどの円盤が動くか、各円盤がどの杭に載っているか、総手数がなぜ 2n−12^n-1 になるか。そのすべてが mm を 22 進で書くだけで読み取れる。本稿ではこの対応を、背景から順にきちんと示す1以下の命題はすべて、最適解を生成する短いシミュレーションで n=1,…,7n=1,\dots,7 の全 2n−12^n-1 手について機械的に照合した（第 mm 手の円盤 =ν2(m)+1=\nu_2(m)+1、円盤 kk の移動回数 =2n−k=2^{n-k}、グレイコードの 11 ビット変化 =1=1 円盤の移動、杭位置の閉じた式）。下の脚注へ。

1. 最適解の再帰構造をもう一度

nn 枚を A から C へ最小手数で移す手順は、次の三段だった：

  1. 上の n−1n{-}1 枚を A から B へ移す（an−1a_{n-1} 手）。
  2. 最大円盤 nn を A から C へ移す（11 手）。
  3. n−1n{-}1 枚を B から C へ移す（an−1a_{n-1} 手）。

いま「第何手でどの円盤の番号が動くか」だけを、手の順に一列に並べたものを SnS_n と書こう（円盤は小さいほうから1,2,…,n1,2,\dots,n と番号を振る）。上の三段は、この列がそっくり自分自身の一回り小さい版を2回くり返す形をしていることを意味する：

Sn  =  Sn−1⏟①,    n⏟②,    Sn−1⏟③S_n \;=\; \underbrace{S_{n-1}}_{\text{①}},\;\; \underbrace{n}_{\text{②}},\;\; \underbrace{S_{n-1}}_{\text{③}}

実際、S1=(1)S_1=(1) から始めると

S2=1,2,1S3=1,2,1,  3,  1,2,1S4=1,2,1,3,1,2,1,  4,  1,2,1,3,1,2,1\begin{aligned}S_2&=1,2,1\\S_3&=1,2,1,\;3,\;1,2,1\\S_4&=1,2,1,3,1,2,1,\;4,\;1,2,1,3,1,2,1\end{aligned}

となる。この自己相似な列こそ、以下すべての土台である。中央の項がちょうど各段の最大番号になり、その両側に一段下の模様がくり返される。

2. 背景：2 進法と 2 進付値 ν2\nu_2

22 進法とは、数を 0,10,1 の並びで、右の桁から順に 20,21,22,…2^0,2^1,2^2,\dots の重みで位取りする書き方である（例：6=4+2=110(2)6=4+2=110_{(2)}、11=8+2+1=1011(2)11=8+2+1=1011_{(2)}）。ここで主役になるのは、各正整数 mm に対して定まる22 進付値 ν2(m)\nu_2(m) である。

ν2(m)\nu_2(m) とは

ν2(m)\nu_2(m) を、mm を割り切る 22 の最大べきの指数と定める。すなわち m=2 e⋅(奇数)m=2^{\,e}\cdot(\text{奇数}) と一意に書いたときのee のこと。これは mm の 22 進表記で右に並ぶ 00 の個数に等しく、言いかえれば最下位の 11 が右から数えて第 (ν2(m)+1)(\nu_2(m)+1) 桁にある、ということである。

ν2(1)=0,ν2(2)=1,ν2(3)=0,ν2(4)=2,ν2(6)=1,ν2(8)=3.\begin{aligned}&\nu_2(1)=0,\quad \nu_2(2)=1,\quad \nu_2(3)=0,\quad \nu_2(4)=2,\quad \nu_2(6)=1,\\&\nu_2(8)=3.\end{aligned}

たとえば 6=110(2)6=110_{(2)} は末尾の 00 が 11 個で ν2(6)=1\nu_2(6)=1、最下位の 11 は右から第 22 桁。12=1100(2)12=1100_{(2)} ならν2(12)=2\nu_2(12)=2 である。

3. 主結果：第 mm 手で動く円盤は ν2(m)+1\nu_2(m)+1

定規数列との一致

nn 枚のハノイの塔の最適解において、第 mm 手で動かす円盤の番号は ν2(m)+1\nu_2(m)+1 に等しい（1≤m≤2n−11\le m\le 2^n-1）。番号の並び SnS_n は m=1,2,3,…m=1,2,3,\dots に沿って

1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3,…1,\,2,\,1,\,3,\,1,\,2,\,1,\,4,\,1,\,2,\,1,\,3,\dots

となり、これは定規数列（ruler sequence, OEIS A001511）と呼ばれる、ものさしの目盛りの高さと同じ模様である。

証明（nn に関する帰納法）.　 n=1n=1 のときは第 11 手で円盤 11 を動かすだけで、ν2(1)+1=1\nu_2(1)+1=1 と合う。次に、n−1n{-}1 枚で主張が成り立つと仮定する。全体は 2n−12^n-1 手で、前半 Sn−1S_{n-1} は 2n−1−12^{n-1}-1 手だから、中央の第 2n−12^{n-1} 手が最大円盤 nn を動かす手である。2n−1=100⋯0⏟n−1(2)2^{n-1}=1\underbrace{00\cdots0}_{n-1}{}_{(2)} ゆえ ν2(2n−1)=n−1\nu_2(2^{n-1})=n-1 で、ν2+1=n\nu_2+1=n。中央は合う。

残りは前半（第 1∼2n−1−11\sim 2^{n-1}{-}1 手）と後半（第 2n−1+1∼2n−12^{n-1}{+}1\sim 2^n{-}1 手）で、どちらも中身は Sn−1S_{n-1} である。前半では手番 mm がそのまま n−1n{-}1 枚の問題の手番だから、帰納法の仮定でその円盤は ν2(m)+1\nu_2(m)+1。後半では、第(2n−1+j)(2^{n-1}{+}j) 手（1≤j≤2n−1−11\le j\le 2^{n-1}-1）が Sn−1S_{n-1} の第 jj 手と同じ円盤を動かす。ここで j<2n−1j<2^{n-1}だから、2n−1+j2^{n-1}+j の 22 進表記はjj を n−1n{-}1 桁で（足りない上の桁は 00 で埋めて）書いた表記の左に 11 を一つ足しただけで、右側の桁、とりわけ末尾の 00 の個数は、そっくり変わらない。ゆえに ν2(2n−1+j)=ν2(j)\nu_2(2^{n-1}+j)=\nu_2(j) となり、動かす円盤も ν2(j)+1\nu_2(j)+1 で一致する。以上で nn 枚でも主張が成り立つ。■\blacksquare

33 枚（全 77 手）で読み取る

最初は 33 枚すべてが杭 A：図1。各手で mm を 22 進で書き、枠で囲んだ最下位の 11 の桁位置が、そのまま動かす円盤の番号になる（配置図は左から A・B・C、円盤は大きいほど幅広で濃い）。

手数 mmmm を 22 進で（最下位の 11 を□）ν2(m)+1\nu_2(m)+1 ＝動かす円盤その手のあとの配置
110 0 10\,0\,\boxed{1}0+1=0+1= 図2 円盤 11図3
220 1 00\,\boxed{1}\,01+1=1+1= 図4 円盤 22図5
330 1 10\,1\,\boxed{1}0+1=0+1= 図6 円盤 11図7
441 0 0\boxed{1}\,0\,02+1=2+1= 図8 円盤 33図9
551 0 11\,0\,\boxed{1}0+1=0+1= 図10 円盤 11図11
661 1 01\,\boxed{1}\,01+1=1+1= 図12 円盤 22図13
771 1 11\,1\,\boxed{1}0+1=0+1= 図14 円盤 11図15

4. 移動回数と総手数を数え直す

上の対応から、各円盤の働きぶりも見える。円盤 kk が動くのは ν2(m)+1=k\nu_2(m)+1=k、すなわち ν2(m)=k−1\nu_2(m)=k-1 のとき、つまり mm が 2k−12^{k-1} の奇数倍のときである（m=2k−1, 3⋅2k−1, 5⋅2k−1,…m=2^{k-1},\,3\cdot2^{k-1},\,5\cdot2^{k-1},\dots）。1≤m≤2n−11\le m\le 2^n-1 の範囲にこれは

円盤 k の移動回数=2 n−k(回)\text{円盤 $k$ の移動回数}=2^{\,n-k}\quad(\text{回})

だけある。番号が 11 大きいと回数は半分、最大円盤 nn はちょうど 11 回。総手数はこれらの和で、初項 11・公比 22・項数 nn の等比数列の和として

∑k=1n2 n−k=2 n−1+2 n−2+⋯+2+1=2 n−12−1=2 n−1.\begin{aligned}\sum_{k=1}^{n} 2^{\,n-k}&=2^{\,n-1}+2^{\,n-2}+\cdots+2+1\\&=\frac{2^{\,n}-1}{2-1}\\&=2^{\,n}-1.\end{aligned}

2n−12^n-1 を 22 進で書けば 11⋯1⏟n(2)\underbrace{11\cdots1}_{n}{}_{(2)}（11 が nn 個）で、各円盤がちょうど一つの桁を受け持つ、と読める。前の記事で漸化式から得た 2n−12^n-1 が、ここでは一手ごとの数え上げから再び現れた。

5. グレイコード：配置そのものを 22 進で読む

「どの円盤が動くか」だけでなく、各時点の配置も 22 進と結びつく。鍵は反射 22 進グレイコード

G(m)=m⊕⌊m/2⌋(⊕ はビットごとの排他的論理和)\begin{aligned}G(m)&=m\oplus\lfloor m/2\rfloor\qquad (\oplus\text{ はビットごとの排他的論理和})\end{aligned}

である。G(0),G(1),G(2),⋯=0,1,3,2,6,7,5,4,…G(0),G(1),G(2),\dots=0,1,3,2,6,7,5,4,\dots は、隣り合う 22 数がちょうど 11 ビットだけ違うという性質をもつ 00 以上の整数の並べ替えである。

11 手 == 11 ビット反転 == 11 円盤の移動

G(m−1)G(m-1) と G(m)G(m) が異なるただ一つのビットは、右から第 (ν2(m)+1)(\nu_2(m)+1) 桁にある（これはグレイコードの定義からすぐ従う）。一方ハノイの第 mm 手で動くのは円盤 ν2(m)+1\nu_2(m)+1 であった。よって、

m を 1 進めて配置を 1 手変える⟺  G(m) の第 (ν2(m)+1) 桁が反転する\begin{gathered}m\text{ を }1\text{ 進めて配置を }1\text{ 手変える}\\\Longleftrightarrow\;G(m)\text{ の第 }(\nu_2(m)+1)\text{ 桁が反転する}\end{gathered}

が完全に対応する。ハノイの最適解を進めることは、グレイコードで数を数えることにほかならない。第 kk 桁が円盤 kk を担い、桁が反転するたびにその円盤が動く。

さらに、各円盤の行き先にも規則がある。円盤 kk は動くたびに、三つの杭をつねに同じ向きに巡回する。向きは n−kn-k の偶奇で決まり、

n−k が偶: A→C→B→A→⋯ ,n−k が奇: A→B→C→A→⋯\begin{aligned}n-k\ \text{が偶}&:\ \text{A}\to\text{C}\to\text{B}\to\text{A}\to\cdots,\\n-k\ \text{が奇}&:\ \text{A}\to\text{B}\to\text{C}\to\text{A}\to\cdots\end{aligned}

である（最大円盤 k=nk=n は n−k=0n-k=0 で偶、一度だけ A→C\text{A}\to\text{C}。最小円盤 k=1k=1 は nn が奇なら A→C\text{A}\to\text{C}から、偶なら A→B\text{A}\to\text{B} から動きだす）。第 mm 手までに円盤 kk が動いた回数を tk(m)=⌊(⌊m/2k−1⌋+1)/2⌋t_k(m)=\bigl\lfloor(\lfloor m/2^{k-1}\rfloor+1)/2\bigr\rfloor とすれば、円盤 kk の載る杭は上の巡回を tk(m)t_k(m) 歩進めた先であり、これで任意の時刻 mm の全配置が閉じた式で定まる。

6. 応用：目隠しでも解ける反復アルゴリズム

最小円盤の巡回規則だけを取り出すと、再帰も記憶も使わずに最適解を打てる。次を交互にくり返すだけでよい。

反復解（グレイコード順）

  1. 奇数手（第 1,3,5,…1,3,5,\dots 手）では、最小円盤を巡回の向きに 11 つ進める（nn が偶なら A→B→C→A\text{A}\to\text{B}\to\text{C}\to\text{A}、nn が奇なら A→C→B→A\text{A}\to\text{C}\to\text{B}\to\text{A}）。
  2. 偶数手では、最小円盤を含まない唯一の合法手を打つ（そのような手はつねにちょうど 11 通り）。

これを 2n−12^n-1 手くり返すと、円盤はすべて C に正しく積み上がる。

なぜ偶数手の合法手が一意かというと、最小円盤以外の 22 本の杭の一番上を比べれば、小さいほうを大きいほうへ載せる手しか許されないからである（一方の杭が空なら、もう一方の一番上をその空の杭へ移す手だけが許される。両方とも空になるのは全円盤が最小円盤と同じ杭にあるとき、すなわち最初と最後の配置だけなので、偶数手では起こらない）。奇数手・偶数手いずれも「次の一手」がその場の状況だけで決まるので、先の手順を覚えておく必要がない。前の記事で見た再帰は「全体を追わずに済ませる」考え方だったが、こちらは反対に、一手ごとの確定した規則として同じ最適解を与える。同じ最適解を、上からたたむ再帰と、下から数えるグレイコードという二つのまったく異なる言葉で言い表せる、というのがこの対応の要点である。

まとめ：ハノイの塔と 22 進法

  1. 最適解の円盤番号列は自己相似 Sn=Sn−1,n,Sn−1S_n=S_{n-1},n,S_{n-1}。第 mm 手の円盤はν2(m)+1\nu_2(m)+1（定規数列）。
  2. 円盤 kk は 2n−k2^{n-k} 回動き、総和は 2n−12^n-1。2n−1=1⋯1⏟n(2)2^n-1=\underbrace{1\cdots1}_{n}{}_{(2)}。
  3. 配置の遷移はグレイコード G(m)=m⊕⌊m/2⌋G(m)=m\oplus\lfloor m/2\rfloor の 11 ビット反転。各円盤は杭を一方向に巡回し、配置は mm から閉じた式で定まる。
  4. 最小円盤を巡回・残りは唯一手、の反復アルゴリズムで、記憶なしに最適解を打てる。

1　以下の命題はすべて、最適解を生成する短いシミュレーションで n=1,…,7n=1,\dots,7 の全 2n−12^n-1 手について機械的に照合した（第 mm 手の円盤 =ν2(m)+1=\nu_2(m)+1、円盤 kk の移動回数 =2n−k=2^{n-k}、グレイコードの 11 ビット変化 =1=1 円盤の移動、杭位置の閉じた式）。

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

目次PDFPDF

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

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