数学B / 漸化式と数学的帰納法

隣にしか動かせないハノイの塔

最難関編漸化式を立てる操作の分解

問題

3本の杭 A, B, C がこの順に一列に並び、杭 A に大きさの異なる $n$ 枚の円盤が大きい順に積まれている。円盤は1回に1枚だけ動かせ、隣り合う杭にしか移動できず(A↔B、B↔C のみ)、小さい円盤の上に大きい円盤を置くことはできない。 $n$ 枚すべてを杭 A から杭 C へ移すのに必要な最小の手数を $a_{n}$ とする。

(1) $a_{n} = 3 a_{n - 1} + 2$ ( $n \geq 2$ )が成り立つことを示せ。

(2) $a_{n}$ を求めよ。

ヒントを見る

いちばん大きい円盤はいつ・どこへ動けるか — 隣接制限の下では C へ一足飛びに行けない。最大円盤が動く瞬間、残りの $n - 1$ 枚はどこに退避していなければならないか。その退避と復帰は、それぞれ「小さいハノイの塔」1回分ではないか。

解答・解説

方針

最大の円盤の動きに注目して操作全体を分解する: 最大円盤は A→B→C と2回動くしかなく、その前後で上の n−1 枚が「A→C」「C→A」「A→C」と3回の完全な引っ越しをする — これで a_n=3a_{n−1}+2 が立つ。解くのは特性方程式型で 3ⁿ−1。

解答

⓪ 発想 — どう考え始めるか。 操作列を正面から数えるのは不可能だ。最大の円盤の動きを軸に全体を分解するのが、漸化式を立てる定石になる。

隣接制限があるから、最大円盤は $A \to C$ と一足飛びには動けず、 $A \to B \to C$ と最低2回動く。そして最大円盤が動く瞬間には、残り $n - 1$ 枚がすべて「今いる杭でも行き先でもない杭」に退避していなければならない。

追いかけると、 $n - 1$ 枚は $A \to C$ 、 $C \to A$ 、 $A \to C$ と3回の完全な引っ越しを強いられる。これが $3 a_{n - 1} + 2$ の正体だ。

重要漸化式を立てる型: 「最大(最後・最外)の要素の動き」で場合を骨組みし、残りを同じ問題の小さい版として数える

① 下からの評価(必要性)。 どんな最短手順でも: 最大円盤が $A \to B$ と動く直前、上の $n - 1$ 枚はすべて杭 C にある(A は最大円盤の下、B は行き先だから空でなければならない)— ここまでに $n - 1$ 枚の A→C の引っ越し(最小 $a_{n - 1}$ 手)が済んでいる。次に最大円盤が $B \to C$ と動く直前、 $n - 1$ 枚はすべて杭 A に戻っている必要がある(C→A の引っ越し、最小 $a_{n - 1}$ 手)。最後に $n - 1$ 枚を A→C へ( $a_{n - 1}$ 手)。最大円盤自身の2手とあわせて

$a_{n} \geq 3 a_{n - 1} + 2$

② 上からの評価(実現可能性)。 逆に、「 $n - 1$ 枚を A→C → 最大を A→B → $n - 1$ 枚を C→A → 最大を B→C → $n - 1$ 枚を A→C」という手順は制約をすべて守り、ちょうど $3 a_{n - 1} + 2$ 手。よって $a_{n} \leq 3 a_{n - 1} + 2$ 。①②から

$a_{n} = 3 a_{n - 1} + 2$

③ 解く((2))。 $a_{1} = 2$ (A→B→C)。特性方程式 $x = 3 x + 2$ より $x = - 1$ : $a_{n} + 1 = 3 (a_{n - 1} + 1)$ で ${a_{n} + 1}$ は初項 $a_{1} + 1 = 3$ 、公比3の等比数列。

$a_{n} + 1 = 3 \cdot 3^{n - 1} = 3^{n} ⟹ a_{n} = 3^{n} - 1$

まとめ: 「最大の円盤の運命」で操作全体が3つの子問題+2手に割れる — 漸化式は数式でなく操作の構造から立てるもの。この最小手数 $3^{n} - 1$ は、実は全円盤配置 $3^{n}$ 通りをすべて1回ずつ通る手順になっている(だから1手も無駄にできない)、というおまけの美しさも持っている。

発展 — 一歩先へ。 $3^{n}$ 個の配置を頂点、合法手を辺としたグラフを描くと、シェルピンスキーの三角形(自己相似のフラクタル)が現れることが知られている。隣接制限ハノイの最短手順は、その三角形の一辺を端から端までなぞる道にあたる。ちなみに通常ルール(どの杭へも動かせる)なら最小手数は $2^{n} - 1$ — 制限が手数を $2^{n}$ 型から $3^{n}$ 型へ跳ね上げる。

答

(1) 最大の円盤を2回動かす分解(証明) (2) $a_{n} = 3^{n} - 1$

別解

「全部の配置を通る」ことから直接数える(状態の視点)。 円盤 $n$ 枚の置き方は、各円盤がどの杭にいるかで決まり(同じ杭の中では大きい順が強制される)、全部で $3^{n}$ 通り。1手動かすごとに配置は1つ変わる。

そこで次を帰納法で示す: 最短手順は、 $3^{n}$ 通りの配置をすべてちょうど1回ずつ通る(だから手数は $3^{n} - 1$ )。

$n - 1$ 枚で正しいとする。 $n$ 枚の最短手順は本解の3幕構成で、第1幕(最大が A にいる間)は上の $n - 1$ 枚が全 $3^{n - 1}$ 配置を1回ずつ通り、第2幕(最大が B)、第3幕(最大が C)も同様。最大円盤の位置が3幕を区別するから、全体で $3 \times 3^{n - 1} = 3^{n}$ 配置をちょうど1回ずつ通る。手数は配置数より1少ない $3^{n} - 1$ 。

漸化式を解く(本解)代わりに、「手数=通る配置の数 $- 1$ 」という対応で答えが直接出た。1手も無駄にできない(同じ配置に二度戻れない)ことまで、おまけで証明されている。

ポイント

最大円盤は A→B→C の2回、その合間に $n - 1$ 枚が3回引っ越す。
下からと上からの両評価で $a_{n} = 3 a_{n - 1} + 2$ 。
$a_{n} + 1 = 3^{n}$ → $a_{n} = 3^{n} - 1$ 。

よくある間違い

隣接制限を忘れて、通常のハノイの塔( $2^{n} - 1$ )と混同する。
「この手順で $3 a_{n - 1} + 2$ 手で運べる」(上からの評価)だけを示し、それより少ない手数では不可能なこと(下からの評価)を落とす。「最小の手数」の証明は両側が要る。
特性方程式 $x = 3 x + 2$ の解 $x = - 1$ を使う場面で、 $a_{n} - 1$ を等比としてしまう(正しくは $a_{n} + 1 = 3 (a_{n - 1} + 1)$ )。