書記が数学やるだけ#38 ハノイの塔にまつわる大学入試問題

ブレイクタイムとして，ハノイの塔にまつわる大学入試問題を扱っていく。2つの問題を融合し，さらに一つ加えることで幅広い範囲を扱えるようにした。

以下Wikipedia参照。

ハノイの塔は，フランスの数学者エドゥアール・リュカが1883年に発売したゲーム『ハノイの塔』がルーツである。日本では，1907年（明治40年）に書かれた書物『世界遊戯法大全』で紹介されている。

ところで，同梱のリーフレットには次のような伝説があると書かれていた。

インドのガンジス河の畔のヴァラナシ（ベナレス）に、世界の中心を表すという巨大な寺院がある。そこには青銅の板の上に、長さ1キュビット、太さが蜂の体ほどの3本のダイヤモンドの針が立てられている。そのうちの1本には、天地創造のときに神が64枚の純金の円盤を大きい円盤から順に重ねて置いた。これが「ブラフマーの塔」である。司祭たちはそこで、昼夜を通して円盤を別の柱に移し替えている（移し変えのルールの説明は省略）。そして、全ての円盤の移し替えが終わったときに、世界は崩壊し終焉を迎える。

さて，いわゆる世界滅亡について書かれており，なかなかに恐ろしそうだ。しかし，仮にこの手順に従ったとして，いつになったら世界滅亡を迎えるのだろうか。本記事の内容を理解することで分かることである。

問題

(2)までがハノイの塔の最短手順の導出である。nとn+1の関係を見ていくことで一般項を求めていく。

(3)は世界滅亡までどれくらいかかるかの概算になる。

(4)からはとある数が素数であるかについて論じている。

解法

a2とa3は自力で考える。

a4，a5と考えていって気づくことができるか。ここでポイントとなるのは，「まずn段を全て別の棒に移す→n+1段を別の棒に移す→その上にn段を乗せる」といった感じに，漸化式として表現できる点である。

ここで出てきた数列はメルセンヌ数そのものである。

a64について考える。1の位は周期性より，桁数は常用対数をとって求める。

ちなみに，実際の数は「1844京6744兆737億955万1615」であり，もし1枚移動させるのに1秒かかったとすると，最低でも約5845億年かかる計算である。ビックバンから現在よりも遥かに長く，ハノイの塔で世界滅亡について悲観することはないだろう（？）。

さて話題は変わって，本問はメルセンヌ数と素数の関係について。まずは「anが素数なら，nが素数」が真であるか。

次は，その逆である「nが素数なら，anは素数である」が真かどうか。これが真なら大変なことで，素数の規則性が分かるといえる。

実際にはn=11が反例となる（2047が合成数であることは，訓練してないと気づかないかも）。

メルセンヌ数の存在は，ユークリッドの「原論」に示されていたとされる。1644年に，メルセンヌは

「素数 p で 2^p − 1 が素数になるのは、p ≦ 257 では p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 の11個の場合だけである」

という予想を公表した。後にオイラーやリュカなどにより予想の正誤に決着がつき，2^p − 1 のうちの素数がメルセンヌ素数と呼ばれることになる。現代では分散型コンピューティングにより新たなメルセンヌ素数が探索されている。

本記事のもくじはこちら：