中学数学解説

コラッツ予想の反例から攻める

コラッツ予想

718

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

あいさつ

んちゃ！
今日はコラッツ予想にチャレンジします。
予想しか書いてません。

コラッツ予想

コラッツ操作

写像 $C : N ∋ n \mapsto C (n) N$ を次の様に定める。なおこの写像を以下コラッツ操作と呼ぶ。
$\begin{array}{r} C (n) = {\begin{cases} \frac{n}{2} (n \equiv 0 (m o d 2) \\ 3 n + 1 (n \equiv 1 (m o d 2) \end{cases} \end{array}$
また、自然数 $n \in N$ に対して $k$ 回コラッツ操作を行う事を $C^{k} (n)$ の様に書く事にする。
また、以下の様に略記する。
2で割る操作をC1
3かけて1を足す操作をC2

コラッツ予想

任意の自然数 $n \in N$ に対して、ある自然数 $k \in N$ が存在して $C^{k} (n) = 1$ が成り立つ。

コラッツ予想の反例から攻める

今日、僕は仕事中に次の様な方法を思い付いたのでそれを紹介する。
それは次の様だ。

仮にコラッツ予想が成り立たないとすると、ある自然数 $n \in N$ が存在して、任意の自然数 $k \in N$ に対して $C^{k} (n) \neq 1$ が成り立つ。
そこで、その様な自然数 $n$ のうち最小のモノを $n_{0}$ を考える。
以下、その様な $n_{0}$ が存在しない事を示す事を目指す。

もし、コラッツ予想が成り立たないならば、自然数の集合 $N$ は次の様に分割できる。
$\begin{array}{r} {\begin{cases} S_{0} ⊔ S_{1} ⊔ S_{2} ⊔ S_{3} \dots \\ S_{0} = (コラッツ予想を満たす自然数全体) \\ S_{k} = (コラッツ予想を満たさない自然数の集合) (k = 1, 2, . . .) \end{cases} \end{array}$
コラッツ予想を満たさないそれぞれの系列 $S_{k}$ について最小の自然数 $n_{0} \in S_{k}$ が存在して次の条件を満たす。
1. $n_{0}$ は奇数
2. $n_{0}$ から始めた場合C1が現れる回数はC2が現れる回数の2倍を超える事は無い。

[1] $n_{0}$ が偶数とすると、 $n_{0}$ の最小性に反する。
ゆえに奇数でなければならない。
[2]C1が現れる回数をkがC2が現れる回数をlとする。
すると以下の不等式が成り立つ。
$C^{k + l} (n_{0}) < \frac{4^{k}}{2^{l}} n_{0}$
ゆえに、 $l = 2 k$ とすると $C^{k + l} (n_{0}) < n_{0}$ を得るので $n_{0}$ の最小性に反する。

反コラッツ的配置

コラッツ操作でC1が現れた時○
コラッツ操作でC2が現れた時●
と書くとコラッツ予想の反例は次の事と等価
●○●○●○○○●○○●○●・・・
ここで、○、●は左から順に置くものとし、○は自身を含む左側の○の総数が●の総数の二倍を超えない様に配置されている。
この様な○、●の配置を反コラッツ的配置と呼ぶ事にする。
反コラッツ的配置の集合を $N C o l l a z (ω)$ と書く事にする。
また、反コラッツ的配置の一番左から見て長さnの部分を切り取ったモノを有限反コラッツ的配置と呼び、その集合を $N C o l l a z (n)$ と書く事にする。

いかなる有限反コラッツ的配置 $F N C \in N C o l l a z (n)$ に対しても、適当な自然数 $N_{N F C} (n) \in N$ が存在して、その有限コラッツ的配置を再現する。

有限反コラッツ的配置 $F N C \in F N C o l l a z (n)$ を再現する最小の自然数 $N_{N F C} (n) \in N$ は $n$ に対して単調増加となる。

もし、上記の予想が成り立つなら有限の自然数 $n_{0}$ ではコラッツ予想の反例を得る事が出来ない事が分かるので証明が完了するはず。

長さ $2 n$ の反コラッツ的配置
●○●○・・・●○
を再現する自然数 $m_{0}$ を求めよ。

[1]反コラッツ的配置を数式に変換
自然数 $m_{0}$ にコラッツ操作 $C$ を $2 k$ 回作用させた結果を $m_{k}$ と書くと以下の連立方程式を得る。
$\begin{array}{r} {\begin{cases} m_{k} = \frac{3 m_{k - 1} + 1}{2} \in N \\ m_{k} ≢ 0 (m o d 4) \end{cases} \end{array}$
[2] $m_{k}$ を求めると次の様に書ける。
$\begin{array}{rcl} m_{k} & = & \frac{(m_{0} + 1) 3^{k} - 2^{k}}{2^{k}} \in N \Rightarrow 2^{k} | m_{0} + 1 \Leftrightarrow \exists q s . t . m_{0} = 2^{n} q - 1 (k \leq n) \\ ≢ & 0 (m o d 4) \end{array}$
[3][2]よりさらに次の式を得る。
$\begin{array}{rcl} 2^{n - k} q 3^{k} - 1 & \equiv & {\begin{matrix} 0 \\ 2 \end{matrix} q (- 1)^{k} - 1 (m o d 4) \\ ≢ & 0 (m o d 4) \end{array}$
[4]ゆえに、 $q$ は任意の自然数！
[5]特に $q = 1$ として $m_{0} = 2^{n} - 1$ は与えられた長さ2nの反コラッツ的配置を満たす事が分かる。