『ハノイの塔』解答

◆広島県　清川　育男さんからの解答。

【問題１】

Ｎ＝１　のとき　　　１回。
Ｎ＝２　のとき　　　３回。
Ｎ＝３　のとき　　　７回。
Ｎ＝４　のとき　　１５回。

・・・・・・・・・・・・

Ｎ＝n　のとき　　２ⁿ−１回。

A₁=1。A_n=2×A_n-1+1。　

答え（２ⁿ−１）回。

【コメント】

　このパズルは数学的にきちんとしていますから、解析するのは比較的やさしいですね。
公式ができれば「問題２」も電卓を使えば簡単に解けるはずです。
冗談みたいな問題ですが、ぜひ考えてみてくださいね。

◆広島県　清川　育男さんからの解答。

【問題２】

　２⁶⁴−１
＝１８４４６７４４０７３７０９５５１９９９。

１年は３６５日として、
６０×６０×２４×３６５＝３１５３６０００（秒）。

約５８５０億年後には地球は崩壊していると。
地球が誕生して何億年になるのでしたかね。

【コメント】

　地球が誕生してから、約４６億年だそうです。
５８５０億年後ですか。
まあ、自分は生きていないような気がするので、世界が滅んでもいいでしょう！！

◆石川県　Takashiさんからの解答。

Ｎ枚の円盤をＡ〜Ｃに移すのに必要な回数をＴ(ｎ）とする。
Ｎ段目の円盤をＡ〜Ｃに移すには、ｎ−１段の円盤は全てＢに存在していなければならない。

Ｎ段の円盤を全てＡ〜Ｃに移すには、

Ｔ(ｎ-１)回かけてｎ−1段をＡ〜Ｂに移し、
その後Ｎ段目をＡ〜Ｃに移し、
最後にＴ(ｎ-１)回かけてｎ−１段をＢ〜Ｃに移さなければならない。

よって、

　Ｔ(ｎ)＝２Ｔ(ｎ-１)＋１、Ｔ(１)＝１

計算すると、

Ｔ(ｎ)＝

n-1 �� j=0

２j

Ｔ(ｎ)＝２ⁿ−１

＜感想＞

このパズルは、一番下の段を動かすためにそれより上の段を全て１ヶ所に移動しなければならないので【解】のような考え方がもっとも適切だと思います。

【コメント】

　実は、プログラム自体がこの方法を用いて作られているのですが（再帰）、アルゴリズム的には最もきれいですね。

◆三重県　久保田　尚　さんからの解答。

『ハノイの塔』は、選択授業で取り上げました。

生徒には、色ケント紙を使って大きさの違う円を作り、小さな順にＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆとアルファベットを書いて６枚渡し、動かした順番にアルファベットを書いて、動いた回数を書かせるようにしました。

結果は、

• １枚の時　１回（Ａ）

• ２枚の時　３回（ＡＢＡ）

• ３枚の時　７回（ＡＢＡＣＡＢＡ）

• ４枚の時　１５回
  （ＡＢＡＣＡＢＡＤＡＢＡＣＡＢＡ）

• ５枚の時　３１回
  （ＡＢＡＣＡＢＡＤＡＢＡＣＡＢＡＥＡＢＡＣＡＢＡＤＡＢＡＣＡＢＡ）

• ６枚の時　６３回
  （略・・・アルファベットを書けた生徒はいない）

• 左右対称になる

• 前の回を２倍して１を足すと良い
  （１つ少ない枚数の時の回数（の２倍）に、余分な１枚分を足すことになるので）

１枚少ないときに関連して考えることはできたんだけど、一般式は思いつかないので（当たり前だけど）、それぞれの回数に１を足したらどうなるか考えさせたら、２の枚数乗になることに気がつき、
ｎ枚の時はｎ²−１ということもわかって、そのシンプルさに驚いていました。

他には、回数を２進数で表すと、

１（１枚）、１１（２枚）、１１１（３枚）・・・・と、１が枚数分だけ並ぶというのも美しいと思います。
（案外２進法というのが、この問題のポイントなのかもしれませんね）

◆大阪府の高校生　satoru さんからの解答。

数列で考えて、n枚のときをＡ_nとする。

Ａ_nは、 Ａ_n＝Ａ_n‐1＋１＋Ａ_n‐1
（普通に考えればわかるので説明は略）

これを式変形して（説明略）

Ａ_n＋１＝２（Ａ_ｎ-1＋１）

この式は、等比数列の形なので Ａ₁＝1より

Ａ_n＋１＝（１＋１）２^ｎ-1

よってＡ_n＝２^ｎ―１（答）

◆和歌山県の中学校３年生　中辺路中学校選択数学5人衆 さんからの解答。

1枚から8枚まで実際に動かしてみて、その回数の規則性をみんなで考えました。

1枚   1回
2枚   3回 ＝　　１×２＋１
3枚   7回 ＝　　３×２＋１
4枚  15回 ＝　　７×２＋１　
5枚  31回 ＝　１５×２＋１
6枚  63回 ＝　３１×２＋１
7枚 127回 ＝　６３×２＋１
8枚 255回 ＝１２７×２＋１
n枚　(n-1)枚の回数×２＋１

◆和歌山県の中学校３年生　中辺路中学校選択数学5人衆 さんからの解答。

ヒントをもとに、みんなでもう一度考えました。
そして、次のことに気が付きました。

　　　２＝２
　　　４＝２２
　　　８＝２３
　　１６＝２４
　　３２＝２５
　　６４＝２６
　１２８＝２７
　２５６＝２８

このことについては、この前の時間には気がつきませんでした。
みんなでああなるほどと納得しました。

◆香川県の中学校３年生　ぺこ さんからの解答。

円盤の数	回数	２n
1	1	2
2	3	4
3	7	8
4	15	16
5	31	32
・・・・・
n	2n-1	2n

◆兵庫県の高校生　積　さんま さんからの解答。

２⁶⁴−１
＝１８４４６７４４０７３７０９５５１６１５。

１８４４６７４４０７３７０９５５１６１５÷３６００÷２４÷３６５
＝５８４９４２４１７３５５．０７・・・・・

従って　A,　５８４９億年後

◆福岡県の高校生　くおれ さんからの解答。

n-1個の円盤を動かす。
n番目の円盤を動かす。
その上にまたn-1個の円盤を動かす。
以上より Ａ_n=2Ａ_n-1+1
よって２ⁿ−１

◆海外　あぱれる さんからの解答。

2⁶⁴ は 18446744073709552000 ではないだろう。

2⁶⁴ に対して 1 は誤差として，
2¹⁰ = 10³ と近似すると．

2⁴ x (10³)⁶ 秒かかる．

で，一年は 60x60x24x365 秒で
これも近似して，32x10⁶．

24 x 1018 32 x 106

= 500 x 109．

で，五千億年．

◆京都府　いてまえ？ さんからの解答。

「数学的帰納法」で２ⁿ―１回になることを証明する。

ポイントは、次の１枚をふやすためには、上の段の円盤をすべて移動して、下の１枚を移動したあと、また、その上に上の円盤をすべて移動させることを繰り返す。

n=1のときは、もちろん成り立ちます。

n=kのとき成り立つとすると、
n=k+1のとき、（２^k-1）+１+（２^k-1）

これを計算すると、２^k+1-１

となって、先の式のｎにk+1を代入したものと同じになる。
したがって、すべてのｎについて成り立つ。

◆東京都の小学生　遼太朗 さんからの解答。

まず、３枚の時には３＋１＋３＝７です。

そして、４枚の時は３枚の答えの７＋１＋７となります。
答えは１５です。

５枚の時は４枚の答えである１５＋１＋１５となります。

このとおり、前の枚数の全部をたした答えに１をたして、そしてまた前の枚数の足した答えを足すことです。

◆愛知県の中学校２年生　高橋　大志 さんからの解答。

【問題１】

ｎ＝１のとき１回
ｎ＝２のとき３回
ｎ＝３のとき７回
ｎ＝４のとき１５回
ｎ＝５のとき３１回

　　　　・
　　　　・
　　　　・

となるので、求め方は　（２ⁿー１）　となる。

【高橋　大志 さんからのコメント】

これはわりと簡単ですね。
実は、昨年行われた第５回日本ジュニア数学コンクールに、これ（ハノイの塔）に関係のある問題があったんですよ。
皆さん知ってましたか？

◆栃木県の中学校１年生　たかたか　さんからの解答。

円板の数をｘ枚とすると、世界が終わるまでの時間は、(2^ｘ-1)秒となる。

64枚の円板があるとき、一回の移動に1秒かかるとすると、

　2⁶⁴-1
＝18,446,744,073,709,551,616-1
＝18,446,744,073,709,551,615秒となる。

これを年,日,時,分,秒に直すと、

18446744073709551615(sec)/60/60/24/365

=307445734561825860(min)/60/24/365        |あまり15(sec)
                                          |
=5124095576030431(hour)/24/365            |あまり0(min)
                                          |
=213503982334601(day)                     |あまり7(hour)
                                          |
=584942417355(year)                       |あまり26(day)

つまり、世界が終わる心配は無用なわけである。

◆東京都の中学校１年生　akito さんからの解答。

答えは２ⁿ−１である。

n=kで移動にかかる手数が２^k-1とする。

n=k+1においては一番大きな円盤を動かすためにk段の塔を他の一本に動かしまとめる必要がある。
そこまでに2^k-1手かかり、一番大きな円盤を動かすのに1手、
さらにその上にk段の塔を乗せるのに、2^k-1手、
合計で2^k+1-1手である。

よって帰納的に最初の解が正しいことが証明されている。
（n=1は明らか）

◆北海道の小学生　ぎしょう さんからの解答。

円盤

n＝1のとき：円盤をAからCへ移動
n＞1のとき：

1. (n-1)枚をAからBへ移動
2. 残り１枚をAからCへ移動
3. (n-1)枚をBからCへ移動

n＝1のとき：M(n)=1

n＞1のとき：M(n)=2M(n-1)+1

M(n)
=2M(n-1)+1
=2(2M(n-2)+1)+1
・・・・・・
=2^n-1+2^n-2+2^n-2-1
=2ⁿ-1　

∴2ⁿ-1

◆新潟県の中学校３年生　komodo さんからの解答。

最近あった市の人材教育「数学アカデミー」課題学習内にありやってみました。

円盤が三枚なら

｜１｜　｜　｜
｜２｜　｜　｜
｜３｜　｜　｜

のようにして、モデルとして表し円盤が６枚までやり表にまとめました。

ｘ	１	２	３	４	５	６
Ｙ	１	３	７	15	31	63

その際にＹの値が、+2,+4,+8…となっていくことに注目し
y=2^x-1という式にたどり着きました。

また、その課題の中で円盤が64枚の場合の回数の問題もあったので、先ほどの式に代入して
y=2⁶⁴-1

2⁶⁴を電卓で求めようとしたのですが、桁が表示しきれないので

2⁶⁴
=4³²
=16¹⁶
=(16²)⁸
=256⁸
=(256²)⁴
=65536⁴
=(65536²)²
=4294967296²

そして、4294967296²を地道に計算して、
18446744073709551616が出ましたので、

y=18446744073709551616-1 =18446744073709551615

として回数を求めました。

◆大阪府　assa さんからの解答。

まず、1個なら1回、2個なら3回。3個なら小さい2個を移動して最下段を移動してもう一度小さい2個を今度は大 きい円盤の上に乗せるので、
3+1+3=3×2+1=7、

4個ならまず小さい3個を移動して最下段を移してその上に小さい3個を移動してくるので、
7×2+1=15、

同様に5個なら15X2+1=31。
漸化式はA(n+1)=2A(n)+1

これを変形すると、
A(n+1)+1=2(A(n)+1)
A(n)+1=(A(0)+1)*2ⁿ=2ⁿ

答え、A(n)=2ⁿ-1

◆広島県　yoshihioro さんからの解答。

N枚の円盤を移動させるのに必要な回数をa(n)として
N+1枚の円盤を移動させるのに必要な回数a(n+1)を求めて漸化式を数学的に解いてやればイイ。

つまりn+1枚の円盤を考えるが、まず一番下の（n+1番目)の円盤を無視して考えてやる。

ｎ枚の円盤を一つの棒に（ここではBの棒）移す。
このときa(n)回必要。
そのあと、n+1番目の円盤をｃに移す。
これでa(n)+1回。

そのあとBに重なっているｎ枚の円盤をｃに移してやるのに必要な回数はa(n)回。
よって合計２a(n)+1回必要ということになり、
a(n+1)=2a(n)+1という高校二年生で習う代表的な漸化式を解いてやれば終了。

a(3)=7であるからｎ枚の円盤をすべて移動させるのに必要な移動回数は
２ⁿー１。

　『ハノイの塔』へ

　数学の部屋へもどる