考える力AI照合済み

ハノイの塔と、64枚の伝説

円盤が64枚あったら、全部を動かすのに何手かかる?
← 一覧にもどる
イメージ図(AI生成)

おもちゃ屋さんで、3本の棒と、大きさのちがう円盤がそろったパズルを見つけました。ルールは3つだけ。1回に動かせるのは1枚、小さい円盤の上に大きい円盤は置けない、そして全部を別の棒へ移す。「すぐできそう」と始めても、なかなか終わりません。このパズルの名前は「ハノイの塔」。手の数をぴたりと言い当てる、きれいな決まりがかくれています。

まず予想!

3本の棒と、大きさのちがう円盤3枚。1回に1枚ずつ動かして、全部を別の棒に移すには、最低で何手かかる?

円盤が3枚なら、何手かかる?

おもちゃ屋さんで、木の棒が3本立った台と、大きさのちがう円盤を見つけました。ルールは3つだけです。1回に動かせるのは、いちばん上の1枚。小さい円盤の上に、大きい円盤は置けない。そして、左の棒にある円盤を、そっくり右の棒へ移す。棒はいつでも使ってかまいません。「すぐできそう」と思って始めると、これが意外に終わりません。

円盤が1枚なら、1手で終わりです。2枚なら、小さいほうをまん中の棒へ、大きいほうを右の棒へ、最後に小さいほうを右の棒へ戻して、3手。では3枚はどうでしょう。小さい順に1・2・3と番号をつけると、「1を右へ、2をまん中へ、1をまん中へ、3を右へ、1を左へ、2を右へ、1を右へ」で、7手で完成します。声に出して番号を読みながら、手でなぞってみてください。

1枚で1手、2枚で3手、3枚で7手。1、3、7と並べて、何か気づきませんか。4枚のときは、10手でしょうか、11手でしょうか。じつは答えは15手です。その理由は、手順を丸暗記するのではなく、「全部をいっぺんに考えない」ことにありました。ここから先は、円盤をひとつずつ追いかける代わりに、「大きい円盤が動く、ちょうどその瞬間」だけをじっと見つめてみます。そこに、手数を言い当てるカギがかくれています。

1手 → 3手 → 7手 → ?

大きな問題を、小さな問題に分ける

さっきの7手を、もう一度よく見てください。4手目で、いちばん大きい円盤の3が動いています。その前の3手は、上に乗っていた1と2を、まん中の棒へどかす作業でした。3が動いたあとの3手は、まん中の棒の1と2を、右の棒の3の上へ乗せる作業です。つまり、3枚の問題は、「2枚を動かす」「いちばん大きいのを1手動かす」「2枚を動かす」の3つに分かれていたのです。

2枚の動かし方は、さっき知りました。3手です。だから3枚は、3手+1手+3手で7手。4枚なら、上の3枚をどかすのに7手、いちばん大きいのに1手、3枚を戻すのに7手で、7+1+7=15手になります。n枚の問題は、n−1枚の問題に分かれ、それはn−2枚の問題に分かれ……と続いて、最後は「1枚を動かす」という、いちばんやさしい問題になります。やさしい問題の答えさえ分かっていれば、それを積み重ねるだけで、どんなに枚数が多くても、手数の答えにたどりつけるのです。

こうして「同じ形の、ひとつ小さい問題」に分けるやり方は、数学でもプログラムでもよく使います。下の図で、実際に円盤を動かしてみましょう。枚数をふやしたら、「いちばん大きい円盤が動くのはいつか」に注目してください。そのとき、ほかの円盤は全部、1本の棒に集まっているはずです。実際に手を動かすと、文章で読むよりずっと早く、規則がからだに入ってきます。

n枚の手数=(n−1枚の手数)+1+(n−1枚の手数)
さわってみよう

棒をタップして、上の円盤を1枚ずつ動かしましょう。右の棒に全部を移せば成功です。枚数を変えて、手数がどう増えるか見てください。迷ったら「ヒント」を押します。

手数は「2を何回かけて、1を引く」

手数を表にしてみましょう。1枚で1手、2枚で3手、3枚で7手、4枚で15手、5枚で31手、6枚で63手、7枚で127手。前の手数を2倍して1を足すと、次の手数になっています。3×2+1=7、7×2+1=15、15×2+1=31、という具合です。一見ばらばらに見える数も、並べて眺めると、きまりがかくれています。数学の発見は、こうして表にして、次の数を予想するところから始まることが多いのです。

この数には、もっとすっきりした見方があります。それぞれの手数に1を足してみてください。2、4、8、16、32、64、128。ぴったり2倍ずつふえています。理由は式で書けます。前の手数に1を足した数を2倍すると、次の手数に1を足した数になるからです。つまり、n枚の手数に1を足した数は「2をn回かけた数」。手数は、それから1を引いて、2のn乗マイナス1です。10枚なら、1024−1で1023手です。

ここで、「7手より少なくできないの?」と疑問がわきます。理由は、いちばん大きい円盤にあります。この円盤は最低1回は動きます。そして動かす前には、上のn−1枚が、ほかの1本の棒に集まっていなければなりません。動かしたあとには、そのn−1枚を、その上へ動かす必要があります。だから、n−1枚の最少手数の2倍に、大きい円盤の1手を足した数より少なくは、できないのです。(上のn−1枚を動かす最少手数は、どの棒からどの棒へ動かすときも同じです。棒の名前をつけかえても、同じ問題だからです。)

最少手数 = 2ⁿ − 1

64枚の塔と、世界の終わりの伝説

この遊びには、有名な伝説がついています。ベナレスという町で、僧そう(お坊さん)たちが、神さまが世界のはじめに置いた64枚の金の円盤を、ルールどおりに別の棒へ移している。すべて移し終えたとき、世界は雷かみなりのような音とともに終わる、という話です。どこかで聞いたことがあるかもしれません。ですが、この話がどこから来たのかを調べてみると、おもしろい事実が見つかります。

この遊びが世に出たのは、1883年のパリです。売り出した人の名は「シャムのN・クロー」(N Claus de Siam)。この名前は、文字を入れかえると「アミアンのリュカ」になります。リュカは、リセ・サン=ルイという学校で教えていたフランスの数学者、エドゥアール・リュカだと、数学史の資料に書かれています。伝説は、この遊びといっしょに語られていました。ベナレスの伝説が、そのずっと前から語り継がれていたのかどうかは、確認できていません。

では、64枚だと何手でしょう。2⁶⁴−1で、18446744073709551615手。約1844京6744兆手です。1秒に1手、休まず動かしたとしても、約5845億年かかります。伝説の「世界の終わり」を、心配する必要はなさそうです。円盤を1枚ふやすと、かかる時間は2倍より少し多くなります。それを64回くり返した64枚の塔は、もう「遊び」の大きさを、はるかにこえているのです。

2⁶⁴ − 1 = 18446744073709551615

何枚までなら、人間にできる?

1秒に1手の速さで続けると、時間はこうなります。10枚は1023手で、約17分。20枚は1048575手で、約12日。30枚は1073741823手で、約34年。64枚は約5845億年。枚数が10枚ふえるごとに、手数は約1000倍ずつふえていきます。20枚から30枚へ、さらに1000倍。「12日」が「34年」に変わるのです。10枚のうちは、お昼休みに終わる遊びだったものが、気づけば一生かけても終わらない作業になっています。

紙を折るたびに厚さが2倍になって、42回で月に届く「紙を折る」の章と、同じ仕組みです。2倍をくり返すと、人間の感覚では追いつけない数になります。ただ、この章で大事にしたいのは、大きさにおどろくことより、「分けて考えたから、手数をぴたりと言い当てられた」ことです。64枚を実際に動かさなくても、頭の中だけで、手数の答えが出せたのですから。

実際に遊ぶときのコツも、ひとつ紹介します。いちばん小さい円盤は、奇数番目の手(1手目、3手目、5手目…)で必ず動かします。その向きは、いつも同じ回り方です。全部の枚数が奇数で右へ移すときなら、左→右→まん中→左→右…と回ります。枚数が偶数なら、左→まん中→右→左…と、逆の回り方になります。偶数番目の手では、小さい円盤以外で、ルールどおりに動かせる手がちょうど1つしかありません。これを覚えておけば、迷ったときでも、機械のように正しい手を選んで、最少手数のまま進められます。ただし、この規則がなぜ正しいのかまでは、ここでは説明しません。実際に枚数を変えて、確かめてみてください。

トーナメントの試合数と、同じ数

いちばん大きい円盤は1回、2番目に大きい円盤は2回、3番目は4回と、小さくなるほど、動く回数が2倍ずつふえます。4枚の場合は、1回+2回+4回+8回で15手です。1+2+4+8+……と足していった形は、じつは身近なところにもあります。そのひとつを、次に見てみましょう。実際にチームの数を数えて、手数と同じ数が出てくるかどうか、確かめてみます。

たとえば、64チームのトーナメントです。決勝は1試合、準決勝は2試合、準々決勝は4試合と、1回戦に向かって、試合数が2倍ずつふえます。1+2+4+8+16+32で、全部で63試合。2⁶−1と同じです。別の数え方もできます。優勝チーム以外の63チームは、それぞれ1回だけ負けます。1試合に負けるチームは1つなので、試合は63回。同じ答えになります。もし128チームなら、127試合です。63×2+1=127で、円盤が1枚ふえたときと、同じふえ方をしています。

同じ数が、まったくちがう場面に出てくるのは、どちらも「半分に分かれる(または2倍になる)」形をしているからです。円盤とチームという、見た目のまるでちがうものが、同じ「型」を持っていたわけです。数学の道具が、いろいろな場面で使える理由のひとつです。ハノイの塔で見つけた「2のn乗マイナス1」は、円盤の遊びを遠く離れて、スポーツの試合表でも顔を出す数でした。

今日、どこで使う?

散らかった部屋を前にして、「ぜんぶ片づけなきゃ」と思うと、手が止まります。机の上、本棚、床と分けます。本棚はさらに、上の段、下の段と分けます。ハノイの塔と同じように、大きな問題を、ひとつ小さい同じ形の問題に分けていくと、最後は「この1冊を本棚に戻す」という1手になります。どんなに大きな仕事も、一手ずつなら進められます。

パソコンやスマホのフォルダの整理も、同じ考え方です。プログラムを書く人は、同じ形の小さい問題に分けて、自分自身の手順をもう一度使う「再帰(さいき)」という書き方をします。ハノイの塔の手順は、この書き方で、とても短く書けます。身近な道具の中にも、分けて考える知恵が、ちゃんと使われているのです。この章の検算も、実際にそうやって手数を数えました。

大きな数に出会ったときは、「いくつかを2倍し続けたら、どうなるか」と考えてみましょう。毎月2倍にふえる、毎日2倍にひろまる。ニュースやゲームで見かける「急にふえる」には、2倍の積み重ねが隠れていることがあります。そして、むずかしい問題にぶつかったら、「ひとつ小さい問題にできないかな」と聞いてみてください。ハノイの塔の7手も、そうやって見つかりました。

ひとことで言うと大きな問題は、ひとつ小さい問題に分けて考える。

使ってみよう

円盤が6枚のとき、最少で何手?
2を6回かけると 2⁶ = 64
64 − 1 = 63
答え:63手
円盤10枚を、1秒に1手の速さで動かし続けると、最少で何分かかる?
2¹⁰ − 1 = 1023(手)
1023秒 ÷ 60 = 17.05…分
答え:約17分(17分3秒)

よくある「あれ?」

円盤が2倍の枚数になれば、手数も2倍 → 5枚で31手、10枚で1023手。枚数が2倍で、手数は約33倍
「枚数に比例する」と思いがちだからです。実際は、1枚ふえるごとに、手数が2倍より1多くなります。
n枚の最少手数は 2ⁿ 手 → 2ⁿ − 1 手(3枚なら 8手ではなく7手)
「2倍ずつふえる」ことだけ覚えていると、最後の「−1」を落としがちです。1枚で1手、2枚で3手と、小さい数で確かめましょう。

これ、どこで使う?

散らかった部屋の片づけ、大きな宿題の計画、パソコンのフォルダ整理。「ひとつ小さい同じ問題」に分ける考えは、ハノイの塔の外でも役に立ちます。トーナメントの試合数にも、同じ数が出てきます。

なるほど2問

ほんとうは…・出典

【未確認】ベナレスの伝説は、いつから語られていたか

出典(セントアンドリューズ大学の数学史サイト)で確認できたのは、この遊びが1883年にパリで「N・クロー・ド・シャム」という名で出され、伝説が遊びに添えられていたことです。その名前がリュカの名前の文字の並べかえであることも、同じ出典で確認できました。ベナレスの伝説が、1883年より前から別の形で伝わっていたかどうかは、確認できていません。コラムでは「伝えられている話」として書きました。

【未確認】「ハノイ」という名前の由来

遊びの名前の由来は、確認できた資料にくわしい説明がなかったため、本文には書いていません。

「1秒に1手」は仮定

人間が64枚を動かせるはずもないので、「1秒に1手で、休まず動かす」という、現実にはありえない仮定での計算です。1年は365.25日として計算しました。

最少であることの確かめ方

本文では、いちばん大きい円盤の前後に必要な手数から「これより少なくはできない」と説明しました。厳密には、「上のn−1枚を、ある棒から別の棒へ動かす最少手数は、棒の組み合わせによらず同じ」ことも使っています(棒の名前を入れかえても同じ問題になるため)。

出典と確認状態(AI照合済み)

例題・数値はこのサイトのオリジナルです(実在の店・商品とは関係ありません)。

この章で、まちがいや古くなった情報に気づいたら、報告フォームから教えてください