京都大学 2024年度理系数学第4問解答・解説

問題

与えられた自然数 $a_{0}$ に対して，自然数からなる数列 $a_{0}, a_{1}, a_{2}, \dots$ を次のように定める．

a_{n + 1} = ⎩ ⎨ ⎧ \frac{a _{n}}{2} \frac{3 a _{n} + 1}{2} (a_{n} が偶数のとき) (a_{n} が奇数のとき)

次の問いに答えよ．

(1) $a_{0}, a_{1}, a_{2}, a_{3}$ がすべて奇数であるような最小の自然数 $a_{0}$ を求めよ．

(2) $a_{0}, a_{1}, \dots, a_{10}$ がすべて奇数であるような最小の自然数 $a_{0}$ を求めよ．

出典：京都大学 2024年度前期日程第2次学力試験理系第4問

方針

奇数 $a_{n}$ から次も奇数になる条件を合同式で調べると， $a_{n} \equiv 3 (mod 4)$ が必要十分である。より長く奇数が続く条件は， $a_{n} + 1$ に含まれる2の因子の個数で管理できる。 $a_{0} = 2^{r} q - 1$ （ $q$ は奇数）と書くと，奇数が続く間は $a_{j} = 3^{j} 2^{r - j} q - 1$ となり， $j = r$ で偶数になる。したがって $a_{0}, a_{1}, \dots, a_{m}$ がすべて奇数であるには $r ≧ m + 1$ が必要十分で，最小値は $q = 1$ ， $r = m + 1$ のときである。

解答

まず，奇数 $a_{n}$ に対して次の項も奇数になる条件を調べる。 $a_{n}$ が奇数のとき $a_{n + 1} = \frac{3 a _{n} + 1}{2}$ である。これが奇数であるためには $3 a_{n} + 1 \equiv 2 (mod 4)$ であればよい。これは $3 a_{n} \equiv 1 (mod 4)$ と同値であり， $3 \equiv - 1 (mod 4)$ より $a_{n} \equiv 3 (mod 4)$ である。

長く奇数が続く条件を一般化する。自然数 $a_{0}$ を $a_{0} = 2^{r} q - 1$ と書く。ただし $q$ は奇数， $r ≧ 1$ である。この形なら $a_{0}$ は奇数である。奇数の項が続く限り， $a_{j + 1} = \frac{3 a _{j} + 1}{2}$ なので，帰納的に $a_{j} = 3^{j} 2^{r - j} q - 1 (0 ≦ j ≦ r)$ となる。実際， $j$ から $j + 1$ へは $\frac{3 ( 3 ^{j} 2 ^{r - j} q - 1 ) + 1}{2} = 3^{j + 1} 2^{r - j - 1} q - 1$ である。

この式から， $j = 0, 1, \dots, r - 1$ では $a_{j}$ は奇数であり， $j = r$ では $a_{r} = 3^{r} q - 1$ となって偶数である。したがって， $a_{0}, a_{1}, \dots, a_{m}$ がすべて奇数であるためには $r ≧ m + 1$ が必要十分である。最小の $a_{0}$ は $q = 1, r = m + 1$ のときで， $a_{0} = 2^{m + 1} - 1$ である。

(1)

$a_{0}, a_{1}, a_{2}, a_{3}$ がすべて奇数であるには $m = 3$ とすればよい。したがって最小値は $2^{4} - 1 = 15$ である。

(2)

$a_{0}, a_{1}, \dots, a_{10}$ がすべて奇数であるには $m = 10$ とすればよい。したがって最小値は $2^{11} - 1 = 2047$ である。

京都大学 2024年度理系数学 第4問

問題

方針

解答

(1)

(2)

京都大学 2024年度
理系数学第4問