トップ› 京都大学› 2024年› 理系第4問

京都大学 2024年理系第4問解説

方針・初手

$a_n$ が奇数であるとき、漸化式は $a_{n+1} = \frac{3a_n + 1}{2}$ となります。この式をよく観察し、両辺に $1$ を加えると $a_{n+1} + 1 = \frac{3}{2}(a_n + 1)$ となり、等比数列に似た扱いやすい形を作れることに気づくのが最大のポイントです。ここから、$a_0, a_1, \dots, a_k$ がすべて奇数となるための $a_0$ の条件を一般的に求めていきます。

解法1

$a_n$ が奇数であるとき、与えられた漸化式は

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

である。この両辺に $1$ を加えると、

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

となる。

ある自然数 $k$ に対して、$a_0, a_1, \dots, a_k$ がすべて奇数であると仮定する。このとき、$m = 0, 1, \dots, k-1$ に対して上記の変形が成り立つため、数列 $\{a_n + 1\}$ は $n=k$ まで公比 $\frac{3}{2}$ の等比数列のように振る舞う。したがって、任意の $m \in \{0, 1, \dots, k\}$ に対して

$$ a_m + 1 = \left(\frac{3}{2}\right)^m (a_0 + 1) $$

すなわち

$$ a_m = \frac{3^m(a_0 + 1)}{2^m} - 1 \quad \cdots (*) $$

が成り立つ。

$(*)$ によって定まる $a_m$ がすべての $m \in \{0, 1, \dots, k\}$ において自然数かつ奇数となる条件を考える。 $3^m$ と $2^m$ は互いに素であるから、$a_m$ が整数となるためには、$a_0 + 1$ が $2^m$ の倍数でなければならない。これが $m=k$ のときにも成り立つ必要があるため、$a_0 + 1$ は $2^k$ の倍数である。したがって、自然数 $M$ を用いて

$$ a_0 + 1 = 2^k \cdot M $$

とおける。これを $(*)$ に代入すると、

$$ a_m = 3^m \cdot 2^{k-m} \cdot M - 1 $$

となる。さらに、$a_m$ が奇数であるためには、$a_m + 1 = 3^m \cdot 2^{k-m} \cdot M$ が偶数でなければならない。これがすべての $m \in \{0, 1, \dots, k\}$ で成り立つ必要があるが、特に $m=k$ のとき

$$ a_k + 1 = 3^k \cdot M $$

となり、$3^k$ は奇数であるから、$M$ 自身が偶数でなければならない。したがって、自然数 $L$ を用いて $M = 2L$ とおける。ゆえに、

$$ a_0 + 1 = 2^k \cdot 2L = 2^{k+1} L \iff a_0 = 2^{k+1} L - 1 $$

が必要である。

逆に $a_0 = 2^{k+1} L - 1$ のとき、

$$ a_m = \frac{3^m \cdot 2^{k+1} L}{2^m} - 1 = 3^m \cdot 2^{k+1-m} L - 1 $$

となる。$0 \leqq m \leqq k$ において $k+1-m \geqq 1$ であるから、第一項の $3^m \cdot 2^{k+1-m} L$ は常に偶数となる。よって $a_m$ は常に奇数となり、条件を満たす。

以上より、$a_0, a_1, \dots, a_k$ がすべて奇数であるための必要十分条件は、

$$ a_0 = 2^{k+1} L - 1 \quad (L \text{ は自然数}) $$

である。このような $a_0$ のうち最小のものは $L=1$ のときで、$a_0 = 2^{k+1} - 1$ となる。

(1) $a_0, a_1, a_2, a_3$ がすべて奇数である最小の自然数

$k=3$ の場合であるから、求める最小の自然数 $a_0$ は

$$ a_0 = 2^{3+1} - 1 = 16 - 1 = 15 $$

(2) $a_0, a_1, \dots, a_{10}$ がすべて奇数である最小の自然数

$k=10$ の場合であるから、求める最小の自然数 $a_0$ は

$$ a_0 = 2^{10+1} - 1 = 2048 - 1 = 2047 $$

解法2

(1)のように項数が少ない場合は、文字式を用いて順次条件を求めていくこともできる。 $a_n$ が奇数のとき、$a_n = 2m + 1$ （$m$ は整数）とおくと、

$$ a_{n+1} = \frac{3(2m+1)+1}{2} = 3m+2 $$

となる。ここから、$a_{n+1}$ が奇数になるのは $m$ が奇数（すなわち $m = 2l + 1$）のときであると分かる。

(1)の解答

$a_0, a_1, a_2, a_3$ がすべて奇数になる条件を順に求める。 $a_0$ が奇数 $\iff a_0 = 2k_1 + 1$ このとき $a_1 = 3k_1 + 2$ となる。 $a_1$ が奇数 $\iff k_1$ が奇数 $\iff k_1 = 2k_2 + 1$ これを代入して整理すると $a_0 = 4k_2 + 3$, $\quad a_1 = 6k_2 + 5$ $a_2 = \frac{3(6k_2+5)+1}{2} = 9k_2 + 8$ となる。 $a_2$ が奇数 $\iff k_2$ が奇数 $\iff k_2 = 2k_3 + 1$ これを代入して整理すると $a_0 = 8k_3 + 7$, $\quad a_2 = 18k_3 + 17$ $a_3 = \frac{3(18k_3+17)+1}{2} = 27k_3 + 26$ となる。 $a_3$ が奇数 $\iff k_3$ が奇数 $\iff k_3 = 2k_4 + 1$ これを $a_0$ の式に代入すると $a_0 = 16k_4 + 15$ $a_0$ が自然数となる最小の非負整数は $k_4 = 0$ のときであり、最小の $a_0 = 15$ である。

(2)の解答

(1)の計算の規則性から、$a_0, \dots, a_k$ がすべて奇数になる条件は、$a_0 = 2^{k+1} \cdot p + (2^{k+1} - 1)$ （$p$ は非負整数）と表せることだと推測できる。したがって、$a_0, \dots, a_{10}$ がすべて奇数になる条件は $a_0 = 2^{11} \cdot p + (2^{11} - 1)$ となり、その最小値は $p=0$ のときの $2^{11} - 1 = 2047$ である。

解説

未解決問題として有名な「コラッツ予想」を題材にした問題です。解法1のように、$a_{n+1} = p a_n + q$ の形を見たら、等比数列を作るための特性方程式の考え方（$c = p c + q$ を解いて両辺から引く）を適用してみるのが強力です。今回の場合、特性方程式 $\alpha = \frac{3}{2}\alpha + \frac{1}{2}$ を解くと $\alpha = -1$ となるため、$a_{n+1} - (-1) = \frac{3}{2}(a_n - (-1))$ という変形を導くことができます。解法2のように、まずは実験して規則性を探るアプローチも実戦では非常に有効です。