ニコニコ大百科モバイル

7/2(月)よりスマホまたはPCでアクセスした場合、各デバイス向けのサイトへ自動で転送致します


ハノイの塔


ヨミ: ハノイノトウ
掲示板をミル!
51カキコ!
今週のおすすめ この記事は第359今週のオススメ記事2015年5月5日)に選ばれました!
よりニコニコできるような記事に編集していきましょう。

ハノイの塔とは、パズルゲームの一種である。


概要


3本の棒と、中心にのあいた何枚かの異なる大きさの円盤がある。ゲームスタート時は一番左の棒に下から大きい順に円盤が積み重ねられており、所定のルールに従って全ての円盤を一番右の棒に移動させていく。

単純で理解しやすいゲームであり、小学校中学校算数数学の教材に使われることもある。


ルール



最短手数


上記のルールに従ってn枚の円盤を一番左の棒から一番右の棒へと動かす場合、最少でも2n-1の手数が必要となることが知られている。たとえば、3枚の場合なら23-1=7となり7手必要である。また、最短手数の場合、奇数の手(1手、3手、5手…)は一番小さい円盤を動かす手であり、その次の偶数の手(2手、4手、6手…)は1通りしかない。

3段
[画像]
[画像クリックで1手進む]
1手
[画像]
[←][→]
2手
[画像]
[←][→]
3手
[画像]
[←][→]
4手
[画像]
[←][→]
5手
[画像]
[←][→]
6手
[画像]
[←][→]
7手
[画像]
[←][最初に戻る]
4段
[画像]
[画像クリックで1手進む]
1手
[画像]
[←][→]
2手
[画像]
[←][→]
3手
[画像]
[←][→]
4手
[画像]
[←][→]
5手
[画像]
[←][→]
6手
[画像]
[←][→]
7手
[画像]
[←][→]
8手
[画像]
[←][→]
9手
[画像]
[←][→]
10手
[画像]
[←][→]
11手
[画像]
[←][→]
12手
[画像]
[←][→]
13手
[画像]
[←][→]
14手
[画像]
[←][→]
15手
[画像]
[←][最初に戻る]
5段
[画像]
[画像クリックで1手進む]
1手
[画像]
[←][→]
2手
[画像]
[←][→]
3手
[画像]
[←][→]
4手
[画像]
[←][→]
5手
[画像]
[←][→]
6手
[画像]
[←][→]
7手
[画像]
[←][→]
8手
[画像]
[←][→]
9手
[画像]
[←][→]
10手
[画像]
[←][→]
11手
[画像]
[←][→]
12手
[画像]
[←][→]
13手
[画像]
[←][→]
14手
[画像]
[←][→]
15手
[画像]
[←][→]
16手
[画像]
[←][→]
17
[画像]
[←][→]
18手
[画像]
[←][→]
19手
[画像]
[←][→]
20手
[画像]
[←][→]
21
[画像]
[←][→]
22手
[画像]
[←][→]
23手
[画像]
[←][→]
24手
[画像]
[←][→]
25
[画像]
[←][→]
26手
[画像]
[←][→]
27手
[画像]
[←][→]
28
[画像]
[←][→]
29手
[画像]
[←][→]
30
[画像]
[←][→]
31
[画像]
[←][最初に戻る]
盤の枚数を変える

最短手数についての解説


このゲームを最短手数で終わらせる際、次のような手順で解いていくことになる。

  1. 左の棒に積み重なっている円盤のうち、一番下以外の円盤何らかの方法でん中の棒に移す
  2. 左の棒に残っている一番大きい円盤を右の棒に移す
  3. ん中の棒に残っている円盤をすべて何らかの方法で右の棒に移す

さて、ここで気になるのは「何らかの方法」なのだが、これは全体の円盤の枚数より1枚少ない状態でゲームをするのに等しい。例えば、5枚の円盤ゲームをする場合、「4枚の円盤でのゲーム」を2回行っていることになる。これを1枚の円盤で行うゲームから順に適用していくと、次のようになる。

以上のように回数は増加していき、円盤の枚数がn枚のとき、最短手数は2n-1回であることが確認できる。より厳密に明したい場合は数学的帰納法か漸化式を用いれば明することができる。


伝説


「一番左の棒に64枚の円盤を積み、それら全てを一番右の棒に移し終わったとき世界は滅亡する」という旨の伝説があるが、これは考案者の創作であると考えられている。

前述したとおり、n枚の円盤を移し終えるには最少でも2n-1の手数が必要であるため、円盤64枚の場合に必要な手数は途轍もない数となる。仮に一度も間違えることなく1に1回のペース円盤を動かし続けるとすると264-1、約5845億年の時間が掛かることになる。移し終える前に人類は滅亡してしまうだろう。


関連動画



■sm18348421[ニコ動]

■sm22961677[ニコ動]


関連商品


■azB00IF3VQAM
■azB001A686UE


関連ゲーム



関連項目



外部リンク



最終更新日: 19/10/18 21:31
タグ検索 パソコン版を見る


[0]TOP
ニコニコ動画モバイル
運営元:ドワンゴ