初期状態P0から第1手はサークルBかCへ最小の皿を移す。これが状態P1である。3手目に最小の皿を2番目の皿の上に移す。4手目に3番目に小さい皿を空のサークルに移動する事ができる。上の手順のように空のサークルを用意して新しい皿をA塔の1番上から移動するのである。次の定義を設ければ直ちに次の推定ができるであろう。手かかる」この推定はn=0、1、2、3、4程度の実際例で確認される。一般には、上の推定をそのまま仮定とし、次の命題を証明すればよい。他の塔の1番下の皿を残して皿n以上をA塔の上に移す。仮定した手順に準ずるとみなしてよい。次に、皿n+1を皿n+2の上に移すのを第1手としてA塔の皿n以上を皿n+1の上に移す。これも仮定の手順に準ずる。手数の合計は2n+2n=2n+1結論。初期状態から状態Pnを完成するのに要する手数は1+2+22+・・・+2nー1=2n-1従って、64枚の皿の塔を移動させるのに、次の手数を必要とする。264−1手1手1秒で何年かかるか。この世の終わらぬ理由がわかりました。64枚の皿でB塔をつくるためには第1手をサークルCに施さなければなりません。実際例での確認と一般の証明の中に盛り込むことが出来ます。解答・その5(ペンネ−ム:aa)こういうのは数を少なくして実際にやってみよー、が基本ですね。1)黄金の円盤が1枚の場合これは明らかにA->Bの1回2)黄金の円盤が2枚の場合この場合は、A->CA->BC->Bの3回3)黄金の円盤が3枚の場合この場合は、A->BA->CB->CA->BC->AC->BA->Bの7回。4)黄金の円盤が4枚の場合そろそろ何か考えないと、面倒になってくる。下の大きな円盤を動かすためには、その上の3枚をCに移しておく必要がある。3)よりこれには7回掛かる。次に、一番大きな円盤をBに移し(1回)、Cの3枚をBに移すのに7回必要。よって7+1+7=15回5)黄金の円盤が5枚の場合15+1+15=31回6)黄金の円盤が6枚の場合31+1+31=63回ふー、この調子で64まで行けばいいのだが、64は遠い(!)ので、いままでの回数を振り返ってみると、1,3,7,15,63う〜ん、これは2n-1って形じゃん。7)ちなみに黄金の円盤が7枚の場合63+1+63=127・・・おー、まさに27-1だぁ。よって64枚の場合は、264-1回必要。Windowsの関数電卓でこの値を求めると、264-1=18446744073709551615というととてつもなく大きな値。584942417355。5850億年かかるというもの。解答・その6(ペンネ−ム:teki)今月は、超有名な「ハノイの塔」ですか。枚では2n-1手になります。円盤の枚数が1枚のときは、明らかに1手です。1手の合計3手かかります。残った1枚を移すのに1手の合計7手です。いう漸化式が成立します。H(n)+1は初項2、公比2の等比数列ですので、その一般項は、2nです。よって、H(n)=2n-1が成立することになります。かかることになります。(なんと、5800億年以上かかっちゃうんですね。うになれば、あと60年ほどで終わっちゃいますけど・・・。M1は明らかに1である。3本目の大理石の柱に移動しておく必要がある。Mn−1回移動する必要がある。この作業が完了後、最大のN番目の円盤を2本目の大理石の柱に移動するには1回の移し換えが必要。この回数はMn−1であるから、Mn=2Mn−1+1が成立する。この漸化式を解いて、Mn=2n−1となる。解答・その8(ペンネ−ム:Toru)N枚の円盤を移すのにF(N)秒かかるとする。(秒)≒1.8×1019(秒)≒2.1×1014(日)≒5.8×1011(年)とまあ大分先のようでちょっと安心しました。(億年)この5800億年後が,この問題がいうところの「この世の終わり」です。,「この世の終わり」を『地球の終わり』と捉えるなら,それはもっともっと最近(?)です。太陽は現在50億歳,あと50億年で自身の水素エネルギーを消費し尽くし赤色巨星への道を辿ります。「この世の終わり」を『人類の終わり』と捉えるなら......あと200年もつかどうか解答・その10(ペンネ−ム:夜ふかしのつらいおじさん)n枚の円盤をAの柱からCの柱に移すとき、右の図のような段階があります。�@は始めの状態です。�AはAの柱にあった上のn−1枚の円盤をBの柱に移した状態です。�BはAの柱にあった一番下の1枚の円盤をCに移した状態です。�CはAからBに移したn−1枚の円盤をCに移して完成した状態です。f(n)をn枚の円盤を違う柱に移すのに必要な手数とします。f(n−1)の手数がかかります。両辺に1を加えて変形すると、f(n)+1=2{f(n−1)+1}すると、f(n)+1は、初項f(1)+1=2、公比2の等差数列になるので、f(n)+1=2・2nー1=2nf(n)=2n−1ここで、n=64とすると、f(64)=264−1=18446744073709551615となります。(宇宙が出来て今までの時間の約43倍)ともかく気が遠くなるような先にこの世がなくなります。解答・その11(ペンネ−ム:SOU)n枚の移動にかかる最短の手数をf(n)とすると、f(1)=1がわかります。あとは、f(n+1)とf(n)の関係を求め、漸化式に持ち込みます。f(n+1)とf(n)との関係を調べてみます。3つの柱をそれぞれ左、真ん中、右という名前をつけます。右の柱にn+1枚の皿が刺さっていて、真中の柱に移動させることにします。�@まず上からn枚だけ左に動かします。いま、右にはまだ1枚残ってます。�A右にある最後の一個を真中に移動させます。ここでかかる手数は1回です。�B更に左にあるn枚を真中に移動させます。この時かかる手数はさっきと同じf(n)回です。これで、f(n+1)=f(n)+1+f(n)=2f(n)+1という関係があることが分かりました。