赤目無冠のぶろぐ

アニメ、将棋・麻雀、音楽(作曲、DTM、ベース)、思想など

帰ってきたニートの一日の作者。詳しくははじめにへ。

コラッツの問題の証明(というか予想)

コラッツの問題という数論の未解決問題があるらしい。
偶数なら2で割る、奇数なら3倍して1を足す、という操作を繰り返すと、どんな整数から始めてもいずれ必ず1になるというもの。


証明(というかいい加減な予想)

まず奇数を3倍して1を足すと必ず偶数になることは容易に証明できる。
その奇数を2n-1(nは自然数)とおくと、
3(2n-1)+1=6n-2=2(3n-1)なのでこれは偶数。
ということは「偶数なら2で割る」ということなので3n-1まではいくと断言できる。

で、この値は当初の値の約1.5倍。

対して偶数の場合、2で割るので、値は当初の値の0.5倍になる

ということは奇数の場合は約1.5倍になるが、偶数の場合は0.5倍になるので、
明らかに偶数の場合の減少速度が奇数の場合の増加速度を勝っている。
(つまりこの演算は、詳細は難しいが、減少関数だと考えられる)

そして一般にある整数が奇数(偶数)である確率は、交互に並んでいるものなので、50%。

よって、具体的な値はケースバイケースだが、とにかく傾向として減少していくことは言える。
そして最も小さな正の整数は1なので、紆余曲折を経て、最終的に1に収束すると予想される。

ただ、これは傾向を示しただけであり、いかなるときも厳密に成立することを示すほどのものではない。
無限の試行で平均的に収束するのは確かだと思うのだが。
インスピレーションはいいと思うのだが・・・誰かやっつけてくれないものだろうか。


追記(2014/01/02)

 減少速度が増加速度を勝っていれば1に収束すると安易に予想したが、この問題はそんなに甘くないことが分かった。
 というのも、似たような問題で反例があるのだ。

反例

 「3倍して1を足す」というルールを「3倍して1を引く」に変更

 これでも約1.5倍の増加と0.5倍の減少の丁半博打になることは変わらない。
 「1を足す」を「1を引く」に変えても、おおよそ1.5倍前後であることは同じであり、偶数が半減していく速度には勝てないからである。
 従って前の理屈でいくとこれも最小の正の整数、1に収束しそうである。

 しかし5の場合、
 5→14→7→20→10→5となり、循環するため、1に収束しない。

 よって、確率的な考えだけで1に収束することを安易に決め付けてはいけないことになる。
 循環するパターンがあるので1だけとは限らない。
 (ただ発散の可能性が低く、何らかの整数に収束してループする可能性が高いのは確かだと思う)

 因みに最初のルールの場合、1になっても続けるとすると、1→4→2→1という循環になる。
 そのため、最初の方は4→2→1というループに全てが誘導されることを示すという考え方もあると思う。
 (2の累乗になれば1になるのだから、2の累乗になることを示せばよい)