ハノイの塔単語

24件
ハノイノトウ
2.4千文字の記事
  • 15
  • 0pt
掲示板へ
今週のおすすめ この記事は第359今週のオススメ記事2015/5/5)に選ばれました!
よりニコニコできるような記事に編集していきましょう。

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

概要

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

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

ルール

  • 一手につき1枚しか円盤を動かすことはできない。
  • ある円盤の上に、それより大きい円盤を積むことはできない。
  • 棒以外のところに円盤を移動させることはできない。

最短手数

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

3段
1手
2手
3手
4手
5手
6手
7手
4段
1手
2手
3手
4手
5手
6手
7手
8手
9手
10手
11手
12手
13手
14手
15手
5段
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枚の円盤で行うゲームから順に適用していくと、次のようになる。

  • 1枚:円盤を右に動かす……1手
  • 2枚:1枚の円盤ん中に(1手)→一番大きい円盤を右に(1手)→1枚の円盤を右に(1手)……3手
  • 3枚:2枚の円盤ん中に(3手)→一番大きい円盤を右に(1手)→2枚の円盤を右に(3手)……7手
  • 4枚:3枚の円盤ん中に(7手)→一番大きい円盤を右に(1手)→3枚の円盤を右に(7手)……15手
  • 5枚:4枚の円盤ん中に(15手)→一番大きい円盤を右に(1手)→4枚の円盤を右に(15手)……31手
  • 6枚:5枚の円盤ん中に(31手)→一番大きい円盤を右に(1手)→5枚の円盤を右に(31手)……63手
  • 7枚:6枚の円盤ん中に(63手)→一番大きい円盤を右に(1手)→6枚の円盤を右に(63手)……127

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

伝説

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

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

ちなみに関連動画ではTASさんをもってしても127手に0.43かかっているので、単純計算で一手あたり約0.0033300分の1)であり64段には約19億年かかる計算になる。だいぶマシになったがそれでも長い。

関連動画

関連リンク

関連項目

関連記事

親記事

子記事

  • なし

兄弟記事

【スポンサーリンク】

  • 15
  • 0pt
記事編集 編集履歴を閲覧

ニコニ広告で宣伝された記事

大和(艦これ) (単) 記事と一緒に動画もおすすめ!
提供: O3
もっと見る

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

ハノイの塔

49 ななしのよっしん
2019/03/20(水) 02:40:44 ID: 7Ua1Zk6flM
の束をふたつ折りにするには、の大きさがその束の厚さよりも大きくないと
「ふたつ折りにした」と言える状態じゃないような気もするw

【鋭利な物で束をふたつに切断する→重ねる】…A
という形式なら、幾分か現実味がある
…まあどのみち、Aの動作を40回も100回も実際にやるのは不可能だろうから
現実味もクソいのかも知れんけどw
👍
高評価
0
👎
低評価
0
50 ななしのよっしん
2019/11/20(水) 23:22:11 ID: CTEHVx8viw
私はあるヤクザと勝負している
3本の柱A,B,Cがあり、柱Aにある64枚の円盤(上から下で順に大きい)を1枚ずつ柱Bを中継点にして柱Cに移動させる。ただし、どの柱でも上の円盤の方が小さくなければならない。
ヤクザ「このゲーム24時間以内にクリア出来れば、1000万やろう。但し失敗した場合は解体ショーゲストになって貰う」
こんな簡単なゲーム1000万は、美味しいよな(笑)
👍
高評価
0
👎
低評価
0
51 ななしのよっしん
2020/02/23(日) 20:06:46 ID: K6kU4dUdvh
今日買ってやってみた。1時間ほどでコツのようなものを見つけた。

・1手奇数段のとき→端、偶数段のとき→ん中に移動させる
奇数段、偶数段を連続して置いてはならない

......これくらいは皆とっくに気付いてるもんなのかな?
👍
高評価
0
👎
低評価
0
52 ななしのよっしん
2022/03/13(日) 08:31:54 ID: 9MVA0mO5yd
算数教科書の最後の方のストーリー仕立てのコーナーにあった印
👍
高評価
0
👎
低評価
0
53 ななしのよっしん
2022/03/13(日) 09:40:55 ID: qlWdvx7i0X
昔の中にこれをテーマにした問題があったな
小問の最後は6枚詰んだ円盤全に移すのに必要な手数を答えさせる問題だった気がする
👍
高評価
0
👎
低評価
0
54 ななしのよっしん
2022/03/13(日) 11:03:45 ID: ENB1RlcLt3
子供のとき何かのお土産でもらってに置いてあった

構造を理解するとゲーなので、本来インテリアなんでは
👍
高評価
0
👎
低評価
0
55 ななしのよっしん
2022/04/11(月) 00:18:37 ID: k57vocWutL
古典的なハノイの塔って
 ・左の柱にすべての円盤を重ねた状態で開始する
 ・小さな円盤の上に大きな円盤を置けない
というルールのもとに進められるけど
 ・初期配置では円盤を3つのどの柱にも配置できる
 ・初期配置に限り小さな円盤の上に大きな円盤を置ける
というルールでやったらどうなるのかなと考えたら
 ・最短手数が最長になるような初期配置はどのようなものか?
 ・解けない初期配置はあるか?
という疑問が生まれた。まぁこの程度の疑問はすでにかが解決済みだろう。
個人的には、右の柱に逆ピラミッドが最長になるのかなと予想する。
解けない初期配置はないような気がする。なんとな~くだけど。
👍
高評価
0
👎
低評価
0
56 ななしのよっしん
2022/12/11(日) 17:57:50 ID: gAtsQgGG5g
ワーキングスペースの広さは処理速度に直結する
👍
高評価
0
👎
低評価
0
57 ななしのよっしん
2023/02/10(金) 00:30:25 ID: aJqLmsL5cl
宇宙終焉という途方もない時間経過を数学的帰納法で表現した
古代インド人が考えそうな壮大な伝説だとずっと信じてたのに
まさかオモチャの設定だと知った時はショックだった
👍
高評価
0
👎
低評価
0
58 ななしのよっしん
2023/02/10(金) 00:36:10 ID: hxlpM2KHY9
64段って結構高いな。記事の画像の感じ一段2cmでも1mえる
👍
高評価
0
👎
低評価
0