福西です。

今回は幾何をお休みして、代わりに、以前小学4年生のかずクラスで問題にした「ブラフマンの塔」(64段のハノイの塔)の問題を出してみました。3年生のA君が率先し、1年生のR君がそれをフォローするという形で、以下のように考えてくれました。それが、今まで私の考えたことのない方法(着眼点)だったので、驚きました。

 

A君の考え 「それぞれの円盤を最初に動かした時は何手目にあたるか? に着目する」

 

円盤

1枚目(一番上) …手目で最初に動かす

2枚目…手目で最初に動かす

3枚目…手目で最初に動かす

4枚目…手目

5枚目…16手目

というように、ちょうど「2の倍数になっている」ことに気付いてくれました。

 

そして、5枚の例だと、5枚目(一番下)の円盤を動かした(16手目)後の手順は、16-1手かければよいので、全部で16×2-1=31手と求まります。

 

つまり、2×2^(n-1)-1=2^n-1です。このように、あっさりと法則を見つけ出してくれました。

 

以前、小学生たちの見抜いた法則は、5枚の円盤の場合は、16+1+16=31という「左右対称」のとらえ方でした。これも結果は2^n-1となり、同じ法則を表していることになります。

 

さて、法則はこのように「つかまえた」のですが、まだそれの計算が残っています。ブラフマンの塔は64段あるので、2^64-1を計算しなくてはなりません。実際にしてみれば分かりますが、それはとても大きな数になります。(そして非常に手間がかかります)

 

ここに、「法則はわかっていても、答がすぐに出てこない」という、実際的な問題が生じます。では、実際、どのようにすれば計算できるのでしょうか。生徒たちは、次のように考えてくれました。

 

step1 32段まではひたすら計算する。

結果:2^32-1=4294967295

 

この結果に至る途中で、「2^n-1の1の位は、1、3、7、5、1、3、7、5・・・を繰り返す」という副産物的な法則も見つけてくれました。素晴らしい知的好奇心の発露です。

 

さて、次です。

step2 2^64=(2^32)^2であることに着目する。

結果:2^64-1=4294967296×4294967296-1

また、1年=31536000秒

 

実際、2^32まで計算し、その次また2倍、2倍…としていくことは、非常に骨が折れます。そこではたとA君が気付いたことには、(2^32)の二乗がちょうど2^64となっている、ということです。ということは、上のように4294967296をもう1回かければ、2^64は求められることになります。

 

これでだいぶ手間は減ったとはいえ、それでも4294967296×4294967296をするのは、大変です。そこで私から一つ、ぜひとも知っておいて欲しい数学的な道具を教えました。「評価」という方法です。

 

step3 不等式で「評価」する。

結果:ブラフマンの塔の並べ替えにかかる年数は、5000億年~6000億年(12桁)である。

 

今、問題に対して、真値(厳密解)は知る必要はありません。つまり、「何年かかるか?」という質問には、1000年、あるいは10000年といった、その桁数(オーダー)を答えられれば十分です。このような場合、

 

a×10^m<真値<b×10^m (ただし1<a<b<10)

 

というように、両側から「不等式で押さえる」ことを考えます。もし上の式のように、「左もm+1桁、右もm+1桁」という「同じ桁の数字」でおさえられたとすれば、真ん中にはさまっている「真値も、m+1桁」と特定することができます。

 

ここで、活躍するのが、小学生のときに習った(あまりその便利さにぴんとこなかった)、切り捨て切り上げです。

以下、生徒たちの計算結果を示します。

 

(下限の計算)

4294967296>4000000000=4×10^9

4294967296×4294967296>16×10^18=1.6×10^19

31536000<32000000=3.2×10^6

1.6×10^19/3.2×10^6=0.5×10^12=5×10^11

(ここで、分母を大きくとると、全体が小さくなることに注意する)

 

(上限の計算)

4294967296<43×10^8

4294967296×4294967296<(43×10^8)×(43×10^8)=1849×10^16<1.85×10^19

31536000>3×10^7

1.85×10^19/3×10^7<6×10^11

 

よって、5×10^11<真値(2^64-1)<6×10^11

 

となり、12桁(5ないし6のうしろに0が11個並ぶ)。すなわち5000億年~6000億年である。

 

以上が、中学生クラスで求めてくれた結果でした。

Share