京都大学 理系 2024年度 第4問 解説
問題編
問題
与えられた自然数 $a_0$ に対して、自然数からなる数列 $a_0,a_1,a_2,\cdots$ を次のように定める。
\begin{eqnarray} a_{n+1} = \begin{cases} \dfrac{a_n}{2} & ( a_n \ \textsf{が偶数のとき} ) \\[5pt] \dfrac{3a_n+1}{2} & ( a_n \ \textsf{が奇数のとき} ) \\[5pt] \end{cases} \end{eqnarray}次の問いに答えよ。(1) $a_0$, $a_1$, $a_2$, $a_3$ がすべて奇数であるような最小の自然数 $a_0$ を求めよ。
(2) $a_0$, $a_1$, $\cdots$, $a_{10}$ がすべて奇数であるような最小の自然数 $a_0$ を求めよ。
考え方
$a_0$ から順番にしらみつぶしにやっていく方法では、(1)ができても(2)が間に合いません。しかし、よく考えると、 $a_0$ を決めてまじめに計算していく必要はありません。ぜんぶ奇数になるなら、下側の式をずっと使うんだから、下側の漸化式についてよく考えればいいことがわかります。
解答編
問題
与えられた自然数 $a_0$ に対して、自然数からなる数列 $a_0,a_1,a_2,\cdots$ を次のように定める。
\begin{eqnarray} a_{n+1} = \begin{cases} \dfrac{a_n}{2} & ( a_n \ \textsf{が偶数のとき} ) \\[5pt] \dfrac{3a_n+1}{2} & ( a_n \ \textsf{が奇数のとき} ) \\[5pt] \end{cases} \end{eqnarray}次の問いに答えよ。(1) $a_0$, $a_1$, $a_2$, $a_3$ がすべて奇数であるような最小の自然数 $a_0$ を求めよ。
(2) $a_0$, $a_1$, $\cdots$, $a_{10}$ がすべて奇数であるような最小の自然数 $a_0$ を求めよ。
解答
$a_0$ が奇数の場合だけを考えればよい。
$n=m$ のときにはじめて偶数になるとする。つまり、 $a_0,a_1,\cdots,a_{m-1}$ が奇数で、 $a_m$ が偶数であるとする。このとき、 $n=0,1,2,\cdots,m-1$ に対して\[ a_{n+1}=\frac{3a_n+1}{2} \]が成り立つ。このとき
\begin{eqnarray}
a_{n+1}+1 &=& \frac{3a_n+1}{2}+1 \\[5pt]
a_{n+1}+1 &=& \frac{3}{2} (a_n+1) \\[5pt]
\end{eqnarray}なので、 $n=0,1,2,\cdots,m-1,m$ に対して\[ a_n=\frac{3^n}{2^n}(a_0+1)-1 \]が成り立つ。 $a_0,a_1,\cdots,a_{m-1}$ が奇数だから、 $a_0+1$ は $2^0,2^1,\cdots,2^{m-1}$ で割り切れて商は偶数である。つまり、 $a_0+1$ は $2^m$ の倍数である。また、 $a_m$ は偶数なので、 $a_0+1$ は $2^{m}$ で割り切れて商は奇数である。
以上から。 $a_0+1$ は $2^m\times$(奇数) とかける。また、作り方から、逆に $a_0+1$ が $2^m\times$(奇数) とかけるとき、 $n=m$ ではじめて $a_n$ は偶数になることがわかる。
(1) $n=4$ 以降で偶数になればいいので、条件を満たすのは $a_0+1$ が $2^4$ の倍数のときであり、最小の $a_0$ は $2^4-1=15$ …（答）
(2) $n=11$ 以降で偶数になればいいので、条件を満たすのは $a_0+1$ が $2^{11}$ の倍数のときであり、最小の $a_0$ は $2^{11}-1=2047$ …（答）
