« ■コマネチ大学数学科106講:総集編 | トップページ | ■小学生にもできる魔方陣の作り方 »

2008年9月27日 (土)

■放送大学:Collatz・角谷の問題

 テレビ番組の改編成時期とあって、「たけしのコマ大数学科」は、しばらくお休みのようだ。でも、10月以降も「たけしのコマ大数学科」は存続するようなので、ひと安心^^; そこで、今回は「コラッツ・角谷の問題」を考えてみよう。

【遊び方】初期値の入力欄をダブルクリックして、適当な数値を入力したら、「Enter」ボタンを押す。すると、偶数なら2で割り、奇数なら3倍して1を加えるという計算を繰り返して行う。デフォルトの「26」では、10回計算を行うと「1」になる。そこで初期値を「27」にすると、111回目で、やっと「1」に収束する。はたして、初期値が「1」以上のすべての整数は、このルールに従う限り「1」に収束するのか? というのが「コラッツ・角谷の問題」。こんな簡単なルールであるにも関わらず、「コラッツ・角谷の問題」は、未解決問題なんだよね。だから「コラッツ(角谷)予想」とも呼ばれる。いろいろな数値を入れて確かめてみてね。

 なんだか、知ったかぶりの爺だが、じつは「放送大学」の「数学とコンピュータ」とゆー講義を見ていたら、「Javaによるプログラミング」の例題として、この「Collatzの問題」あるいは「角谷の問題」として、紹介されていたので、初めて知った次第^^;

 で、この「放送大学」、入学するには、ふつうの大学並みの授業料が必要だが、講義をテレビで視聴するだけなら無料だ^^ 爺の住んでいる地域では、UHFの16chで見ることができるし、スカイパーフェクTV!の205ch(無料)や、ケーブルテレビなどでも視聴可能だ。

 「数学とコンピュータ」は、すでに全15回の講義が終了してしまったけれど、講師人が贅沢で、メイン講師、長岡亮介氏をはじめとして、講義内容に応じて、その分野の第一人者が務める。たとえば、「LaTex文書の書き方」や「Javaによるプログラミング」の講義では、奥村晴彦氏が務めていた。「たけしのコマ大数学科」のようにエンターテインメント性はないけれど、爺にとっては、どちらも、かわりなく楽しい(もちろん、興味のある話題だけ^^;)。

 さて、冒頭の「Collatz・角谷の問題」だが、現在、コンピュータを使い「3×2^53=27,021,597,764,222,976」まで反例がないことが確認されているそうな。

詳しくは以下を参照
Wikipedia:コラッツの問題

Collatz 問題の一般化について

数学とコンピュータ 数学とコンピュータ
(放送大学教材)

長岡 亮介/著
岡本 久/著

放送大学教育振興会
新訂版(2006/5)


|

« ■コマネチ大学数学科106講:総集編 | トップページ | ■小学生にもできる魔方陣の作り方 »

コメント

ある数が奇数なら、3を掛けて1を足す。ある数が偶数なら2で割る。計算結果が奇数なら、また3を掛けて1を足す。偶数なら、また2で割る。その計算を続けて行くと、ありとあらゆる数から始めても、最後は全て4→2→1→4→2→1の繰り返しになるのではないかと、コラッツは予想しました。
計算値が次第に小さくなって行くと、必ず最終的には4→2→1の繰り返しになってしまいます。従って、計算値が、無限に大きくなって行く様な始まりの数があれば、必ずしも4→2→1の繰り返しにはならないことが証明されます。
最初の数が奇数(X)の場合、3を掛けて1を足すと、X(奇数)×3(必ず奇数)+1=Y(必ず偶数)となります。従って、Yは偶数なので、次の計算は必ず割る2となります。よって、幾ら計算値をどんどん大きくしていこうとしても、X(奇数)×3+1=Y(偶数)→Y(偶数)÷2=Z(奇数)、Z(奇数)×3+1=O(偶数)、O(偶数)÷2=P(奇数)と、奇数→偶数の繰り返し以上には、計算値は大きくなっては行かないことが分かります。つまり、(ある奇数×3+1)÷2の計算結果が、必ず奇数であれば、計算値は無限に大きくなって行き、必ずしも最後は4→2→1の繰り返しとはならないことが証明されます。
 では、その様な始まりの奇数Xがあるか否か、エクセルを使って検証してみましょう。列Aに上の行から順番に、1・3・5・7・9・11・・・・と奇数を入力してください。列Bに上から順に「=(A1×3+1)/2」「=(A2×3+1)/2」「=(A3×3+1)/2」・・・・と、左のA列の奇数を3倍して1を足し2で割る数式を入力します。列Cに上から順に「=(B1×3+1)/2」「=(B2×3+1)/2」「=(B3×3+1)/2」・・・・B列のセルの計算値を、更に3倍して1を足し2で割る数式を入力します。同様の式をD列・E列・F列・・・に入力して行き、どんどん3倍して1を足し2で割る計算を行います。
この結果、全ての列の計算値が奇数となるものがあれば、計算値は無限に大きくなって行きます。そこで、各列において奇数が出現する様子を見てみましょう。B列では、上から2回に1度5・11・17・23・29・35・・と奇数が現れます。C列では、4回に1度17・35・53・71・89・107・125・・・と奇数が現れます。D列では8回に1度53・107・161・215・269・323・・・と奇数が現れます。E列では、16回に1度161・323・485・647・809・・・と奇数が現れます。F列では、32回に1度485・971・1457・1943・2429・2915・・・と奇数が現れます。G列では、64回に1度1457・2915・4373・5831・7289・・・・と奇数が現れます。以後同様に、H列では128回に1度、I列では256回に1度、J列では512回に1度奇数が現れます。
ここまでの計算で、奇数が連続するのは、512行目の1,023・1,535・2,303・3,455・5,183・7,775・11,663・17,495・26,243・39,365の1つです。3倍して1を足し2で割る計算をn回行えば、全ての計算値が奇数になるものは、2のn乗分の1に減少していきます。この事実は、簡単に証明出来るでしょう。
従って、計算を行えば行う程、計算値が奇数の連続になるものは1/2・1/4・1/8・1/16・1/32・・どんどん半分に減少していきます。しかし、無限の数の中では、2のn乗分の1は決して0にはなりません。3倍して1を足し2で割る計算をn回する場合、1から数えて2のn乗番目の奇数(又はその倍数番目の奇数)から始めると、n回の計算結果全てが奇数となります。計算値は大きくなる一方で、4→2→1の繰り返しにはなりません。
有限の数の範囲内では、計算値がその範囲を超えるまで計算を行っていけば、奇数が連続しなくなります。しかし、無限の数の中では、常に先に2のn乗番目の奇数があります。それは(1+2×2のn乗)で表現される数値で、尽きることはありません。そのnを∞にした数値から始めれば、無限に計算を繰り返しても4→2→1の繰り返しにはなりません。
少なくとも1組は、永遠に奇数が連続し数値が大きくなっていく組み合わせが存在します。従って、コラッツの予想は残念ながら誤っています。

投稿: catbird | 2011年2月11日 (金) 23時29分

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/99648/24058337

この記事へのトラックバック一覧です: ■放送大学:Collatz・角谷の問題:

« ■コマネチ大学数学科106講:総集編 | トップページ | ■小学生にもできる魔方陣の作り方 »