今回のコラムでは，これまで取り上げたコラムの中からパズル的な要素を含む問題について数学的な注釈を添えて収録した．たとえば，魔方陣のパズルを２題掲げてあるが，魔方陣とはｎ^2個の整数を正方形に配列し，行和，列和，（対角線和）が等しくなるように並べたものである．
魔方陣の歴史は古く，中国では洛書と呼ばれ紀元前に知られていたようであるし，日本では江戸時代に関孝和をはじめ和算家が研究している．よく知られたパズルであるから誰しも試行錯誤したことがあるに違いない．
魔方陣は数学愛好家の興味をそそる単なるパズルだと思われがちだが，４次の魔方陣は有限射影平面と関係している．数論ではよくあるようにこの上なく単純な問題でもその奥には複雑な数学が広がっているのである．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【Ｑ１】球面上の２色問題
球面のちょうど５０％を黒塗りする問題を考えます．赤道が与えられているならば北半球か南半球を黒く塗りつぶせばよいのですが，そのような塗り方ではなく，赤道の周りに幅２ωの帯を設けて，ここに表面積の５０％が含まれるようなωを求めてみてください．すなわち
Ｐ｛ｘ＜Ｓ2：−ω≦ｘ≦ω｝＝Ｐ｛ｘ＜Ｓ2：ｘ^2≦ω^2｝＝０．５
ただし，赤道や両極，緯線は与えられているものとします．
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
【Ａ１】ｎ＝３の場合，Ｓ2は４π（表面積）ですが，y=f(x)>0のグラフをｘ軸を中心に回転させてできる曲面の面積は
S[y]=2π∫y(1+(y')^2)^1/2dx
で与えられますから，y=(1-x^2)^(1/2)とおくと
S[y]=2π∫(0,x)dx=2πx=0.5/2･4π
よりω＝０．５と求められます．
ｓｉｎθ＝０．５
は緯度３０°に相当しますから，表面積の５０％となるためには北緯３０°〜南緯３０°の範囲を塗りつぶせばよいことがわかります．なお，Ｓ1は２π（円周）ですから，円周の５０％となるためには
ω＝ｓｉｎ(0.5/4･2π)＝ｓｉｎ４５°＝１／√２
より北緯４５°〜南緯４５°の範囲を黒く塗りつぶします．
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
この問題は高次元球面に一般化することができます．ｎ＞３は簡単には求められませんが，x=(x1,x2,･･･,xn)を単位球面Ｓn-1上で一様分布する点とすると，xn^2の分布はベータ分布Beta(1/2,(n-1)/2)となります．→［参］高次元のパラドックスとスターリングの公式（その３）
ベータ分布は不完全ベータ関数と密接に関係していて，その分布関数はガウスの超幾何関数2Ｆ1を使って以下のように表現されます．
Ｆ（ｘ）＝１／ｐｘ^p2Ｆ1(p,1-q,p+1,x)／Β（ｐ，ｑ）
＝１／ｐｘ^p（１−ｘ）^q2Ｆ1(p+q,1,p+1,x)／Β（ｐ，ｑ）
この式からわかるようにベータ分布は区間（０，１）で定義された分布で，（０，１）に制限されているため，ニュートン法などの反復解法を用いてパーセント点を求めるには不向きです．そこで，区間（０，∞）で定義されたＦ分布の上側確率との間には
Ｑ（df1,df2,F)＝Ｉx（df2/2,df1/2,x)，ｘ＝df2/(df2+df1*F)
Ｉx(p,q)＝∫(0,x)t^(p-1)(1-t)^(1-q)dt/B(p,q)
の関係のあることを使って，Ｆ分布に関する計算をしてからベータ分布関数に変換する方法でベータ分布のパーセント点を求めることにします．また，その方が初期値を求めるうえでもを便利です．
ｎ ω
2 .707107
3 .5
4 .403973
5 .347296
6 .309073
7 .281128
8 .259573
9 .242303
10 .228067
20 .155824
30 .12583
40 .108378
50 .0966214
60 .0880126
70 .0813585
80 .0760163
90 .0716048
100 .0678818
この計算が示していることは，（直観に反して）大きいｎに対してはＳn-1のほとんどが赤道のかなり近くに位置しているというものです．ｎが大きいときωのオーダーはｎ^(-1/2)になります．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【Ｑ２】ミツウロコの問題（三角形はいくつある？）
口の字には四角形が１個ありますが，田の字には小さい四角形が４個と大きい四角形が１個で，合計５個の四角形があります．さらに，囲の字には小さい四角形が９個，中位の四角形が４個，大きい四角形が１個で，合計１４個の四角形があります．
次数 １ ２ ３ ４ ５
□ □□ □□□ □□□□ □□□□□
□□ □□□ □□□□ □□□□□
□□□ □□□□ □□□□□
□□□□ □□□□□
□□□□□
さらに次数を増やすと，四角形の合計は
１→５→１４→３０→５５→・・・
と増えていくのですが，この数列が
１^2＋２^2＋３^2＋・・・＋ｎ^2＝１／６ｎ（ｎ＋１）（２ｎ＋１）
で表されることは容易に理解されるでしょう．
ところで，息子・耕太郎（当時，小学１年生）の宿題に，ミツウロコ文様
△
△▽△
が描かれていて，すべての三角形（下向きの三角形も含む）を数えると何個あるかという問題をみつけました．息子はミツウロコのことをトライフォースと呼んでおりました．４つの三角形という意味だと思われますが，多分，アニメ（漫画？）ではそう呼ばれていたのでしょう．ちなみに，息子の答えは，大きな三角形を数えもらしていたため，４個となっておりましたが，５個が正解です．
（問）△，▽を三角形状に積み上げて次数ｎのミツウロコ文様を作る．三角形はいくつ？
次数 １ ２ ３ ４ ５
△ △ △ △ △
△▽△ △▽△ △▽△ △▽△
△▽△▽△ △▽△▽△ △▽△▽△
△▽△▽△▽△ △▽△▽△▽△
△▽△▽△▽△▽△
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
【Ａ２】基本三角形の個数は
１＋３＋５＋７＋・・・＋（２ｎ−１）＝ｎ^2
ですが，基本三角形を積み重ねてできる大三角形のなかにあるすべての正三角形の総数はという問題ですから，求める数は
１→５→１３→２７→４８→７８→１１８→・・・
と増えていきます．
一般項はどのように表されるのでしょうか？ この問題には難しいことは何一つ出てきませんが，口，田，囲の場合と同じように考えようとするとなかなか一筋縄ではいかない問題であることがわかります．
数え落としや重複など数え間違いのないように整理してから，階差をとるとその理由が見えてくるのですが，
１→５→１３→２７→４８→７８→１１８→・・・
第１階差 ４→８ →１４→２１→３０→４０→・・・
第２階差 ４ →６ →７ →９ →１０→・・・
第３階差 ２ →１ →２ →１ →・・・
第３階差では２と１が交互に繰り返しているので，この数列は１つの多項式で表せず，その答えも交互に２つの式で表されることになります．
この規則性を用いて，ｎ＝８の正三角形の総数を予想すると１７０と求められます．
１→５→１３→２７→４８→７８→１１８→１７０→・・・
第１階差 ４→８ →１４→２１→３０→４０→５２→・・・
第２階差 ４ →６ →７ →９ →１０→１２→・・・
第３階差 ２ →１ →２ →１ →２ →・・・
（答）
ｎが偶数のとき，１／８ｎ（ｎ＋２）（２ｎ＋１）
ｎが奇数のとき，１／８｛ｎ（ｎ＋２）（２ｎ＋１）−１｝
まとめると
１／８［ｎ（ｎ＋２）（２ｎ＋１）＋｛（−１）^n−１｝／２］
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【Ｑ３】デューラーの魔方陣
デューラーは１４７１年に生まれ，１５２８年に没しています．透視図法の発展を促し，有名な版画作品「メランコリアＩ」は彼の透視図法に対する関心の高さを示しています．メランコリー（黒胆汁質）は初めはよくない気質と考えられていたのですが，ルネサンス時代には芸術家的な気質，創造力に繋がるものとされていたようです．
この版画には幾何学や建築に関係のあるいろいろな品物が描かれています．切頂菱面体（デューラーの八面体）はこの版画の中にある品物のひとつですが，その他に，４次の魔方陣
［１６，０３，０２，１３］
［０５，１１，１０，０８］
［０９，０６，０７，１２］
［０４，１５，１４，０１］
も描かれています．まさにメランコリーの寓意がこれらの品物に託されているというわけです．
ところで，この魔方陣の下の行の真ん中の２つは１５と１４になっていて，これが製作年の１５１４年を表していることはよく知られています．４次の魔方陣は一意ではなく，たとえば，
［１２，１３，０１，０８］
［０６，０３，１５，１０］
［０７，０２，１４，１１］
［０９，１６，０４，０５］
なども考えられます．
（問）１次の魔方陣はただひとつの升目に数字１を含む．２次の魔方陣は不可能である．３次の魔方陣はいくつかの並べ方が可能であるが，
［８，３，４］
［１，５，９］
［６，７，２］
のように本質的には中央の升目に５，４隅に偶数が配置されたものただひとつしかない．さて，４次の魔方陣を作るためのアルゴリズムを定めよ．
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
【Ａ３】ｎ次の魔方陣，すなわち，１からｎ^2までの数を配置した魔方陣の定和は
ｎ（ｎ^2＋１）／２
である．定和を手がかりにして，たとえば１から２５までの数を５×５個の升目に書き込み，縦の列も横の列も対角線も足した数がすべて同じになるようにするだけなら，誰でも試行錯誤すれば解くことができる．しかし，升目の数が多くなると試行錯誤では時間がかかりすぎる．
数学者に限らず数学愛好家ならば，升目の数がどんなに増えてもこうすればすべての升目を埋めることができるという一般的方法とその根拠となる法則を見いだそうとするに違いない．
［参］内田伏一「魔方陣にみる数のしくみ」日本評論社
にしたがって，奇数次魔方陣の一般的な作り方を示すと
(1)たとえば，中央升の真下に１を置く
(2)右斜め下の升に順に数を配置していく
(3)枠外に飛び出す場合は平行移動した升に数を配置する
(4)既に数が配置されている場合は，その升の左斜め下に次の数を配置する
［１１，２４， ７，２０， ３］
［ ４，１２，２５， ８，１６］
［１７， ５，１３，２１， ９］
［１０，１８， １，１４，２２］
［２３， ６，１９， ２，１５］
はこのようにして作った５次の魔方陣である．奇数次の魔方陣についてはこの方法で必ず魔方陣を作ることができる．
どの升目に１をおくことによっても始めることができるが，これからできる魔方陣は行和と列和が等しくなるが，対角線和は等しくはならない．最上部の中央の升目に１をおいて，斜め右上に進むと対角線和も等しくなる．
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
（答）４次の魔方陣の場合，作り方はまったく異なっていて
(1)１〜１６までを順に並べる
(2)４隅と中央の４升を動かさず，他の数を中心に対して対称の位置にある升目に移動させる
［ １， ２， ３， ４］ ［ １，１５，１４， ４］
［ ５， ６， ７， ８］ → ［１２， ６， ７， ９］
［ ９，１０，１１，１２］ ［ ８，１０，１１， ５］
［１３，１４，１５，１６］ ［１３， ３， ２，１６］
あるいは（同じことであるが）
(1)まず，２本の対角線を引く
(2)対角線の通る升目を残して，左上隅から数を順番に書き入れていく
(3)右下隅から順番に対角線の通る升目に数を書き入れていく
［××， ２， ３，××］ ［１６， ２， ３，１３］
［ ５，××，××， ８］ → ［ ５，１１，１０， ８］
［ ９，××，××，１２］ ［ ９， ７， ６，１２］
［××，１４，１５，××］ ［ ４，１４，１５， １］
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
偶数次の魔方陣の作り方としては，４の倍数の場合（４ｋ：複偶数）と４で割り切れない場合（４ｋ＋２：単偶数）に分けられるのだが，一般的な４ｋ次の魔方陣の作り方は
(1)１から１６ｋ^2までの数を順に並べる
(2)４ｋ×４ｋの表を縦横に４等分し，１６個のｋ×ｋの表に分割する
(3)この１６個の小方陣について，４次の魔方陣を作ったときと同じ操作を加える
［ １， ２，６２，６１，６０，５９， ７， ８］
［ ９，１０，５４，５３，５２，５１，１５，１６］
［４８，４７，１９，２０，２１，２２，４２，４１］
［４０，３９，２７，２８，２９，３０，３４，３３］
［３２，３１，３５，３６，３７，３８，２６，２５］
［２４，２３，４３，４４，４５，４６，１８，１７］
［４９，５０，１４，１３，１２，１１，５５，５６］
［５７，５８， ６， ５， ４， ３，６３，６４］
はこのようにして作った８次魔方陣の例である．
また，オイラーの考案した８次魔方陣は，左上隅の１から出発して桂馬飛びですべての数をたどることができるという奇抜なものである．
［ １，４８，３１，５０，３３，１６，６３，１８］
［３０，５１，４６， ３，６２，１９，１４，３５］
［４７， ２，４９，３２，１５，３４，１７，６４］
［５２，２９， ４，４５，２０，６１，３６，１３］
［ ５，４４，２５，５６， ９，４０，２１，６０］
［２８，５３， ８，４１，２４，５７，１２，３７］
［４３， ６，５５，２６，３９，１０，５９，２２］
［５４，２７，４２， ７，５８，２３，３８，１１］
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
４ｋ＋２次の魔方陣は，４ｋ次の魔方陣を作ってからその周りを作るのであるが，たとえば６次の魔方陣の場合，
(1)１から３６までの数の中から中央にある１１から２６までを使って４次の魔方陣（すなわち，先に作った４次の魔方陣の各成分に１０加えたもの）を作る
(2)その外周に，上辺，下辺，左辺，右辺の６数の和が１１１となり，４隅に関しては中心に関して点対称の位置にある２数の和が３７，上下または左右に向き合った２数の和が３７となるように数を配置する
［ ５，２８，３６，３５， ３， ４］
［３１，１１，２５，２４，１４， ６］
［ ７，２２，１６，１７，１９，３０］
［ ８，１８，２０，２１，１５，２９］
［２７，２３，１３，１２，２６，１０］
［３３， ９， １， ２，３４，３２］
これを一般化すると，ｎ＝４ｋ＋２の場合
(1)１〜ｎ^2＝（４ｋ＋２）^2までの数の中から中央にある２ｎ−１＝８ｋ＋３からｎ^2−２ｎ＋２＝１６ｋ^2＋８ｋ＋２までを使って４ｋ次の魔方陣を作る
(2)その外周に，上辺，下辺，左辺，右辺の６数の和がｎ（ｎ^2＋１）／２となり，４隅に関しては中心に関して点対称の位置にある２数の和がｎ^2＋１，上下または左右に向き合った２数の和がｎ^2＋１となるように数を配置する
この作り方は１６８３年，和算家の関孝和が発表したものとのことであり，
［参］内田伏一「魔方陣にみる数のしくみ」日本評論社
にはｋ＝１，２，３すなわちｎ＝６次，１０次，１４次の魔方陣が紹介されている．
ちなみに，合同変換に対して移り合うものを同じものとみなすと３次の魔方陣は１個，４次の魔方陣は８８０個，５次の魔方陣は約２．７５×１０^8個，６次の魔方陣は約１．７７×１０^19個あることが知られている．それにしてもこんなに多くの組合せ方があるとは驚きである．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【Ｑ４】オイラーの３６人の士官問題（グレコ・ラテン方陣の存在・非存在）
魔方陣に関連してもう１題．１７７９年，オイラーは行列の性質を研究するために３６人の士官問題を考案した．ｎ行ｎ列の正方形の升目に文字を配列し，各行各列に文字の重複がないものをｎ次ラテン方陣という．
［ａ，ｂ，ｃ］ ［ａ，ｂ，ｃ］
［ｂ，ｃ，ａ］ ［ｃ，ａ，ｂ］
［ｃ，ａ，ｂ］ ［ｂ，ｃ，ａ］
は３次のラテン方陣であるが，縦も横も同じ文字が重複なく１回ずつしかでてこない．ラテン方陣を作るには，最初の行をａ，ｂ，ｃとして一行下がるごとに左に（あるいは右に）ひとつずつ巡回置換させればよい．
ラテン方陣では属性はひとつであったが，次に属性を１つ増やして２つの属性を有する対象を升目状に並べた配列を考える．同じ組が現れずすべて異なる配列が「グレコ・ラテン方陣」である．グレコ・ラテン方陣はオイラーにちなんで「オイラー方陣」とも呼ばれる．
［ａ，ｂ，ｃ］ ［α，β，γ］ ［ａα，ｂβ，ｃγ］
［ｂ，ｃ，ａ］＋［γ，α，β］＝［ｂγ，ｃα，ａβ］
［ｃ，ａ，ｂ］ ［β，γ，α］ ［ｃβ，ａγ，ｂα］
は３次の左巡回ラテン方陣と右巡回ラテン方陣を組み合わせて，グレコ・ラテン方陣にしたものである．このように，合併してグレコ・ラテン方陣になる２つのラテン方陣を（比喩的に）直交するという．
［１，２，３］ ［１，２，３］ ［１１，２２，３３］
［３，１，２］＋［２，３，１］＝［３２，１３，２１］
［２，３，１］ ［３，１，２］ ［２３，３１，１２］
は３次のラテン方陣を組み合わせて，グレコ・ラテン方陣にしたものである．
（問）すべてのｎに対してグレコ・ラテン方陣は存在するのか？ また，そうでないとしたらどのようなｎに対してグレコ・ラテン方陣は存在するのだろうか？
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【Ａ４】答えを先にいうと，グレコ・ラテン方陣はｎが奇数のときと４の倍数のときに可能である．１７８２年，オイラーはｎが２の奇数倍のときグレコ・ラテン方陣は不可能と予想したのだが，この予想は誤りであって，ｎ＝２と６の場合だけが不可能なのである．詳しく見ていくことにしよう．
ｐ次のグレコ・ラテン方陣とｑ次のグレコ・ラテン方陣があれば，ｐ×ｑ次のグレコ・ラテン方陣を作ることができます．また，グレコ・ラテン方陣はｎが奇数のときと４の倍数のときに可能であることがわかっていて，
ｎ＝２^q×ｌ，ｌは奇数，ｑ≧２
とすると，ｌは奇数ですからｌ次のグレコ・ラテン方陣は存在します．２^q個の元からなる体は存在し，したがって，２^q次のアフィン平面も存在するので，２^q次のグレコ・ラテン方陣は存在しますから，２^q×ｌ次のグレコ・ラテン方陣も可能であることがわかります．
結局，ｑ＝１の場合，すなわち，
ｎ＝２×ｌ＝２（２ｋ＋１）＝４ｋ＋２
の場合だけが残ります．
１７８２年，オイラーはｎ＝４ｋ＋２（２の奇数倍）のときグレコ・ラテン方陣は不可能と予想し，そして１９０３年にタリーがｋ＝１すなわちｎ＝６の場合があることをしらみつぶしの方法によって証明しました．
その後，１９５９年になって，ボーズ，シュリカンデ，パーカーによって，ｎが２２や１４のときに可能なことがわかると，せきをきったように一般的な作り方がわかっていき，最も困難だったｎ＝１８の場合も攻略され，１年ほどでｎ≧１０であるｎ＝４ｋ＋２という形の数すべてについて，互いに直交するラテン方陣が存在することが判明しました．１７７年にわたる難問の解決は当時の世界に大きな衝撃を与え，New York Timesのトップ記事として報道されたのですが，数学に関する取り扱いとしては空前絶後のものでした．
たとえば，１０次のグレコ・ラテン方陣
［００，４７，１８，７６，２９，９３，８５，３４，６１，５２］
［８６，１１，５７，２８，７０，３９，９４，４５，０２，６３］
［９５，８０，２２，６７，３８，７１，４９，５６，１３，０４］
［５９，９６，８１，３３，０７，４８，７２，６０，２４，１５］
［７３，６９，９０，８２，４４，１７，５８，０１，３５，２６］
［６８，７４，０９，９１，８３，５５，２７，１２，４６，３０］
［３７，０８，７５，１９，９２，８４，６６，２３，５０，４１］
［１４，２５，３６，４０，５１，６２，０２，７７，８８，９９］
［２１，３２，４３，５４，６５，０６，１０，８９，９７，７８］
［４２，５３，６４，０５，１６，２０，３１，９８，７９，８７］
では，１≦（ｉ，ｊ）≦７の場合と８≦（ｉ，ｊ）≦１０の場合で作り方が違っていて，１０＝３＋７＝３＋（１＋２×３）と分解することによって，２個の直交するラテン方陣を作り出しています．
こうして，オイラーの予想は覆され，ｎ＝２と６の場合だけグレコ・ラテン方陣が不可能であることが判明したのでした．
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
６次の魔方陣は存在し，
［００，０１，０２，３３，３４，３５］
［３０，３１，１４，０３，２２，０５］
［２９，２８，２７，０８，０７，０６］
［１１，１０，０９，２６，２５，２４］
［２３，１９，２１，２０，０４，１８］
［１２，１６，３２，１５，１３，１７］
は和算家・久留島義太の手作りとされるものである．
この６進数版は
［００，０１，０２，５３，５４，５５］
［５０，５１，２２，０３，３４，０５］
［４５，４４，４３，１２，１１，１０］
［１５，１４，１３，４２，４１，４０］
［３５，３１，３３，３２，０４，３０］
［２０，２４，５４，２３，２１，２５］
であるが，グレコ・ラテン方陣にならないことはすぐにみてとれる．
このように，６次のラテン方陣は存在するのに対して，６次のグレコ・ラテン方陣は不可能であることが証明されている．その証明はタリー（１９０３年）によってなされたが，全数を列挙して調べつくすというものであった．
端的にいって「あらゆる可能性を調べて不可能であることを示す」のはとても厄介な話である．「やってみてできなかった」という証明は組織的に完全に実行すれば立派な証明になるのであるが，オイラーの士官３６人の問題は実際にそういう証明しかない数学の問題となっている．いまだ一般的・理論的な証明はなく，不可能性の証明は根気のいるしらみつぶしによる方法しかないのである．奇妙なことに，３つの属性についての３次元オイラー立方体は可能なことがわかっている（１９７７年）．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【Ｑ５】リュカの「ハノイの塔」
１９世紀の数学者リュカの考案したゲームに「ハノイの塔」があります．ハノイの塔とは３本の柱Ａ，Ｂ，Ｃがあり，柱Ａにある何枚かの円盤を１枚ずつ柱Ｂを中継点にして柱Ｃに移動させるものです．ただし，どの柱でも上の円盤の方が小さくなければなりません．
（問）６４枚の円盤があるとき，移し替えが完了するには何回移動しなければならないのか？
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
【Ａ５】円盤が３枚であるとします．Ａにある３枚をＢに移すにはＣを中継点にしてＢに移動させる．このためには上の２枚をＣに移し，３枚目をＢにもってきた後，Ｃの２枚をＢに移動させる．次に円盤が４枚であるとします．上の三枚がくっついているとして，この３枚をＢに移し，一番下の円盤をＣにもってきて，Ｂの３枚をＣに移せばよい．
このような再帰的な方法を用いれば円盤が何枚あってもＡからＣに移動させることができるのですが，ｎ枚の円盤を移動させるのに必要な最小回数をａnと書くことにすれば，漸化式
ａn＝２ａn-1＋１
で表せることがわかります．いま述べたｎ−１枚がくっついているとして・・・という考え方を小学５年生の息子に説明したところ，彼にも意味が理解できた様子でありました．
ａnの具体的な値は
ａn＋１＝２（ａn-1＋１）
ａn-1＋１＝２（ａn-2＋１）
・・・・・・・・・・・・・
ａ2＋１＝２（ａ1＋１）
より，容易に
ａn＝２^n−１
で与えられることがわかりますが，こうして円盤が３枚のとき→４枚のとき→ｎ枚のときに一般化することができます．（形は似ていますが，柱が３本のとき→４本のとき→ｎ本のときに一般化するのはもっと難しい問題になります．）
（答）６４枚の円盤があるとき，２^64−１回の移動をしなければならない．１秒に１回移動をさせるにしても完了までには５８２０億年かかることになる．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【補】リュカとフィボナッチ数列
初項１，第２項１から始まり，隣り合う２項の和が次の項となる数列
１，１，２，３，５，８，・・・
をフィボナッチ数列とよびます．その一般項Ｆn は
Ｆn＝Ｆn-1＋Ｆn-2
です．この数列にフィボナッチ（１３世紀のイタリアの数学者でピサのレオナルドとしても知られる）の名を冠したのはフランスの数学者リュカで，ハノイの塔の名で知られる２進法のパズルも１８８３年にリュカによって考案されたものです．
初項２，第２項１のフィボナッチ数列
２，１，３，４，７，１１，１８，・・・
は彼にちなんでリュカ数列と呼ばれています（１８７７年）．
Ｌn＝Ｌn-1＋Ｌn-2
リュカはフィボナッチ数列，リュカ数列を用いてメルセンヌ数（２^n−１）が素数であるかどうかを判定し，（２^127−１）が素数であることを示しています（１８７６年）．この数は１２番目のメルセンヌ素数で，１９５２年の１３番目（２^521−１）からはコンピュータによる発見ですから，コンピュータを使わずに見つけられた最大のメルセンヌ素数になっていて，わかっている最大の素数として最長不倒記録を保ち続けました．
フィボナッチ数列やリュカ数列の一般項は，３項漸化式：
Ｆn＝Ｆn-1＋Ｆn-2
Ｌn＝Ｌn-1＋Ｌn-2
の特性方程式
ｘ^2−ｘ−１＝０
の２つの解より，連続する２項の比は黄金比
φ＝（１＋√５）／２＝１．６１８０３４・・・
に次第に近づくことになります．
黄金長方形から正方形を取り除くと一回り小さな黄金長方形が現れてきます．このことを繰り返し行えば対数らせんが現れますが，この曲線は自然界ではオーム貝などの形にみられ，自己相似的な成長過程を表す理想的な曲線とされています．サイクロイドの伸開線はそれと合同なサイクロイドですが，対数らせんの伸開線もそれと合同な対数らせんになります．
今度は逆に１辺の長さがフィボナッチ数列の正方形をらせん状に加えていきます．最初の２つの正方形は１辺の長さが１で，そこに１辺の長さが２の正方形，引き続いて１辺の長さが３，５，８，１３，２１，・・・．すると，優美な対数らせんが現れてきますが，このらせんはほぼ黄金比で外に広がることになります．
さらに，１つの項の和がその前の３つの項の和になっている
Ｔn＝Ｔn-1＋Ｔn-2＋Ｔn-3
で定義される数列
１，１，１，３，５，９，１７，・・・
は，フィボナッチ数列の拡張とみなせるので，フィボナッチ（Fibonacci）をもじってトリボナッチ（Tribonacci）数列と呼ばれます．
トリボナッチ数列でも連続する２項の比はある決まった値
１／３｛3√（１９＋３√３３）＋3√（１９−３√３３）＋１｝＝１．８３９・・・
に収束します．これは
ｘ^3−ｘ^2−ｘ−１＝０
の実根です．
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
フィボナッチ数列では正方形をらせん状に並べましたが，次に正三角形をらせん状に並べてみましょう．最初の３つの正三角形は１辺の長さを１，次の２つは１辺の長さが２で，そのあとは３，４，５，７，９，１２，１６，２１，・・・．このようにしてもおおよそ対数らせんを描きます．
数列
１，１，１，２，２，３，４，５，７，９，１２，１６，２１，・・・
は直前の１項を除いたその前の２項を加えたものです．パドヴァンの数列と呼ぶことにしますが，漸化式は
Ｐn＝Ｐn-2＋Ｐn-3 （Ｐ0＝Ｐ1＝Ｐ2＝１）
で表されます．
その特性方程式
ｘ^3−ｘ−１＝０
の唯一の実数解より，パドヴァン数列の連続する２項の比は
ｐ＝１／３｛3√（２７／２−３√６９／２）＋3√（１／２＋√６９／１８）｝＝１．３２４７１８・・・
に次第に近づくことになります．ｐがφよりも小さいことより，パドヴァン数列はフィボナッチ数列に較べてゆっくりと増加することになります．
ｐ^5−ｐ^3−ｐ^2＝０
ｐ^4−ｐ^2−ｐ^1＝０
より
ｐ^5−ｐ^4−ｐ^3−ｐ^1＝ｐ^5−ｐ^4−１
ですから，３次方程式ｐ^3−ｐ−１＝０の解はこの５次方程式も満たすことがわかります．あるいは，因数分解
ｐ^5−ｐ^4−１＝（ｐ^3−ｐ−１）（ｐ^2−ｐ＋１）
でもよいのですが，このことから
Ｐn＝Ｐn-1＋Ｐn-5
の関係が成り立つこともわかります．
リュカはパドヴァン数列と同じ生成規則に従い，最初の項の値が異なるものを考案しました（１８７６年）．
Ａn＝Ａn-2＋Ａn-3 （Ａ0＝３，Ａ1＝０，Ａ2＝２）
３，０，２，３，２，５，５，７，１０，１２，１７，２２，２９，・・・
この数列は現在ではペラン数列と呼ばれるものです．この数列の項比もｐに近づきますが，さらに深遠な性質「ｎが素数のときＡnはｎで割り切れる」をもっています．しかし，逆命題「Ａnがｎで割り切れるときｎは素数である」は必ずしも成り立たないことが知られています．
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
１^2＋２^2＋３^2＋・・・＋２４^2＝２４（２４＋１）（２・２４＋１）／６＝７０^2
級数の公式：Σｋ^2＝ｎ（ｎ＋１）（２ｎ＋１）／６をご存じの方も多いでしょうが，１からｎまでの平方の和が平方数となるのはｎが１か２４の場合しかありません．
２５平方の等式ともいうべきこの等式はリュカの問題（１８７３年）として知られています．ｙ^2＝ｘ（ｘ＋１）（２ｘ＋１）／６の唯一自明でない整数解は（２４，７０）で，それ以外の自明な解がないことは楕円関数やペル方程式を使って証明されています．
この等式は辺の長さが相続く整数列１，２，・・・，２４の正方形を１辺の長さ７０の正方形の中に詰め込める可能性があることを示唆しています．それでは，実際に，７０×７０の正方形を辺が１から２４の相続く正方形によって埋めつくすことができるでしょうか．この問題の答えは否定的（不可能）です．１辺の長さ７の正方形を除くすべての正方形は詰め込めるのですが・・・．
それならば，無駄な空間の割合を最小にして，辺の長さが１，２，・・・，ｎの正方形を全て詰め込むことができる最小の正方形の辺の長さはいくつでしょうか．また，相続く整数辺の正方形を使って長方形を充填できるでしょうか．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝