小学生のための中学受験塾。日能研

日能研教務部算数科　真藤 啓

このページは、「進学レーダー12月号」に連載している算数エッセー「算数好きになるくすり　ハノイの塔（とう）」のうち、問題や解説など、紙面で書ききれなくなったことを補足するために、開設しています。

【目次】

1. 「ハノイの塔（とう）」の考案者リュカについて
2. 「ハノイの塔（とう）」の出自（しゅつじ）について
3. 素数について
4. 完全数とメルセンヌ素数について
5. 論理問題「天国と地獄」　（2004年 浅野中）
6. 「ハノイの塔（とう）」　（1989年 東京女学館中）
7. 素数　（2006年 京都大学前期理系数学）

1. 「ハノイの塔（とう）」の考案者リュカについて

ハノイの塔はフランスのエドゥアルド・アナトール・リュカ（1842年4月4日～1891年10月3日）の考案したものです。
彼は、フィボナッチ数列の研究でも知られています。

「素数の見つけ方」としては「エラトステネスの篩（ふるい）」という方法が知られていますが、大きな素数を探すときに、手間を大幅に節約できるリュカテストという方法を考えました。
この方法は「完全数」や「メルセンヌ素数」を見つけるときにも使えます。

完全数は、メルセンヌ素数と関係が深く、Mがメルセンヌ素数ならば、M×（M＋1）/2が完全数であることが、ユークリッドによって証明されています。また、オイラーは、全ての偶数の完全数が、メルセンヌ素数Mを用いてM×（M＋1）/2で表せることを示しました（オイラーの定理）。
2007年11月現在、44個のメルセンヌ素数と、44個の完全数がみつかっています。

後述のようにリュカは小さい方から12番目の完全数を見つけた記録保持者でもあります。
新しい完全数（やメルセンヌ数）を見つけることは、円周率の続きの小数などとともに、もはや、生身の人間が手計算でできる域をはるかに超えてしまっています。大型コンピュータとか、大勢の人の複数のコンピュータを使って探すようになっています。

2. 「ハノイの塔（とう）」の出自（しゅつじ）について

というわけで、数論の大家であったリュカですが、リュカの書いた「数学遊戯」四巻本には、「ハノイの塔」の解説も載っており、彼は次のような物語を添えました。

「N.クロー教授が私に次のような話をしてくれた。
クローが有名なフェル・フェル・タム・タムの著書を出版するための用件で旅行に出かけたとき、ベナレスの大寺院に寄った。この大寺院には世界の中心を表すドームがあり、その下に真鍮（しんちゅう）の板に立てられた3本のダイヤモンド製の針があった。その針の高さは1キューピットである。太さは蜜蜂の胴体と同じくらいである。創世紀に神は純金製の64枚の円坂をこれら3本のうちの1本の針にはめこんだ。一番大きい円板は、一番下にあって真鍮の板の上に静置されている。その他のものは、上へいくほど小さくなるようにはめこんで置かれている。これが「神プラマーの聖なる塔」である。神プラマーは僧侶たちに、次のような戒律を課した。すなわち、夜となく昼となく、僧侶たちは休むことなく祭壇にやってきて、これらの円板を移し変えよ。ただし、小さい円板の上に大きい円板がのってはいけない。このようにして第1番目のダイヤモンドの針にささっている純金の円板を、第3番目の針に移し変えることに僧侶たちは没頭していた。この作業がすべて終わったとき、この塔もバラモンの僧侶たちも灰塵に帰し、そしてこの世は終わる。」

リュカの上の文は多くの著者に引用されて有名ですが、最初に出てきたクロー（Claus）は自分の名前のリュカ（Lucas）のスペルを並べ変えたものです。また、クローはシャム（現タイ）にあるLi-Sou-Stian大学教教授とありますが、これはリュカが勤務しているSaint Louis大学（リュカは同学の教授）のスペルを変えたものであるといわれています。

なお、フェル・フェル・タム・タムはフェルマーからとったものであることはクライチックが指摘しているとのことです。ただし、ベナレス（バラナシのこと、スペイン読みでベナレス）はインド北部の実在の都市名です。

「梵天（ブラマー）の聖塔（64枚のハノイの塔）」の手順の回数は2⁶⁴－1回となります。すなわち、18446744073709551615回です。1回の操作を1秒、1年を365.25日として計算すると584542046091年（約6000億年）となります。

（参考文献　『新数学辞典（大阪書籍）』、他、フランス語のいくつかのWEBサイト）

3. 素数について

素数という字をすてき（素敵）と読んだ人がいました。このことを思い出すたびに、なぜか「明日という字は明るい日と書くのね」という歌を思い出してしまいます。なお、素数は英語ではプライムナムバーといいます。このプライムには素敵という意味が確かにあります。

素数を見つける方法は、結局はエラトステネスが考えた「エラトステネスの篩（ふるい）」しかありません。つまり、公式に当てはめて計算でいっぺんに求める方法はなく、1つ1つ確かめなくてはならないのです。これを、能率よくしたものがリュカテストで、大きな素数を見つけるとき、またそれを使って、大きな完全数を見つけるのに威力を発揮します。

双子素数

2つの素数の差が2であるとき、この2つの数は双子素数といいます。一番小さい双子素数は3と5です。
それ以外の双子素数は、6で割って5余る数と1余る数になり、和は6の倍数になります。

以下に400未満の素数の表を示しますので、何かを調べたり確かめたりするときに使いましょう。

400未満の素数の表

2	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53
59	61	67	71	73	79	83	89	97	101	103	107	109	113	127	131
137	139	149	151	157	163	167	173	179	181	191	193	197	199	211	223
227	229	233	239	241	251	257	263	269	271	277	281	283	293	307	311
313	317	331	337	347	349	353	359	367	373	379	383	389	397

エラトステネスは地球の1周の長さを求めた

「エラトステネスの篩」のエラトステネス（紀元前275年 - 紀元前194年）はヘレニズム時代のエジプトで活躍したギリシャ人の学者。図書館長だったので、暦に関するさまざまな重要な記録に接することができました。彼は幾何学と地理学と天文学を融合させ、地球を一周する事なしに、地球1周の長さを計算で求めることに成功しました。

このときのもとになる長さの単位はスタディアといい、1スタディアは、「太陽が地平線から顔を出し、太陽の全身が出るまでに歩ける距離です。つまり、太陽がその直径だけ移動する時間に大人が歩ける距離」という意味でした。

シエネ（現在のアスワン）では夏至の日に太陽光線が井戸の底まで届くこと、つまり南中高度が90°となる（北回帰線上に位置する）ことを聞きました。でも同じ夏至の日、アレクサンドリアでは太陽は頭の真上にはきませんでした。これはいったいどうしてなのでしょう？エラトステネスは地球が丸いことに気づきました。地球が丸いということは知っていましたが、証拠を見つけたという感じでした。そうして、場所によって太陽を見上げる高さが違うということを利用して、地球の大きさが計算できることに気付きました。

アレキサンドリアでは夏至の日の南中高度は82.8°であり、この差がシエネとアレキサンドリアの緯度の差に基づくものとして地球の全周の大きさを求めたのでした。

シエネとアレキサンドリアの距離は5000スタディアであり、比率計算で地球の全周は250000スタディア（46,250 km）と求まった。いずれにせよ、概数ながらも、当時としては驚くほど正確な数値を出していることになります。

エラトステネスの考察で偉大なのは、地球の大きさを測定したその測定値にあるのではなく、地球が球体であることをはっきりと見出したこと、そして、その大きさの測定法を発見したことにあります。

エラトステネスは太陽を利用しましたが、北極星を利用することもできます。同じ経線の2点で太陽（または北極星）を見上げる角度の違いを利用します。今日でも大筋で同じ方法をとっていますから、エラトステネスは超人的な天才であったと言われています。

エラトステネスの篩の表は、受験算数では素数を見つけるのにも使いますが、公倍数を見つけたり、除いたりする場合にも使います。

（2007年 灘中2日目の「2」など）

4. 完全数とメルセンヌ素数について

ある整数がその数の真約数（自分自身は除く約数を真約数ということがあります。）の総和と等しいとき、その数を完全数といいます。

完全数は、6、28、496、・・・・・・など現在（2007年11月現在）までに44個が知られています。
小さい完全数はそれが完全数であることは簡単に確かめられます。

6の約数は 1、2、3、6　で6自身を除いた約数の和

1＋2＋3＝6

28の約数は 1、2、4、7、14、28　で28自身を除いた約数の和

1＋2＋4＋7＋14＝28

496の約数は 1、2、4、8、16、31、62、124、248、496　で496自身を除いた約数の和

1＋2＋4＋8＋16＋31＋62＋124＋248
＝（1＋2＋4＋8＋16）＋31×（1＋2＋4＋8）
＝31＋31×15＝31×16＝496

大きい完全数を求めるために2進法を使った面白い方法があることが知られています。
1ばかり並べた2進数を、メルセンヌ数といいます。

11、111、1111、11111、111111、1111111、・・・・・・

これらを、十進数に直せば、次のようになります。2進数には右下に小さく（2）と添えています。

11_（2）＝100_（2）－1_（2）＝2²－1
111_（2）＝1000_（2）－1_（2）＝2³－1
1111_（2）＝10000_（2）－1_（2）＝2⁴－1
11111_（2）＝100000_（2）－1_（2）＝2⁵－1
111111_（2）＝1000000_（2）－1_（2）＝2⁶－1
1111111_（2）＝10000000_（2）－1_（2）＝2⁷－1

メルセンヌ数M_nは、一般に、M_n＝2ⁿ－1 の形で表されます。
10進数の計算で、9999＝10000－1というのがありますが、2進数では、似たように 11111_（2）＝100000_（2）－1_（2）となり、これを10進数になおすと2⁵－1となります。

メルセンヌ数には、素数であるものと、そうでないものがあります。素数のメルセンヌ数をメルセンヌ素数と言います。nが合成数のとき、明らかにM_nは素数になりません。たとえば、n＝10のとき、次のように、

1111111111_（2）＝11111000000_（2）＋11111_（2）＝11111_（2）×100001_（2）

などと書けるので、合成数とわかります。M_n＝2ⁿ－1という形で表せる数のうち、nが合成数のものは除いて考えればよいということで大幅にラクになるのです。

この方法はリュカが発見しリュカテスト（リュカの素数判定法）といいます。

なお、リュカのスペルはLucasでフランスではリュカと読みますが、英語読みなどが輸入され、ルカ、ルカス、ルーカスなどと書いてある書物もあります。本稿では、一貫して、リュカと書くことにしていますが、他の本などを読むときには注意してください。リュカテストは正式には次のように書きます。

このあたりは、小中学生にはちょっときついので、先を急ぐと、リュカは15歳のときから考え始めて、19年かけて1842年（34才のとき）小さい方から12番目の完全数を見つけました。
それ以前では、1772年にオイラーが8番目の完全数を見つけてから、100年たっています。
人間の手計算では空前絶後の記録です。

発見されているメルセンヌ素数と対応する完全数の表

No.	p	Mpの桁数	完全数 2p-1Mp	年	発見者
1	2	1	6	ancient	-
2	3	1	28	ancient	-
3	5	2	496	ancient	-
4	7	3	8128	ancient	-
5	13	4	33550336	1456年	不明
6	17	6	216M17	1588年	カタルディ
7	19	6	218M19	1588年	カタルディ
8	31	10	230M31	1772年	レオンハルト・オイラー
9	61	19	260M61	1883年	ぺボジーネ
10	89	27	288M89	1911年	パワーズ
11	107	33	2106M107	1914年	パワーズ
12	127	39	2126M127	1876年	リュカ
13	521	157	2520M521	1952年	ロビンソン

（この表はウィキペディアの表の一部を抜粋して引用しています。）

なお、リュカはケガを悪化させて49歳でなくなりましたので、人生の多くを完全数に費やしたことになります。

ユークリッドの完全数
完璧な完全数の生成公式がユークリッドによって発見されています。つまり、2^p-1（2のp乗-1）が素数ならば、2^p-1×（2^p-1）の形の数は全て完全数であることが証明されています。
しかし、完全数が全てこの形でなければならないかどうかはわかっていません。

（2007年11月現在）

完全数	ユークリッドの公式	Pの値
6	21×（22-1）	2
28	22×（23-1）	3
496	24×（25-1）	5
8128	26×（27-1）	7
33550336	212×（213-1）	13

過剰数・不足数

真約数の和がもとの数と等しいとき、その数を完全数というのに対し、もとの数より大きい数を過剰数、もとの数より小さい数を不足数といいます。

友愛数

2つの数があって、お互いの真約数の和が他の数に等しいとき、この2つの数を友愛数と言います。

婚約数

2つの数があって、お互いの真約数の和が等しいとき、この2つの数を婚約数と言います。婚約数の2つの数はこれまで見つかっているものは、一方が奇数で他方が偶数です。

5. 論理問題「天国と地獄」　（2004年 浅野中）

さて、『ハノイの塔』はリュカの発明で、その挿話もリュカの作り話であることが知られていますので、それを参考に『進学レーダー』では、はじめ、しっちゃかめっちゃかの笑い話に書いたのですが、残念ながら、紙面の都合で縮めているうちにあのようなおとなしい文章になってしまいました。残念半分ですが、少しほっとしています。これでもなお、生真面目なお方からは「何ですかこれは」などとお叱りを受けるでしょうか。なんとなく心を騒がせるような文章の方がおもしろいと思うのですが、まあいろんな方がおられますので折り合いをつけています。『進学レーダー』の文中の前半は有名な論理問題「天国と地獄」で、2004年浅野中の次の問題をアレンジしました。

なお、浅野中の問題では、上記のように、「あなたは、『右の道が天国に行く道ですか』ときかれたら『はい』と答えますか？」とするのがよいということになっています。地獄にいる者と天国にいる者と比べて否定をそのまた否定するので、正しい結論が得られるという意味で間違ってはいませんが、なんとも、わざとらしいというか2つの質問を2つなぎにしたようなすっきりしない印象になりますが、ここは『進学レーダー』に書いたように、「あなたが普段いるのはこちらですか。」というのが単純な質問の形になっていてよいように思います。ただし、どちらもよく知られている聞き方です。

原作者の野崎昭弘氏は、1936年神奈川県生まれ。1959年東京大学理学部数学科を卒業。1961年東京大学大学院理学研究科修士課程を修了。現在サイバー大学IT総合学部教授。理学博士。専門は情報数学。

『詭弁論理学（野崎昭弘　中公新書／1976年）』は氏が山梨大学工学部教授のころの著で、このころから数学関係の一般向け解説書を何冊も書いています。特にこの本は、1976年に初版が出て以来のロングセラーになっています。最近は、故遠山啓先生の残された数学教育協議会の委員長として活躍なさっておられるかたわら、低年齢層向けの著作もなさっておられます。

中学入試に出た『詭弁論理学』をはじめ、『πの話』と『赤いぼうし』などがよく読まれたことなどで、2007年度の日本数学会出版賞を受賞なさいました。
サイバー大学は2007年4月に開学した私立大学で学長はエジプトの研究で知られる吉村作治氏です。

6. 「ハノイの塔（とう）」　（1989年 東京女学館中）

さて、『ハノイの塔』は昔、灘中に出たあと、しばらく出なかったのですが、1989年東京女学館中に出ました。
桜蔭中やフェリス女学院中や関西の女子中は以前から結構難しかったものの、他の女子中は概してやさしかったころなので、「おっ！」という意外な感じがしたものでした。

最近の女子中での難問は全然珍しくなくなりましたが。「ハノイの塔」は最近では、2003年名古屋女子大中、2005年高輪中、2006年安田学園中3回、など毎年1題位が出ています。出題率は低いのですが、いざ出ると、初見では時間がかかるので、3個から5個くらいまでの「ハノイの塔」について自分で実際に遊んで確かめておきたいものです。

【解法の指針】

もっと詳しく図解すると、

• （1） 円板1、2、3をBに持って行くには、まず、円板3をBに持っていかなければならない。そのために、図3のように円板1、2をCに積み上げなくてはならない。
  円板1、2をCに持って行くには、まず、円板2をCに持っていかなければならない。そのために、図1のように円板1をBに積み上げなくてはならない。
  図1、2、3のあと、図4で、3をBに持ってくることができた。次に図4の状態のあと、円板1、2をBに持って行くには、図5のようにまず、円板1をAに持っていかなければならない。そのために、図3のように円板1、2をCに積み上げなくてはならない。
  円板1、2をCに持って行くには、まず、円板2をCに持っていかなければならない。そのために、図1のように円板1をBに積み上げなくてはならない。
  図1、2、3のあと、図4で、円板1をAに移し、図6のように、円板2をBに移せばよい。

• （2） 円板1、2、3をBに持ってくるには（1）のように7回の手順が必要であった。この仕方を練習して、円板1、2、3を、Bにでも、Cにでも思い通りに積み上げることを練習しておきましょう。
  円板1、2、3、4をBに持って行くには、まず、円板4をBに持っていかなければならない。そのために、図8のように円板1、2、3をCに積み上げなくてはならない。7回の手順で円板1、2、3をCに移す。次に、図9のように円板4をBに移し、最後にまた7回の手順で1、2、3を図10のようにBに移せばよい。

　

さて、「ハノイの塔」はこうしたことを押さえておけば、たいていの問題が解けます。
ところで、メルセンヌ数M_nは、一般に、M_n＝2ⁿ－1の形で表されます。ハノイの塔の答えもメルセンヌ数になります。このあたりさすがはリュカですね。

また、「数学遊戯」の類は、「ハノイの塔」のほかに、「ナイトの旅（桂馬とび）」とか「鴛鴦（えんおう）の遊び」とか、「車両の並べ替え」、あるいは、スライディングゲーム（「15ゲーム」や「箱入り娘」や「倉庫番」など）のようなものなどたくさんありますが、またの機会があれば論じたいと思います。

7. 素数　（2006年 京都大学前期理系数学）

すでに、知っていると思いますが、n²というのは、nの平方つまり、n×nのことです。

今回は、「ハノイの塔」と、その作者リュカについてでした。日本は実は世界でも珍しいほど翻訳物が多い国なのだそうです。しかし、リュカについて書いたものは少ないように思います。リュカについてあまり知らない人が多いようなので少し書いてみました。