コラッツの問題
整数論の有名な未解決問題に、コラッツの問題（角谷の問題とも呼ばれます）というものがあります。問題の内容は、「任意の自然数 n に対し以下の操作を繰り返すとき、有限回の操作で 1 となる：
・n が偶数なら 2 で割る
・n が奇数なら 3 をかけて 1 を足す」
Wikipedia によると、3×2^53 までには反例がないことが確認されているようですが、任意の自然数に対する証明はつけられておらず、未解決問題の理由となっています。
ここからが本題。Yahoo!知恵袋をながめていたら、こちらやこちらにコラッツの問題の自明性を主張されている方々がいらっしゃるのですが、一厘でも良いので、自明であることの一端を知りたいと思いました。
« INSCRYPT 2009: Call for Papers | トップページ | SHARCS 2009: Submission Deadline Extended »
「数学」カテゴリの記事
- NHKスペシャル: 『魔性の難問～リーマン予想・天才たちの闘い～』（地上波版）の再放送(2009.11.26)
- RIMS 研究集会:『代数的整数論とその周辺 2009』(2009.12.04)
- NHKスペシャル: 『魔性の難問～リーマン予想・天才たちの闘い～』の再放送(2009.11.19)
- NHKスペシャル『魔性の難問～リーマン予想・天才たちの闘い～』 を見ました(2009.11.17)
- NHKスペシャル: 『素数の魔力に囚われた人々』(2009.11.10)
コメント
この記事へのコメントは終了しました。
« INSCRYPT 2009: Call for Papers | トップページ | SHARCS 2009: Submission Deadline Extended »
はじめまして。
このブログを読んで「自明」という言葉が出てきたのでコラッツの問題で主張される自明であることの一端を表現してみようと思い、キーボードを打ってみます。
私がコラッツの問題を考えた時には反例がないことを証明することから始めました。
すなわち①１しかループする数がないこと②際限なく大きくなる数がないこと。③Ａ→Ｂ→Ｃ→Ａのように大循環する数がないことです。①②はなんとか答えを見つけましたが、③だけは曲者で考えるヒントは何かないものかと数同士の関係を考えてみました。（③の証明は背理法で別の方がやられています。）
どこの人も言っているように「偶数のことは考えなくてもいい、奇数のことだけを考えればいい」ということでした。つまり偶数を２で割りきれなくなるまで割ると奇数になるということです。
わたしはこのことから奇数と偶数の対応を見ることにしました。
こんな風に
1 2 4 8 16・・・
3 6 12 24 48・・・
5 10 20 40 80・・・
7 14 28 56 112・・・
9 18 36 72 144・・・
11 22 44 88 176・・・
13 26 52 104 208・・・
15 30 60 120 240・・・
17 34 68 136 272・・・
19 38 76 152 304・・・
・
・
・
このように偶数の数列は続くのでどんな偶数を持ってきてもかならず偶数の数列に入ります。いわゆるモレなくダブリなくです。これでどんな偶数を選んでも必ず奇数になるわけです。
次に奇数同士の関係を見てみます。どの数を選んで関係を見るかといいますと、「３を法として０以外と合同な奇数」と全ての奇数です。
こんな風に
1 1 5 21 85・・・
5 3 13 53 213・・・
7 9 37 149 597・・・
11 7 29 117 469・・・
13 17 69 277 1109・・・
17 11 45 181 725・・・
19 25 101 405 1621・・・
・
・
・
一番左の数は「３を法として０以外と合同な奇数」です。左から２番目の数は全ての奇数です。
どのようにこの数列を作ったかを説明します。
まず、３を法として０以外と合同な奇数に２をかけていき、３を法として１と合同な偶数にします。次にできた３を法として１と合同な偶数から１を引いて３で割ります。そしてできた奇数を記載し、あとはその奇数に４をかけて１を足す。これを繰り返すだけです。
左から２番目の数列は実は３をかけて１を足し、２で割りきれなくなるまで割ると一番左の奇数になります。これはどんな奇数も３をかけて１を足すと３を法として１と合同な偶数になるからであり、また、３を法として１と合同な偶数は３を法として０以外と合同な奇数に２をかけて作られ、それだけでなく３を法として１と合同な偶数は３を法として１と合同な偶数に４をかけてもできるからです。
ある奇数ｎに３をかけて１を足す
３ｎ＋１
これにｎを足す
３ｎ＋１＋ｎ＝４ｎ＋１
３をかけて１を足す
３（４ｎ＋１）＋１＝１２ｎ＋３＋１
＝１２ｎ＋４＝４（３ｎ＋１）
このようなことから上の奇数同士のような対応が見いだせるのであり、左から２番目の数列に全ての奇数がモレなく、ダブリなくあると言い切れるのです。
このことからどのような自然数を持ち出してもそれが偶数ならば必ず奇数に対応され、奇数ならばそれがどのような奇数でも数列の左から２番目に出てくるのであるからやがては必ず１に到達するのだと確信しております。
なぜならば一番左にある奇数も左から２番目の数列に必ず１回は出てくるのですから。
無数の奇数がひとつの３を法として０以外と合同な奇数に対応し、やっとひとつになった奇数はまた別の３を法として０以外と合同な奇数に対応する無数の奇数のひとつであるという事実は実にすごいことだと思います。
以上のことから③の問題ももうすぐ解決できるのではと確信しています。もちろんコラッツの問題もです。
以 上
投稿: tocshii | 2012年8月28日 (火) 16時21分
おはようございます
１しかループしないことが自明（？）である事について示します。
全ての正数を四つしか数がない世界で考えます。それは０、１、２、３の四つです。
偶数は０、２としか表されません。
奇数は残りの１、３です。
コラッツの問題では奇数に３をかけて１を足す。偶数になったら２で割り切れなくなるまで割る。という計算をしますので元の奇数よりも大きくなるか小さくなるかは４で割り切れるか、２でしか割り切れないかが重要になってきます。
だから正数を四つしか数がない世界で考えるのです。
このように考えると１に３をかけて１を足すとその数は０になります。
３に３をかけて１を足すとその数は２になります。
このことから、全ての奇数は３をかけて１を足すと少なくとも４で割り切れるか、２でしか割り切れないか二つに一つであることが解ります。
最初に３をかけて１を足しているのですから、４でわったら元の奇数より小さくなります。２で割って奇数になるのならば元の奇数より大きくなります。
しかし、数ある数を見ると一つだけ例外があります。
それは１です。
したがってループする奇数は１しかありません。
このことを示すためには法計算が必要でした。
したがって自明ではありませんでした。
投稿: tocshii | 2012年9月 4日 (火) 05時26分
おはようございます
コラッツの問題において、際限なく大きくなり続ける奇数がないことが自明（？）なのかを示します。
元の奇数より大きくなる数は４を法として３と合同な数です。しかしこの中には８を法として７と合同な数、１６を法として１５と合同な数、３２を法として３１と合同な数・・・２＾ｎを法として２＾−１と合同な数があります。
これらをまとめるにはどうするか
４を法として３と合同な数は数列によって表すことができます。
すなわち中国の剰余定理を使います
例
２が２回かかっている数がある。
これに加えて２が２回かかっている数にできる最小数は何か
答えは８である
例を４個挙げる
４ １２ ２０ ２８・・・
２８までに他の例を挙げる
２が１回かかっている数
６、１０、１４、１８、２２、２６（公差は４）
２が３回かかっている数
８、２４（公差は１６）
２が４回かかっている数
１６、４８（公差は？、３２）
したがって（ｎ≧２）の条件で２＾ｎ−１を初項、２＾（ｎ＋１）を公差とする等差数列が全ての４を法として３と合同な数を表しています
２＾ｎ−１＋２＾（ｎ＋１）
（ｎ≧２）
ようするに数列の任意の項を見ると
２＾ｎ−１＋２＾ｎ×２ｑ
＝２＾ｎ×（２ｑ＋１）−１
（ｎ≧２、ｑ＝０、１、２・・・）
２ｑはｑが０を含む自然数であるという条件で偶数、つまりｅｖｅｎとなります
２＾ｎ×（２ｑ＋１）−１＝２＾ｎ×（ｅｖｅｎ＋１）−１
ｎには有限な数ならばいくらでも大きな数が入ります（ココ重要です）
１０、１００、１０００、１００００・・・
３をかけて１を足します
３×｛２＾ｎ×（ｅｖｅｎ＋１）−１｝＋１
＝３×２＾ｎ×（ｅｖｅｎ＋１）−３＋１
＝３×２＾ｎ×（ｅｖｅｎ＋１）−２
上は必ず偶数なので２で割ります
｛３×２＾ｎ×（ｅｖｅｎ＋１）−２｝／２
＝３×２＾（ｎ−１）×（ｅｖｅｎ＋１）−１
これは必ず奇数であり前の奇数より大きくなっています
続けると２が３に取って代わられ
３＾ｎ×（ｅｖｅｎ＋１）−１
これは必ず偶数になり、２で割れるので前の奇数より小さくなります
ｎに無限大を入れてみましょう
もし、ｎに入る無限大があるとすると計算できたとするモノは最初に入れた無限大よりも大きいことになり矛盾がでます
したがってｎには有限な数しか入りません
ｎが有限なのだから、コラッツの計算を有限回繰り返すと必ず元の奇数より小さくなる時が必ず来ます
これで際限なく増加する数がないことが示されました。これを証明するために使ったのは中国の剰余定理、等差数列、無限大は数ではないということの３つでした。
つまり際限なく増加する数がないということは自明ではないということです
投稿: toshii | 2012年9月 5日 (水) 06時27分