大中小のお皿が重なったシンク。1枚ずつしか持てず，大きい皿を小さい皿の上には置けない——この「お皿の移し替え」は，パズルとして知られるハノイの塔とぴったり同じ構造をしている。ここでは標準的なハノイの塔の漸化式と解，同じサイズの皿をまとめた「変則ハノイ」の一般式，そしてスペースの数による手数の違いを順に確かめていく。

ハノイの塔の基本設定

ハノイの塔は，3本の棒（スペース）と大きさの異なる何枚かの円盤でできたパズル。はじめは1本の棒に，大きい円盤が下・小さい円盤が上の順で積まれている。これを，次のルールを守って別の棒へまるごと移す。

ルール（3つ）：

1. 一度に動かせるのは，どれかの棒の一番上の円盤1枚だけ。
2. 円盤を置けるのは3本の棒（A・B・C）のいずれか。
3. 小さい円盤の上に大きい円盤を載せてはいけない。

目標：棒Aに積まれた $n$ 枚の円盤を，ルールを守って全て棒Cへ移す。

標準ハノイの塔

具体的な手数

たとえば円盤が3枚のとき，最短の手順は次のようになる。

3枚なら7手。同じように数えていくと，手数は $T(n) = 1, 3, 7, 15, 31, 63, \ldots$ となる。

漸化式の導出

$n$ 枚の皿を動かす最適手順は次の3ステップに分解できる：

1. 上の $n-1$ 枚を真ん中に退避させる （$T(n-1)$ 手）
2. 一番下の大皿1枚を洗って右に移す （1手）
3. $n-1$ 枚を真ん中から右に移す （$T(n-1)$ 手）

したがって次の漸化式が成り立つ：

$$T(n) = 2T(n-1) + 1, \quad T(1) = 1$$

補足（最適性）：ステップ1と3はそれぞれ独立したハノイ問題であり，帰納法により $T(n-1)$ が各ステップの最小手数であることが示せる。よってこの分解は最適戦略を与える。

漸化式の解

変換 $U(n) = T(n) + 1$ を導入する。

$$T(n) = 2T(n-1) + 1 \implies T(n) + 1 = 2(T(n-1) + 1)$$

すなわち $U(n) = 2U(n-1)$。初期値は $U(1) = T(1) + 1 = 2$。

$\{U(n)\}$ は初項 $2$，公比 $2$ の等比数列なので，

$$U(n) = 2 \cdot 2^{n-1} = 2^n$$

$T(n) = U(n) - 1$ より，

$$\boxed{T(n) = 2^n - 1}$$

検証：

$$T(1)=1,\quad T(2)=3,\quad T(3)=7,\quad T(4)=15,\quad T(5)=31 \quad \checkmark$$

枚数に応じた手数

$n$（枚）	$T(n) = 2^n - 1$	$T(n) - T(n-1)$
1	1	—
2	3	2
3	7	4
4	15	8
5	31	16
6	63	32
7	127	64
8	255	128
9	511	256
10	1023	512

差の列 $T(n) - T(n-1)$：

$$T(n) - T(n-1) = (2^n - 1) - (2^{n-1} - 1) = 2^n - 2^{n-1} = 2^{n-1}$$

差の列 $2, 4, 8, 16, \ldots$ は初項 $2$，公比 $2$ の等比数列である。数列の $n$ 項目と $(n-1)$ 項目の差が階差数列と呼ばれる。

変則ハノイの塔（グループ化）

設定：同じサイズの皿がある場合

実際の食器洗いでは，同じサイズの皿が複数枚あることが多い。同じサイズなら重ねても安定するので，ルールを次のように緩める：

緩めたルール：同じサイズの皿どうしは上下を問わず重ねてよい。

すると，同じサイズの皿は1つのグループとして一体に扱える。

グループ化の定式化

$k$ 種類のサイズの皿があり，上（最小サイズ）から数えて $i$ 番目のグループに $g_i$ 枚の皿があるとする（$i = 1, 2, \ldots, k$）。すなわち $g_1$ が最上段（最小），$g_k$ が最下段（最大）である。総枚数は $N = g_1 + g_2 + \cdots + g_k$ 枚。

重要：同じグループ内の皿は同サイズなので一体として動かせる。「$g_i$ 枚を移動する」のに必要な手数は $g_i$ 手（1枚ずつ $g_i$ 回）。

変則ハノイの漸化式

$k$ 段の塔（グループ数 $k$）を動かす最小手数 $T(k)$ を求める。手順は標準ハノイと同じ3ステップ：

1. 上 $k-1$ 段を真ん中に退避 （$T(k-1)$ 手）
2. 一番下のグループ $g_k$ 枚を洗って右に移す （$g_k$ 手）
3. $k-1$ 段を真ん中から右へ （$T(k-1)$ 手）

$$T(k) = 2T(k-1) + g_k, \quad T(1) = g_1$$

閉じた式の導出

漸化式を繰り返し展開する。

$$\begin{aligned} T(k) &= 2T(k-1) + g_k \\ &= 2\bigl(2T(k-2) + g_{k-1}\bigr) + g_k \\ &= 2^2 T(k-2) + 2 g_{k-1} + g_k \\ &= 2^2\bigl(2T(k-3) + g_{k-2}\bigr) + 2 g_{k-1} + g_k \\ &= 2^3 T(k-3) + 2^2 g_{k-2} + 2 g_{k-1} + g_k \\ &\quad \vdots \\ &= 2^{k-1} T(1) + 2^{k-2} g_2 + 2^{k-3} g_3 + \cdots + 2^0 g_k \\ &= 2^{k-1} g_1 + 2^{k-2} g_2 + \cdots + 2^0 g_k \end{aligned}$$

よって：

$$\boxed{T = \sum_{i=1}^{k} g_i \cdot 2^{k-i} = g_1 \cdot 2^{k-1} + g_2 \cdot 2^{k-2} + \cdots + g_k \cdot 2^0}$$

重みの解釈：$i$ 番目のグループの重みは $2^{k-i}$。最上段（$i=1$）の重みが最大 $2^{k-1}$，最下段（$i=k$）の重みが最小 $1$。上のグループほど退避・戻しの回数が多いため，重みが指数的に大きくなる。

標準ハノイとの整合性確認

全グループが1枚の場合（すべての $i$ で $g_i = 1$，$k=n$）：

$$\begin{aligned} T &= 1 \cdot 2^{n-1} + 1 \cdot 2^{n-2} + \cdots + 1 \cdot 2^0 \\ &= 2^{n-1} + 2^{n-2} + \cdots + 1 \\ &= \frac{1 \cdot (2^n - 1)}{2 - 1} = 2^n - 1 \quad \checkmark \end{aligned}$$

標準ハノイの式 $T(n) = 2^n - 1$ と一致する。

具体例の計算と比較表

設定：7枚の皿，3種類のサイズ（k = 3）

上から順に $g_1$（小），$g_2$（中），$g_3$（大）とする。重みは $2^{3-1} = 4$（小，$g_1$），$2^{3-2} = 2$（中，$g_2$），$2^{3-3} = 1$（大，$g_3$）。

一般式（$k=3$ の場合）：

$$T = g_1 \cdot 4 + g_2 \cdot 2 + g_3 \cdot 1$$

注意：最上段（小）の重みが最大。上の皿ほど退避・戻しの操作が繰り返されるため，移動回数への寄与が大きい。

曜日ごとの構成と手数

7枚の皿を，その日の組み合わせ（小・中・大，日によっては特大も）で並べたときの手数。

曜日	小	中	大	特大	手数 $T$
月曜	4	2	1	—	21
火曜	2	2	3	—	15
水曜	2	2	2	1	29
木曜	5	1	1	—	23
金曜	3	2	2	—	18

月曜の計算詳細（$g_1=4$（小），$g_2=2$（中），$g_3=1$（大））：

$$T = 4 \times 4 + 2 \times 2 + 1 \times 1 = 16 + 4 + 1 = 21$$

水曜は4段階（$k=4$，特大1・大2・中2・小2）：

$$T = g_1 \cdot 2^3 + g_2 \cdot 2^2 + g_3 \cdot 2^1 + g_4 \cdot 2^0 = 2 \times 8 + 2 \times 4 + 2 \times 2 + 1 \times 1 = 16 + 8 + 4 + 1 = \mathbf{29}$$

全部バラバラ（7枚・7種類，$k=7$）：

$$T = 2^7 - 1 = 127$$

同じ7枚でも，サイズをまとめられるほど手数は小さくなる（バラバラ127手 → まとめると15〜29手）。

各構成の内訳と寄与割合

構成	小の寄与	中の寄与	大の寄与	特大の寄与	合計
月曜（T=21）	16 (76%)	4 (19%)	1 (5%)	—	21
火曜（T=15）	8 (53%)	4 (27%)	3 (20%)	—	15
水曜（T=29）	16 (55%)	8 (28%)	4 (14%)	1 (3%)	29
木曜（T=23）	20 (87%)	2 (9%)	1 (4%)	—	23
金曜（T=18）	12 (67%)	4 (22%)	2 (11%)	—	18

スペース数の影響

2か所：解なし（$n \geq 2$）

シンクが狭くて2か所しかない（左 + 右のみ，真ん中なし）場合を考える。

$n = 2$ の場合：

• 小皿を移動する先は右しかない（左以外に退避場所がない）。
• 小皿を右に移すと，大皿を右に移せない（小の上に大は載せられない）。
• 小皿を左に戻すと元の状態に戻るだけで，進展しない。

したがって $n \geq 2$ で2か所問題は解不可能。

一般証明（背理法）：$n$ 枚の2か所問題が解けると仮定する。最大の皿（底）を移動するには，その上の $n-1$ 枚が左にあってはならない。しかし2か所では退避先が右のみで，右には最大の皿より小さい皿が存在してはならない。$n-1 \geq 1$ の場合，この矛盾を解消する方法がない。

3か所（標準）

$T_3(n) = 2^n - 1$。これがこれまで見てきた標準ハノイである。

4か所：Frame-Stewart 予想

シンクがもう少し広くて4か所使えると，退避先が複数に分散できるため手数が大幅に減る。

$r$ 枚を4か所で動かすコストを $T_4(r)$，残り $n - r$ 枚を3か所で動かすコストを $T_3(n-r)$ とすると，Frame-Stewart 戦略は：

$$T_4(n) = \min_{1 \leq r \leq n-1} \bigl[ 2 T_4(r) + T_3(n-r) \bigr]$$

具体値（Frame-Stewart 予想）：

$n$（枚）	$T_3(n) = 2^n - 1$（3か所）	$T_4(n)$（4か所予想値）
1	1	1
2	3	3
3	7	5
4	15	9
5	31	13
6	63	17
7	127	25
8	255	33
9	511	41
10	1023	49

注意：Frame-Stewart 予想（1941年）は4か所の最適手数を与えると信じられていたが，何枚の場合でもこの方法が本当に最小なのかは，70年以上にわたり証明されなかった。2014年に Bousch が証明を完成させ，Frame-Stewart のアルゴリズムが最適であることが確定した。

スペース数による比較まとめ

スペース数	結果	$n=10$ の手数
2か所	解なし（$n \geq 2$）	—
3か所	$T(n) = 2^n - 1$	1023
4か所	Frame-Stewart 値（2014年証明）	49

スペースが1か所増えるだけで，$n=10$ において手数が $1023 \to 49$ と約21分の1になる。「シンクの広さは大事」という直感と一致する。

参考文献

1. Frame, J. S. & Stewart, B. M. (1941). “Solution to Advanced Problem 3918.” American Mathematical Monthly, 48(3), 216–219. （JSTOR（当該号 Vol.48 No.3 の Problems and Solutions））
   • 杭が4本の場合の最小手数を与えると予想される戦略（Frame–Stewart 戦略）を提示。本ノート「スペース数の影響」（4か所）の漸化式 $T_4(n)=\min_r[\,2T_4(r)+T_3(n-r)\,]$ の出典。
2. Bousch, T. (2014). “La quatrième tour de Hanoï.” Bulletin of the Belgian Mathematical Society — Simon Stevin, 21(5), 895–912. （Project Euclid（全文））
   • 4本杭における Frame–Stewart 戦略が最適であることを証明。1941年の予想提出から70年以上を経て決着がついた。