未解決問題

数学の未解決問題ってよく本で見ますが、
未解決の問題で小学生でも意味のわかるものが結構あると思います。
フェルマーの最終定理が証明されたときは一種の感動を覚えたのを記憶しております。
未解決問題は私もそこそこ知ってはいるのですが、新しい未解決問題を聞くと「自然は奥が深いな」っとつくづく思ってしまいます。
そこで、いろいろな未解決問題（素人にも意味がわかるようなもの）を教えていただけないでしょうか。よろしくお願いいたします。

No.1 回答者： serpent-owl 回答日時： 2001/02/25 22:41

　こんにちは。

数学はド素人なんです。私も。ちょっと興味があってちょこちょこつまみ食いする程度です。
　で、その私でも、一応問題の意味はわかったというのをご紹介しましょう。
　「コラッツの問題」というものです。
　これは、ある数が偶数の場合は二分の一にし、奇数の場合には三倍して一を足すという単純なルールで反復計算するものです。例えば、最初が１なら、
　　　１→４→２→１
となって、最後のものは１ですから、また同じ事を繰り返します。ですから、１になったら「おしまい」としましょう。
　この反復、初期値を１から順に増やしていくと、「１」に戻るまでのステップ数や最大値がさまざまに変化しますが、初期値２７でとんでもないことが起こります。ステップ数が１１１、最大値は９２３２にもなるのです。そしてやっぱり、最後は１に。
　この問題ですが、初期値にどのような数をとっても、必ず最後は「１」に戻るのかどうか、まだ証明されていないそうです。素人眼には、簡単そうに見えるのですが…
　以下はオマケです。この「コラッツの問題」を自動計算するプログラムです。Windowsマシンなら、「十進BASIC」で実行できます（入手先は下記の参考URLに）。

DO
LET i=i+1
LET n=i
LET st=0
LET mx=0
PRINT st,n
DO
IF MOD(n,2)=0 THEN
LET n=n/2
ELSE
LET n=n*3+1
END IF
LET mx=MAX(n,mx)
LET st=st+1
PRINT st,n
IF n=1 THEN EXIT DO
LOOP
PRINT "初期値 ";i
PRINT "ステップ数 ";st
PRINT "最大値 ";mx
PRINT "---------------------------------------------------"
WAIT DELAY 1
LOOP
END

　やたら行数を食いました。ごめんなさい。

参考URL：http://hp.vector.co.jp/authors/VA008683/

No.2 回答者： myzard 回答日時： 2001/02/26 00:17

　よく知られていると思いますが、私は素因数分解の

効率的な手法を挙げさせていただきます。

　素因数分解とは、ご存知のように、ある数を
2つの素数（約数が1とその数の2つしかないような数）の
積に分解することですが、これを可能にする一定の
解法はまだ見つかっていません。一見簡単そうに
思えますが、ちょっとでも大きい数になると総当りで
1つずつ調べるしかないようです。例えば91。このくらいなら
すぐにできそうですが、案外大変です。もしこの
解法を見つけたら、かなりすごい発見だと思います。

　ちなみに、インターネットで情報保護の暗号技術で
広く使われているRSA法も、この素因数分解の困難さが
その暗号の解読されにくさの根拠になっています。
もちろん、コンピュータに総当りでずっと計算させ
つづければ、いずれ分解できるでしょう。しかし、
現在の計算能力では天文学的な時間がかかってしまうのです。
すごいですね。

　ちなみに、91は7x13でした。

No.3 回答者： ryouchi 回答日時： 2001/02/26 12:10

フェルマー系なら下記URLを参考にしてみては

参考URL：http://freepage.gaiax.com/www/freepage/m/t/mathe …

No.4 回答者： sohei 回答日時： 2001/03/04 22:03

純粋に（期待されている意味での）数学かどうかは疑問なのですが、

「巡回セールスマン問題」や「ナップサック問題」等があります。
いずれもよく似た問題です。小学生にもすぐ理解できるかと。争点は
「効率よく」解く方法です。全ての場合を解べれば説けるのですが、
その組み合わせがあまりにも大きくなるため、コンピュータですら扱いきれません

・巡回セールスマン問題
　　幾つかの道で繋がった都市をセールスマンが尋ねていくとき、
　歩く道の長さを最も短くする方法を答えよ

・ナップサック問題
　　ナップサックに詰めるものの価値の合計を最大にするにはどのように詰めればよいか答えよ
　（いくつもの品物があって、それぞれに大きさと価値が与えられています。
　　ex. サッカーボール（\3000）は１個、バナナ（\400）は10個まで入る etc...）

他には、一筆書きができる条件は、「オイラー」が証明しました。
（全ての点から出ている辺が「偶数」か「２本だけが奇数」の時一筆書き可能）
一筆書きは、「全ての線を２回通ることなく通る」というものですが、
よく似たもので

「全ての点を２回通ることなく通れるか？」

という問題があります。
（一筆書きできるのを「オイラー路」と言うのに対し、「ハミルトン路」と言います）
このような問題はNP完全問題と言われています。
未解決問題はグラフ理論の分野に結構あるようです。

完全に未解決ではありませんが、４色問題と言うのも有ります。

「地図で隣り合ったところを異なる色で塗るとする。
　このとき、４色有れば塗り分けられることを示せ」

３色ではできないこと、５色ではできることは比較的簡単に示せるようです。
（３色でできないことは絵を描いてみればすぐに分かることです）
この問題は1000何百通りに分類されて、コンピューターによる総当たり方式
で証明されたようですが、あまりスマートな証明ではありません（^^;

秋山仁さんの本か、ピーターフランクルさんの本でそのような問題を
まとめた本があったような気がします。

文章がわかりにくくなってすみません。
問題の説明に図を使えないとしんどい問題が多いです（^^;

No.5 回答者： 390131 回答日時： 2010/01/01 06:08

4色問題とは、全ての図形は、4色で塗り分けられるかと言う問題です。

5色要するとは、全ての5面が他の4面と接すること。それは、4本足の蛸に似ている。頭に4本の足が生えており、全ての4足が他の3足と接触出来るのか。両サイドの足を接触させると間の足は囲まれる為、向かいの足には接触出来ない。球面上でも同じです。4本足蛸が、ボールを抱いた形です。ボール上で4本足が接触出来るか。平面の時と結果は同じ。5色必要な図形は作れない。4色必要とは、4面が他の3面に接触しているので、3本足の蛸だ。3本の足は接触出来る。単純化すると120度で3分割したドーナッツ形になる。図の外の面が頭。球面上では、三本足蛸がボールを抱えた形を単純化すると三角柱となる。底面が蛸の頭で、3側面が足です。球面中の一面が無限に広がると平面になる。平面上絵の周囲の面は、収縮すると球面上の1面になる。絵は同じです。平面上の無限に広い1面と、球面上の1面は共に1色が必要で同じこと。三角柱底面を無限に広げると、平面の120度で三分割したドーナッツとなる。この三角柱の上面と底面を接触出来るでしょうか。3側面が筒状ならそれぞれ接触しています。3側面上で上面と底面を接触すると、3側面は紐状になり接触が切られます。次につづく

No.6 回答者： 390131 回答日時： 2010/01/01 06:09

前からつづく。

三角柱の中外で接触するしかありません。それはドーナッツになります。中接触の時、横置ドーナッツを水平に3面に分け、内1面を垂直に3分割した形となる。外接触の時、横置ドーナッツを垂直に3面に分け、内1面を水平に3分割した形となる。若しくは、クラインの壷状となる。よって球面上5色を必要とする図形は描けない。三角柱底面を広げると、平面の120度三分割ドーナッツになる。中の穴を外の空間に接触させると、ドーナッツは切られ紐状になり3面の接触が切れる。平面上でも、5色を必要とする図形は描けない。4面に接触する面は4角形以上です。3角形は3面にしか接しない。5つの四角形をそれぞれ接する様に置けるでしょうか。四角形の4辺は接触する（2本が一本になる）ので、出来た図の線は10本です。10本の線で5つの四角形が作れるでしょうか。立法体の辺は12本です。2辺を消すと面は4面となり5面は描けない。ドーナッツなら描ける。従って、平面及び球面に描かれたどの様な図形も、4色で塗り分けられると言えます。