高等学校数学A/数学と人間の活動/ハノイの塔

ゲームのルール

8つの円盤のハノイの塔

「ハノイの塔」は数学ゲームのひとつです。

　

場面としては、3本の杭があって、それに、穴が空いた大きさがそれぞれ違う円盤が、何個か刺さっています。最初の形は、杭の一つに全ての円盤が、上から小さい順に並んでいます。

ゲームの目的は、この円盤の重なりを別の杭に移すことです。この時、以下のルールに従います。

1. 円盤は、ある杭の一番上にあるものを1個ずつしか動かせない。
2. 小さな円盤の上に、大きな円盤を置くことはできない。

パズルとしては、最も少ない手順（円盤の移動の回数）を求めるものです。

由来

ハノイの塔は、フランスの数学者エドゥアール・リュカが1883年に発売したゲーム『ハノイの塔』がルーツです。

同梱のリーフレットには、次のような伝説があると書かれていました。

インドのガンジス河の畔のヴァラナシ（ベナレス）に、世界の中心を表すという巨大な寺院がある。そこには青銅の板の上に、長さ1キュビット（約50cm）、太さが蜂の体ほどの3本のダイヤモンドの針が立てられている。そのうちの1本には、天地創造のときに神が64枚の純金の円盤を大きい円盤から順に重ねて置いた。これが「ブラフマー（インド神話の神）の塔」である。司祭たちはそこで、昼夜を通して円盤を別の柱に移し替えている（移し変えのルールの説明は省略）。そして、全ての円盤の移し替えが終わったときに、世界は崩壊し終焉を迎える。

リーフレットでは「ブラフマーの塔」となっていましたが、パッケージでは「ハノイの塔」となって発売されました。ハノイはベトナムの都市（現在は首都）で、1883年当時、フランスはベトナムへ侵攻を深めており、その年はハノイ周辺を保護領化した年でした（1887年ベトナム全体がフランスの植民地となります。なお、ベトナムは仏教国で、インド神話の神ブラフマーとは、直接の縁はなくあまり馴染みはありません）。この伝説は、リュカによるフィクションであって、インドやベトナムに伝えられていたものではありません。

解き方

円盤が6個の場合の解き方

解き方を考えましょう。

1. 最も基本的な形として、杭をA,B,Cとして、まず、Aに、上からa,b,cの円盤が重なっているものとします（円盤の大きさは a<b<c です）。

杭	上		下
A	a	b	c
B
C

2. 一番上のaしか移せませんから、aをBに移します。

杭	上		下
A		b	c
B	a	×	×
C

3. 次に、bをCに移します。

杭	上		下
A			c
B	a	×	×
C		b	×

4. 次に、cを移す場所を確保するため、aをCに移し、bに重ねます。

杭	上		下
A			c
B
C	a	b	×

5. cを空いているBに移します。

杭	上		下
A
B			c
C	a	b	×

6. bを移すために、aをAかBに移すのですが、Bに移すと手順が増えるのでAに移します。

杭	上		下
A	a	×	×
B			c
C		b	×

7. bをBに移し、cに重ねます。

杭	上		下
A	a	×	×
B		b	c
C

8. aをBに移し、bに重ねることで、AからBへの円盤の移動が完成しました。手順としては、7回の円盤の移動で完成です。

杭	上		下
A
B	a	b	c
C

数学的な考察

さて、ここで、これを数学的に考えてみましょう。

1. 円盤は$n$個あって、杭Aに積まれているとします（上から順につまれた円盤を「山」とここでは呼びます）。
2. $n$個の山を別の杭に移す最小の手順があって、その回数は $a_{n}$回だとします。
3. 一番下の$n$個目の円盤を杭Bに移すには、$(n-1)$個の山を杭Cに移さなければなりません。つまり、ここで $a_{n-1}$回の手順が発生します。
4. 杭Bには何も残っておらず、また、$n$個目の円盤の上に別の円盤はないので、$n$個目の円盤を杭Bに移します。ここで、手順が1個発生しました。
5. $n$個の山を移すには、杭Cにある$(n-1)$個の山を杭Bに移さなければなりません。ここで、また、$a_{n-1}$回の手順が発生し、全ての山が杭Bに移りました。

　

以上から、$n$個の山を別の杭に移す最小の手順 $a_{n}$ は、上の3.~5.の手順の合計 $2a_{n-1}+1$に等しい即ち、$a_{n}=2a_{n-1}+1$ であることがわかります。

　

上の円盤3個の例を当てはめると、$a_{3}=2a_{2}+1$、$a_{2}$は円盤2個の山を動かす手順なので3回、代入して$a_{3}=6+1=7$となります。

　

同様に円盤4個の場合は、$a_{4}=2a_{3}+1=15$となります。試してみてください。

　

一般式に

$a_{n}$ は、$n$が1桁程度であれば、順々に計算していけばその数を求めることができますが、数が大きくなると大変で、計算ミスの可能性も増えます。「世界崩壊」の64個を計算するとかとんでもない話です。

　

そこで、これが $n$ の値を得ることで求められる式（一般式）がないかを探求します。

　

$a_{n}=2a_{n-1}+1$ のように、順を追って値を求める式を漸化式と言い、高等学校数学Bの数列で履修します。

　

漸化式: $a_{n}=2a_{n-1}+1$は、$a_{n}+1=2(a_{n-1}+1)$ と変形できます。同様に、$a_{n-1}+1=2(a_{n-2}+1)$ なので、 $a_{n}+1=2(a_{n-1}+1)=2^{2}(a_{n-2}+1)$ となります。

これを、順々にやっていくと、

$a_{n}+1=2(a_{n-1}+1)=2^{2}(a_{n-2}+1)=\dots =2^{k}(a_{n-k}+1)$

$2^{k}(a_{n-k}+1)$ を見ると、$a_{n-k}$ の $(n-k)$ の部分と、$2$ の累乗の指数 $k$ の和が $n$ であることがわかります。

そうすると、

$a_{n}+1=2^{n-2}(a_{2}+1)=2^{n-1}(a_{1}+1)$

$a_{2}$ は上で $3$ と計算されていますし、$a_{1}$ は、1個の円盤を別の杭に移す手順なので $1$ です。いずれにせよ、代入すると、$a_{n}+1=2^{n}$ となり、

一般式（数列計算では「一般項」と呼びます）: $a_{n}=2^{n}-1$ を得ることができました（公式は、公式集参照）。

　

伝説はどうなる？

では、リュカが作った伝説に当てはめてみましょう。

世界の寿命は、$n=64$ の円盤の移動回数なので、$a_{64}=2^{64}-1=18,446,744,073,709,551,615$回となります。

桁数計算してみましょう。常用対数を使います。$\log _{10}2=0.301$ と近似、桁数計算で $-1$ は無視できるものとして、$\log _{10}2^{64}=64\log _{10}2\fallingdotseq 64\times 0.301=19.26$ で 20桁の数になります。1億（$10^{9}$）→ 1兆（$10^{13}$）→ 1京（$10^{17}$）→ 1000京（$10^{20}$）の桁となります。

円盤が$1$回移動するのに $1$秒要するとしましょう。$2^{64}\div 365.25\div 24\div 60\div 60=5,845.4\times 10^{8}$ となり、5,845億年が世界の寿命ということになります。なお、宇宙の始まりであるビッグバンから現在まで約137億年が経過していると言われています。