アットランダム≒ブリコラージュ

ハノイの塔 (Tower of Hanoi)...^^

画像：http://ja.wikipedia.org/wiki/ハノイの塔 より

「以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。

• 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
• 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
• 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

n枚の円盤すべてを移動させるには 2ⁿ - 1 回の手数がかかる。

由来

ハノイの塔は、フランスの数学者エドゥアール・リュカが1883年に発売したゲーム『ハノイの塔』がルーツである。パッケージには「Li-sou-stian大学勤務のシャム出身のN. Claus教授によりトンキンからもたらされたゲーム」と書かれているが、Li-Sou-Stian大学はリュカが働いていたセントルイス (Saint Louis) 大学のアナグラム、シャム出身のN. Claus (N. Claus de Siam) はアミアン出身のリュカ (Lucas d'Amiens) のアナグラムであるため、すべてはリュカの創作だと思われている。

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

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

パッケージではハノイの塔となっていたが、リーフレットではブラフマーの塔となっていた。ハノイはトンキンの中心都市、ブラフマーはインドの聖職者階級の名である。

この話には多くのヴァリエーションが生まれた。たとえば、ダイヤモンドの針のかわりに大理石の柱が立っているなどである。

64枚の円盤を移動させるには、最低でも（2⁶⁴-1）回 = 18,446,744,073,709,551,615（1844京6744兆737億955万1615）回かかり、1枚移動させるのに1秒かかったとして、約5,845億年かかる（なお、ビッグバンは今から約137億年前の発生とされている）。」

http://www.geocities.jp/ikuro_kotaro/koramu/396_hanoi.htm より Orz〜

「（問）６４枚の円盤があるとき，移し替えが完了するには何回移動しなければならないのか？

　円盤が３枚であるとします．Ａにある３枚をＢに移すにはＣを中継点にしてＢに移動させる．このためには上の２枚をＣに移し，３枚目をＢにもってきた後，Ｃの２枚をＢに移動させる．次に円盤が４枚であるとします．上の三枚がくっついているとして，この３枚をＢに移し，一番下の円盤をＣにもってきて，Ｂの３枚をＣに移せばよい．

　このような再帰的な方法を用いれば円盤が何枚あってもＡからＣに移動させることができるのですが，ｎ枚の円盤を移動させるのに必要な最小回数をａ(n)と書くことにすれば，漸化式

　　ａ(n)＝２ａ(n-1)＋１

で表せることがわかります．いま述べたｎ−１枚がくっついているとして・・・という考え方を小学５年生の息子に説明したところ，彼にも意味が理解できた様子でありました．

　ａ(n)の具体的な値は

　　ａ(n)＋１＝２（ａ(n-1)＋１）

　　ａ(n-1)＋１＝２（ａ(n-2)＋１）

　　・・・・・・・・・・・・・

　　ａ(2)＋１＝２（ａ(1)＋１）

より，容易に

　　ａ(n)＝２^n−１

で与えられることがわかりますが，こうして円盤が３枚のとき→４枚のとき→ｎ枚のときに一般化することができます．

（答）６４枚の円盤があるとき，２^64−１回の移動をしなければならない．１秒に１回移動をさせるにしても完了までには５８２０億年かかることになる．

・・・」

すぐにピンと来なかったわたしはさらにサーチ ^^;

画像：http://www.ngm.ed.ynu.ac.jp/negami/dai3nori/sect2.html より Orz〜

「まず， n 段のハノイの塔の手数を a_n と書くことにする． ・・・

さて，ここに n 段のハノイの塔があったとしよう． 初期状態では，棒 1 に板 1 から板 n までの n 枚の板が 大きい順に積み上げられている． ということは， 一番下の板 n を無視すれば， n-1 段のハノイの塔があると思える．

最終的には，棒 2 に初めと同じ順番で n 枚の板を積み上げるのだから， ある時点で板 n が棒 2 に移動しなければならない． その移動ができるためには， 棒 1 にある板 n の上には何もなく， さらに移動先の棒 2 にも他の板があってはならない． なぜなら，板 n は一番大きいのだから， その下には他の板を置くことができないからである．

ということは，板 n を移動しようとするときには， 板 1 から板 n-1 まではすべて棒 3 に移動していることになる． さらに，小さい板の上には大きい板を乗せられないのだから， 棒 3 にはその n-1 枚の板が大きい順に積み上げられているのである． その状態を最小手数で実現しようと思うなら， n-1 段のハノイの塔の解法を実行すればよい． ただし，板の移動先が棒 3 であるから， 棒 2 と棒 3 の役目を入れ替えて考える必要はある．

したがって，板 n を移動する直前までに n-1 段のハノイの塔の解法と 同じ手数の板の移動があったことになる． その手数は a_n-1 である． それに板 n の移動の 1 手を加えて， a_n-1 + 1 ． あとは，棒 3 にある n-1 枚の板を棒 2 に移動した板 n の上に積み上げれば， ハノイの塔の移動が完成する． その作業も棒の役目を入れ替えて考えれば n-1 段のハノイの塔の移動に他ならない． すなわち，さらに a_n-1 回の板の移動を行えば，すべてが完成することになる． （図 3 参照）

これで， n 段のハノイの塔の解法には， 通算 a_n-1 + 1 + a_n-1 回の板の移動が必要であり， 十分であることがわかった． これから，次の漸化式が得られる．

a₁ = 1, a_n = 2 a_n-1 + 1 　(n ≧ 2)

この漸化式を解いて a_n の一般形を求めるのは簡単である． まず，第 2 式の両辺に 1 を足してみよう．

a_n + 1 = 2 a_n-1 + 2 = 2(a_n-1 + 1)

この式は， n が 1 つ大きくなるたびに， a_n + 1 が 2 倍になっていくことを意味している． となれば， a₁ + 1 = 2 だから， 2 から始めて 2 倍， 2 倍を繰り返していけば， n 回目には a_n + 1 = 2ⁿ となる． これから， a_n = 2ⁿ - 1 が得られるわけだ．」

*なるほど♪

プラスチック数（Plastic number）...^^

画像：http://ja.wikipedia.org/wiki/エドゥアール・リュカ より

「フランソワ・エドゥアール・アナトール・リュカ（François Édouard Anatole Lucas、1842年4月4日 - 1891年10月3日）はフランスのアミアン出身の数学者。フィボナッチ数の研究で知られ、その第 n 項を求める公式を与えた。また、フィボナッチ数列の一般化であるリュカ数列は彼にちなんで名付けられた。

エコール・ノルマル・シュペリウールで学び、天文台に勤めた後、パリで数学の教授になった。教授になる前には軍役に服した時期もある。

リュカは素数判定法、すなわちある整数が素数であるか否かを判定する方法の考案者として有名である。1857年、15歳のときにリュカ数列を用いた方法でメルセンヌ数の一つ 2¹²⁷ - 1 の素数判定を始め、19年後の1876年、ついにその数が素数であることを確かめた。計算機の無い時代のことであるから、それは手計算によるものであった。それからおよそ76年間もの間、この数は知られている中では最大の素数であり続けた。1952年、計算機によってさらに大きな素数が発見されたが、リュカの発見した素数が、手計算で素数であることが確かめられた最大のものであり続けることは確実である。・・・

1875年には、ディオファントス方程式

http://upload.wikimedia.org/math/0/4/4/044ce3ec74f9c80dd5f7119248e85dff.png

が 1 より大きい整数解として N = 24, M = 70 を唯一の解に持つことを示せ、という問題を提示した。この問題は俗にリュカのキャノンボール問題と呼ばれる。リュカ自身の証明は不完全であり、完全な証明が初めて与えられたのは1918年のことである。その証明は超楕円関数を用いた複雑なものであったが、現在はもっと易しい証明が知られている。

数学パズルにも興味を持ち、二進数を用いて五連環の解法を表した。さらに、現在でもアルゴリズムやプログラムの教材としてよく用いられるパズル、ハノイの塔を考案し、偽名 N. Claus de Siam（シャムのクラウス）を用いてこれを販売した。この名は Lucas d'Amiens（アミアンのリュカ）のアナグラムと考えられている。

リュカは珍しい状況で死を迎えた。フランス科学協会 の年会における晩餐会で、ウェイターが落とした陶磁器の破片がリュカの頬を切った。その数日後、おそらくは敗血症によるひどい皮膚炎のために他界した。わずか49歳での出来事であった。」

こんな呼称の数があるのね ^^

http://ja.wikipedia.org/wiki/プラスチック数 より

「プラスチック数（Plastic number）は、

http://upload.wikimedia.org/math/3/2/d/32dea2c743c7decee39bc735388c9b2e.png

という代数方程式の唯一の実数解であり、

http://upload.wikimedia.org/math/f/a/5/fa5cb312909940335942f40c1b6a58bc.png

と書ける。また、小数点以下27桁まで 1.324717957244746025960908854 と近似できる。

黄金比がフィボナッチ数列の隣接項比の、白銀比がペル数の隣接項比の極限であるように、プラスチック数はパドヴァン数列及びペラン数列の隣接項比の極限である。・・・」

http://ja.wikipedia.org/wiki/ペラン数 より

「数学において、ペラン数（英: Perrin number）とは以下の漸化式で定義される数である。

P(0) = 3, P(1) = 0, P(2) = 2,

P(n) = P(n − 2) + P(n − 3) for n > 2

3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39 ... （オンライン整数列大辞典の数列 A001608）

この数列の始めの部分は以下の通り。

n-頂点の閉路グラフにおける異なる極大独立集合の個数はn番目のペラン数となる。

・・・

Binetの公式 

ペラン数は、以下の方程式の解の累乗を用いて表すことが出来る。

x³ − x − 1 = 0

この方程式は3つの解を持ち、1つは実数解（p とする、プラスチック数と呼ばれる）、2つは複素共役な解（q, r とする）である。これら3つの解を用いて、フィボナッチ数列におけるBinetの公式と類似の公式を得ることが出来る。

http://upload.wikimedia.org/math/2/8/f/28f48f5adbe26fb3bfa5d599b8646864.png

複素解 q, r の絶対値は1より小さいので、 n を大きくすればこれらの解の累乗は0に近づく。大きな n に対しては、公式は以下のように簡略化出来る。

http://upload.wikimedia.org/math/7/a/a/7aa4153d412b5012c18b0a34b063e699.png

この公式は、大きなnに対してペラン数列の値を素早く計算するのに用いられる。ペラン数列の連続する項の比は p 、つまりプラスチック数に近づき、その値はおおよそ 1.324718 である。ペラン数列・パドヴァン数列におけるプラスチック数は、フィボナッチ数列における黄金比や、ペル数における白銀比と同様のものである。

・・・

素数、整除性 

P(n) が n で割り切れるような n を考えると以下のようになる。

n = 1, 2, 3, 5, 7, 11, 13, ...

最初は、1の後に素数が続いている。全ての素数 p に対して、 P(p) が p で割り切れることが証明されている。しかし、その逆は成り立たない。すなわち、P(n) が n で割り切れるような合成数 n が存在する。このような n をペラン擬素数（Perrin pseudoprime）と呼ぶ。「ペラン擬素数は存在するか」という疑問はペラン自身も考察したが、これはAdamsとShanksによって最小のペラン擬素数 271441 = 521² が発見される(1982)まで未解決であった。次に小さいものは 904631 = 7 x 13 x 9941 である。10億未満のペラン擬素数は17個存在する。また、無限に多くのペラン擬素数が存在することがJon Granthamによって証明されている。

ペラン素数（Perrin prime）とは、素数のペラン数である。ペラン素数の始めの数個は以下の通り（オンライン整数列大辞典の数列 A074788）。

2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797

2006年5月に、E. W. Weissteinは32,147桁の確率的素数 P(263226) を発見した。」

http://www.geocities.jp/ikuro_kotaro/koramu/396_hanoi.htm より Orz〜

「リュカとフィボナッチ数列

初項１，第２項１から始まり，隣り合う２項の和が次の項となる数列

　　１，１，２，３，５，８，・・・

をフィボナッチ数列とよびます．その一般項Ｆ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−ｘ−１＝０

の実根です．」

*これには呼称がないみたい...?

 ちなみに...

http://ja.wikipedia.org/wiki/ペル数 より

「ペル数（Pell number）は自然数で、n番目のペル数を P_n とおいて以下の式で定義される数列にある項のことである。

http://upload.wikimedia.org/math/a/3/6/a36d1961286e1f61719b002a1b276f98.png

http://upload.wikimedia.org/math/5/3/3/533afaea52b9c2f7d3a3ec8174619232.png

ペル数を1から小さい順に列記すると

1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, …

ペル数は前項を2倍した数と前々項との和になっている。なお0番目のペル数を0と定義する場合もある。

n番目のペル数は

http://upload.wikimedia.org/math/8/7/6/87674db5bf22125bd3867644c9461966.png

という式で表される。http://upload.wikimedia.org/math/0/9/b/09b53f5bee7dd36b3fad51a659e906af.png であるため、nが大きくなるにつれて隣接するペル数の比 P_n+1/P_n は白銀数 http://upload.wikimedia.org/math/4/d/2/4d2a5c0927d4f89965989491cecc2721.png に限りなく近付く。

行列では以下のように表現される。

http://upload.wikimedia.org/math/5/2/e/52e48d27027c0e7fb1e307c99e699988.png

ここから以下の恒等式が導かれる。

http://upload.wikimedia.org/math/f/a/c/fac78abb43f1ff3e7e78806d7c8326a5.png

この式はペル数をフィボナッチ数に入れ替えても当てはまる。

http://upload.wikimedia.org/math/c/6/4/c642c2d759eeeebea9fdc9eaf97bf24d.png　の自然数解 x,y を小さい順に並べるとyはペル数となる。またその x/y の値は

http://upload.wikimedia.org/math/8/8/6/88695b3f8ba3fa9257182ede11a7abea.png　とだんだん√2の値に近付く。

ペル数の内累乗数は1と169のみである。」

*ペル数が違和感あるなぁ...^^;...?　ペラン数ってのはフィボナッチもどきだけど...

3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39 ... を前にさかのぼると...

...,5,7,-13,12,-6,-1,6,-7,5,-1,-2,4,-3,2,1,-1,3,0,2,...といくらでも計算できるけど...

なぜに、3,0,2 を選んだんだろ...?

4444：食塩水濃度...

問題4444・・・算チャレ掲示板でhideさん掲示問 Orz〜

濃度2.0％の食塩水から水を20ｇ蒸発させると濃度が3.0％となった。 
ここに食塩を１ｇ加えると濃度は何％になるか？ 

(これは...高校生クイズで、100問30分なので時間の目安としては18秒です。...だって...

無理〜...^^;)

解答

・わたしの

3% に20gの水を追加したら、2%になったわけだから...

3*x=2*(x+20)

x=40

3%が40g...

塩=3*40/100=1.2g

(1.2+1)/40=2.2/40=0.055=5.5%

↑

間違ってました...^^; (鍵コメ様のご指摘あり Orz~)

食塩水は40+1=41 gになるので...

2.2/41=0.05365...=5.37%

になるんだぁ...!!

吸塩植物...アイスプラント（ice plant）♪

夏の日中戸外で動く人に、塩飴やら梅干しの摂取を勧めてるけど...

外来患者さんから、この植物を携行して食べてますって教えていただいた♪

調べてみたらば...わたしも食べたくなって来た ^^

これって...東北沿岸部の津波による塩害農地の改良に使えますよね？

それで、サラダ菜として買い取ってもらえれば一石弐丁!!

と思ったんだけど...?

画像：JA佐賀 http://jasaga.or.jp/nousanbutsu/yasai/iceplant/index.html より Orz〜

「新野菜「アイスプラント（ice plant）」は、南アフリカ原産の植物で国内では佐賀県で初めて栽培された注目の野菜です。表面を被うキラキラとしたジュエリーのような粒（塩分の結晶）とプチプチとはじける不思議な食感は、生で食べるのが一番です。

サボテンのような多肉多汁組織を持つ南アフリカ原産の多肉植物で、地中のミネラルを吸い上げる力がある吸塩植物。葉や茎の表面にキラキラとした水滴のような粒々が付いており、野菜の通称としてはアイスプラントと呼ばれています。粒々は水滴ではなくミネラル分を多く含むブラッター細胞と呼ばれる葉の一部です。・・・

栽培のきっかけは、土壌に含まれる塩化ナトリウムを吸収するアイスプラントの除塩機能を、有明海沿岸の塩害対策に役立てようと行われていた、佐賀大学農学部の研究。その後、生食で塩味がするという最大の特徴を活かした特産物に育てようと、JAさが管内農家との協力で栽培研究を進め、平成18年に初めて市場へ出荷することが出来ました。・・・」

4443：正三角柱の切断面...

問題4443・・・やどかりさんのブログ  http://blogs.yahoo.co.jp/oka_yadokary/26325027.html  より Orz〜

１辺が 20 の正三角形を底面とする正三角柱を、切り口が直角三角形で底面に触れないように切断します。その切り口の面積Ｓの最小値は？

解答

これまたアップし損ねてましたようで...申し訳ございませんでしたぁ ^^;...Orz〜

と思ってたら...

http://blogs.yahoo.co.jp/crazy_tombo/45333801.html にアップさせていただいておりました ^^;...

耄碌してきましたようで...〜m(_ _)m〜

記事は重複しますが...このままにしますね ^^;v

上記サイト http://blogs.yahoo.co.jp/oka_yadokary/26437705.html  より Orz〜

切り口の三角形の頂点を手前からB,A,Cとし、Aを通り底面に平行な切り口の正三角形に対し、

Bは手前xの所にあり、Cは向こうyの所にあるものとします。
AB²＝20²＋x²，　AC²＝20²＋y²，
BC²＝20²＋(x＋y)²，　BC²＝AB²＋AC² だから、
20²＋(x＋y)²＝20²＋x²＋20²＋y²、 20²＋x²＋2xy＋y²＝20²＋x²＋20²＋y²、
xy＝200 となります。
S²＝AB²･AC²/4＝(20²＋x²)(20²＋y²)/4
コーシー･シュワルツの不等式により、 (20²＋x²)(20²＋y²)≧(20･20＋xy)² だから、
S²≧(400＋200)²/4＝90000 、S≧300 になります。
等号が成立するのは 20：x＝20：y 、x＝y＝10√2 のとき、AB＝AC＝10√6 のとき です。

なお、次のように式変形しても最小値が出ます。

S²＝(20²＋x²)(20²＋y²)/4＝40000＋100(x²＋y²)＋(xy)²/4
＝40000＋100(x²＋y²)＋200²/4＝50000＋200(x²＋y²)/2

ここで、相加平均･相乗平均の関係により、 (x²＋y²)/2≧√(x²y²)＝xy＝200 だから、
S²≧50000＋200･200＝90000、 S≧300 となります。
等号は、x²＝y²＝200 のときに成り立ちます。

*対称性から...直角二等辺三角形と一意に決定されそうな気が...^^;...?