高等学校数学A/数学と人間の活動/ハノイの塔のソースを表示

{{wikipedia|ハノイの塔}}
== ゲームのルール ==
[[画像:Tower of Hanoi.jpeg|thumb|250px|8つの円盤のハノイの塔]]
:「ハノイの塔」は数学ゲームのひとつです。
:　
:場面としては、3本の杭があって、それに、穴が空いた大きさがそれぞれ違う円盤が、何個か刺さっています。最初の形は、杭の一つに全ての円盤が、上から小さい順に並んでいます。
:ゲームの目的は、この円盤の重なりを別の杭に移すことです。この時、以下のルールに従います。
:#円盤は、ある杭の一番上にあるものを1個ずつしか動かせない。
:#小さな円盤の上に、大きな円盤を置くことはできない。
:パズルとしては、最も少ない手順（円盤の移動の回数）を求めるものです。
== 由来 ==
:ハノイの塔は、フランスの数学者[[w:エドゥアール・リュカ|エドゥアール・リュカ]]が1883年に発売したゲーム『ハノイの塔』がルーツです。
:同梱のリーフレットには、次のような伝説があると書かれていました。

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

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

== 解き方 ==
[[File:Iterative algorithm solving a 6 disks Tower of Hanoi.gif|thumb|円盤が6個の場合の解き方]]
:解き方を考えましょう。
:1. 最も基本的な形として、杭をA,B,Cとして、まず、Aに、上からa,b,cの円盤が重なっているものとします（円盤の大きさは a<b<c です）。
<div style="margin:0 2em 0 4em;">
{| class="wikitable" style="width:30%; table-layout:fixed;text-align:center;"
|+ 
! 杭 !! 上 !!  !! 下 
|-
! A
| a || b || c 
|-
! B
|   ||   || 
|-
! C
|   ||   || 
|}
</div>
:2. 一番上のaしか移せませんから、aをBに移します。
<div style="margin:0 2em 0 4em;">
{| class="wikitable" style="width:30%; table-layout:fixed;text-align:center;"
|+ 
! 杭 !! 上 !!  !! 下 
|-
! A
|  || b ||  c
|-
! B
| a  || × || × 
|-
! C
|   ||   || 
|}
</div>
:3. 次に、bをCに移します。
<div style="margin:0 2em 0 4em;">
{| class="wikitable" style="width:30%; table-layout:fixed;text-align:center;"
|+ 
! 杭 !! 上 !!  !! 下 
|-
! A
|  ||  || c
|-
! B
| a  || × || ×
|-
! C
|  || b || ×
|}
</div>
:4. 次に、cを移す場所を確保するため、aをCに移し、bに重ねます。
<div style="margin:0 2em 0 4em;">
{| class="wikitable" style="width:30%; table-layout:fixed;text-align:center;"
|+ 
! 杭 !! 上 !!  !! 下 
|-
! A
|  ||  || c
|-
! B
|  ||   ||
|-
! C
| a || b || ×
|}
</div>
:5. cを空いているBに移します。
<div style="margin:0 2em 0 4em;">
{| class="wikitable" style="width:30%; table-layout:fixed;text-align:center;"
|+ 
! 杭 !! 上 !!  !! 下 
|-
! A
|  ||  ||
|-
! B
|  ||  || c
|-
! C
| a || b || ×
|}
</div>
:6. bを移すために、aをAかBに移すのですが、Bに移すと手順が増えるのでAに移します。
<div style="margin:0 2em 0 4em;">
{| class="wikitable" style="width:30%; table-layout:fixed;text-align:center;"
|+ 
! 杭 !! 上 !!  !! 下 
|-
! A
| a || × || ×
|-
! B
|  ||  || c
|-
! C
|  || b || ×
|}
</div>
:7. bをBに移し、cに重ねます。
<div style="margin:0 2em 0 4em;">
{| class="wikitable" style="width:30%; table-layout:fixed;text-align:center;"
|+ 
! 杭 !! 上 !!  !! 下 
|-
! A
| a || × || ×
|-
! B
|  || b || c
|-
! C
|  ||  ||
|}
</div>
:8. aをBに移し、bに重ねることで、AからBへの円盤の移動が完成しました。手順としては、7回の円盤の移動で完成です。
<div style="margin:0 2em 0 4em;">
{| class="wikitable" style="width:30%; table-layout:fixed;text-align:center;"
|+ 
! 杭 !! 上 !!  !! 下 
|-
! A
|  ||  ||
|-
! B
| a || b || c
|-
! C
|  ||  ||
|}
</div>
===数学的な考察===
:さて、ここで、これを数学的に考えてみましょう。
: 
:#円盤は<math>n</math>個あって、杭Aに積まれているとします（上から順につまれた円盤を「山」とここでは呼びます）。
:#<math>n</math>個の山を別の杭に移す最小の手順があって、その回数は <math>a_n</math>回だとします。
:#一番下の<math>n</math>個目の円盤を杭Bに移すには、<math>(n-1)</math>個の山を杭Cに移さなければなりません。つまり、ここで <math>a_{n-1}</math>回の手順が発生します。
:#杭Bには何も残っておらず、また、<math>n</math>個目の円盤の上に別の円盤はないので、<math>n</math>個目の円盤を杭Bに移します。ここで、手順が1個発生しました。
:#<math>n</math>個の山を移すには、杭Cにある<math>(n-1)</math>個の山を杭Bに移さなければなりません。ここで、また、<math>a_{n-1}</math>回の手順が発生し、全ての山が杭Bに移りました。
:　
:以上から、<math>n</math>個の山を別の杭に移す最小の手順 <math>a_n</math> は、上の3.~5.の手順の合計 <math>2a_{n-1}+1</math>に等しい即ち、<math>a_n = 2a_{n-1}+1</math> であることがわかります。
:　
:上の円盤3個の例を当てはめると、<math>a_3 = 2a_2 + 1</math>、<math>a_2</math>は円盤2個の山を動かす手順なので3回、代入して<math>a_3 = 6 + 1 =7</math>となります。
:　
:同様に円盤4個の場合は、<math>a_4 = 2a_3 + 1 = 15</math>となります。試してみてください。
:　
;一般式に
:<math>a_n</math> は、<math>n</math>が1桁程度であれば、順々に計算していけばその数を求めることができますが、数が大きくなると大変で、計算ミスの可能性も増えます。「世界崩壊」の64個を計算するとかとんでもない話です。
:　
:そこで、これが <math>n</math> の値を得ることで求められる式（一般式）がないかを探求します。
:　
:<math>a_n = 2a_{n-1}+1</math> のように、順を追って値を求める式を漸化式と言い、[[高等学校数学B]]の[[高等学校数学B/数列|数列]]で履修します。
:　
:漸化式: <math>a_n = 2a_{n-1}+1</math>は、<math>a_n + 1 = 2(a_{n-1}+1)</math> と変形できます。同様に、<math>a_{n-1} + 1 = 2(a_{n-2}+1)</math> なので、 <math>a_n + 1 = 2(a_{n-1}+1) = 2^2(a_{n-2}+1)</math> となります。
:これを、順々にやっていくと、 
::<math>a_n + 1 = 2(a_{n-1}+1) = 2^2(a_{n-2}+1) = \dots = 2^k(a_{n-k}+1) </math>
:::<math>2^k(a_{n-k}+1)</math> を見ると、<math>a_{n-k}</math> の <math>(n-k)</math> の部分と、<math>2</math> の累乗の指数 <math>k</math> の和が <math>n</math> であることがわかります。
:そうすると、
::<math>a_n + 1 = 2^{n-2}(a_2 + 1) = 2^{n-1}(a_1+1)  </math> 
:::<math>a_2</math> は上で <math>3</math> と計算されていますし、<math>a_1</math> は、1個の円盤を別の杭に移す手順なので <math>1</math> です。いずれにせよ、代入すると、<math>a_n + 1 = 2^n </math> となり、
:一般式（数列計算では「一般項」と呼びます）: <math>a_n = 2^n - 1</math> を得ることができました（公式は、[[初等数学公式集/数列#二項間漸化式|公式集]]参照）。
:　
;伝説はどうなる？
:では、リュカが作った伝説に当てはめてみましょう。
:世界の寿命は、<math>n = 64</math> の円盤の移動回数なので、<math>a_{64} = 2^{64} - 1  = 18,446,744,073,709,551,615</math>回となります。
:桁数計算してみましょう。[[初等数学公式集/初等関数の性質#常用対数|常用対数を使います]]。<math>\log_{10} 2 = 0.301</math> と近似、桁数計算で <math>-1</math> は無視できるものとして、<math>\log_{10} 2^{64} = 64 \log_{10} 2  \fallingdotseq 64 \times 0.301 = 19.26</math> で 20桁の数になります。1億（<math>10^9</math>）→ 1兆（<math>10^{13}</math>）→ 1京（<math>10^{17}</math>）→ 1000京（<math>10^{20}</math>）の桁となります。
:円盤が<math>1</math>回移動するのに <math>1</math>秒要するとしましょう。<math>2^{64} \div 365.25 \div 24 \div 60 \div 60 = 5,845.4 \times 10^8</math> となり、5,845億年が世界の寿命ということになります。なお、宇宙の始まりであるビッグバンから現在まで約137億年が経過していると言われています。

{{DEFAULTSORT:はのいのとう}}
[[Category:高等学校数学A]]
[[カテゴリ:数学ゲーム・数学パズル]]
[[カテゴリ:数列]]