コラッツ予想に挑戦！（嘘） – 2024年京大数学第4問

2024年5月8日

　2024年京大数学第4問はコラッツ予想と呼ばれる未解決問題に出てくる、漸化式に関する問題です。問題文は以下のとおりです。

　与えられた自然数 a₀ に対して、自然数からなる数列 a₀,a₁,a₂,… を次のように定める。

a_{n+1} = \left \{ \begin{aligned} & \frac{a_n}2 & (a_n \text{が偶数のとき})\\ & \frac{3a_n + 1}2 & (a_n \text{が奇数のとき})\\ \end{aligned} \right .

次の問いに答えよ。

(1) a₀,a₁,a₂,a₃ がすべて奇数であるような最小の自然数 a₀ を求めよ。

(1) a₀,a₁,…,a₁₀ がすべて奇数であるような最小の自然数 a₀ を求めよ。

　一般項を出せと言っているわけではないし、割となんとかなりそうな気がします。それでは見ていきましょう。

1. 2024年京大数学第4問小問1の解法
2. 2024年京大数学第4問小問2の解法
3. うんちく- コラッツ予想
4. 解法のポイント

2024年京大数学第4問小問1の解法

　傾向を掴むため、 a₀ にいろいろな値を置いて、a_n が偶数になるまで実際に計算してみましょう。

\begin{aligned} & a_0 & a_1 && a_2 && a_3 && a_4 \\ & 1 & 2 \\ & 3 & 5 && 8 \\ & 5 & 8 \\ & 7 & 11 && 17 && 26 \\ & 9 & 14 \\ & 11 & 17 && 26 \\ & 13 & 20 \\ & 15 & 23 && 35 && 53 && 80 \end{aligned}

　a₀ = 15 のとき、a₃ までが奇数になって a₄ は偶数です。したがって答えは 15 です。単に計算しただけなので解法というほどの内容はありませんが、とりあえず実験して傾向を見るというのは重要です。方針を決めるためにも必ず試行しましょう。あと、計算ミスに注意しましょう。

2024年京大数学第4問小問2の解法

　これは実際に計算をしてみるというのは無理そうです。前言撤回、一般項を求める必要がありそうです。

　そうは言っても、条件によって満たすべき漸化式が違うので場合分けとか面倒くさそうだ、と一旦思案に沈みますが、よく考えると、a₀,a₁,…,a₁₀ がすべて奇数であるということは、これらすべてが漸化式

a_{n+1} = \frac{3 a_n +1}2

を満たすことを意味します。この一般項を求めれば、 a₀ が満たすべき条件を導出できそうです。

　というわけで、a₀ = 2m -1 (mは自然数) のとき、数列 {b_n}_n=0,1,… を、

\begin{aligned} b_{n+1} & = \frac{3 b_n +1}2 ( n=0,1,2, \cdots) \\ b_0 & = a_0 \end{aligned} \cdots(1)

と定義します。するとセオリー通り

\begin{aligned} b_{n+1} - b_n & = \frac{3}2(b_n- b_{n-1}) \\ & = \left ( \frac{3}2 \right )^n ( b_1-b_0) \\ & = \left ( \frac{3}2 \right )^n \left ( \frac{3a_0+1}{2}-a_0 \right) \\ & = \left ( \frac{3}2 \right )^n \left ( \frac{a_0+1}{2} \right) \\ & = \left ( \frac{3}2 \right )^n m \\ \end{aligned}

なので、 n ≧ 1 のとき

\begin{aligned} b_n -b_0 & = m \sum_{k=0}^{n-1} \left ( \frac{3}2 \right )^k \\ & = \frac{(\frac{3}2)^n -1}{ \frac{3}2 -1} m\\ & = ( \frac{3^n}{ 2^{n-1} }-2)m \end{aligned}

であり

\begin{aligned} b_n & = ( \frac{3^n}{ 2^{n-1} }-2)m + b_0 \\ & = ( \frac{3^n}{ 2^{n-1} }-2)m + a_0 \\ & = ( \frac{3^n}{ 2^{n-1} }-2)m + 2m-1 \\ & = \frac{3^n}{ 2^{n-1} }m -1 \\ \end{aligned}

というように、一般項を求めることができました。これは n=1 のときも成り立ちます。

　したがって、a₀,a₁,…,a₁₀ がすべて奇数であるならば、

\begin{aligned} a_n = b_n = \frac{3^n}{ 2^{n-1} }m -1 \\ (n=0,1, \cdots 10)\\ \end{aligned}

が成り立つので、 m は 2^n-1 (n=1,2,…,10) で割り切れて、かつその商が偶数である必要があります。すなわち、 m は 2¹⁰ の倍数である必要があります。

　逆に m は 2¹⁰ の倍数であるとし、

m= 2^{10} l (l \text{は自然数})

と表記します。

a₀ = 2m – 1 のとき、漸化式(1) で定義される数列 {b_n}_n=0,1,… の一般項

\begin{aligned} b_n & = \frac{3^n}{ 2^{n-1} }m -1 = 3^n 2^{11-n} l -1\\ \end{aligned}

は n ≦ 10 のとき奇数になります。したがって n がこの範囲のとき a_n = b_n です。よって、 a₀,a₁,…,a₁₀ がすべて奇数であるための必要十分条件は、 a₀ = 2m – 1 と置くときに m が　2¹⁰ の倍数になることであることが明らかになりました。

　そのような m で最小なものは当然 2¹⁰ なので、求める a₀ は 2 ☓ 1024 – 1 = 2047 です。

うんちく- コラッツ予想

　コラッツ予想とは、本問の漸化式で得られる数列 {a_n}_n=0,1,… において、自然数 a₀ をどのように選んでもある自然数 j が存在してa_j = 1 になる、というものです。言い換えると、 a_n を計算していくと必ず 2 のべき乗になる、ということです。今のところ未解決で、懸賞金も出ているようです。