【解答速報】京大理系数学2024第4問

問題

与えられた自然数$${a_0}$$に対して, 自然数からなる数列$${a_0, a_1, a_2, …}$$を次のように定める.

$$
a_{n+1} =
\begin{cases}
\cfrac{a_n}{2} & (a_nが偶数のとき)\\
\cfrac{3a_n+1}{2} &  (a_nが奇数のとき)
\end{cases}
$$

次の問いに答えよ.

(1) $${a_0, a_1, a_2, a_3}$$がすべて奇数であるような最小の自然数$${a_0}$$を求めよ.
(2) $${a_0, a_1, … , a_{10}}$$がすべて奇数であるような最小の自然数$${a_0}$$を求めよ.

解説

(1)

実験しながら進めていきます。まず、$${a_0}$$が奇数のとき$${a_1}$$も奇数であるための条件は

$$
a_1 = \frac{3a_0+1}{2} \equiv1\pmod2
$$

と表すことができ、これは

$$
3a_0 + 1 = 2 \pmod4
$$

すなわち

$$
a_0 = -1\pmod4
$$

と同値です。最初の変形は、$${(3a_0+1)/2 = 2n+1}$$と$${3a_0+1 = 4n+2}$$が同値であることからわかります。したがって、$${a_0}$$と$${a_1}$$が奇数であるための必要十分条件は$${a_0=-1\pmod4}$$となります。

同様のことを繰り返し行えば、$${a_3}$$まですべて奇数である条件も調べられます。$${a_2}$$が奇数のとき、$${a_3}$$が奇数であるための条件は

$$
a_2 = \frac{3a_1+1}{2}\equiv-1\pmod4\\
$$

より

$$
\begin{array}{rll}
{3a_1+1}&\equiv-2\pmod8\\
a_1 &\equiv -1\pmod8
\end{array}
$$

となり、同様にして

「$${a_0}$$が奇数のとき$${a_1 \equiv -1\pmod8}$$を満たすための条件は$${a_0 \equiv -1\pmod{16}}$$」

ということが分かります。以上より、$${a_3}$$まですべて奇数である条件は$${a_0=-1\pmod{16}}$$であり、求めるのはこの条件を満たす最小の自然数$${a_0}$$なので、答えは$${\bm{a_0=15}}$$です。

(2)

(1)で見えてきた規則性を利用します。この規則を厳密に表現すると、「$${a_k(l\leqq k\leqq m)}$$が奇数であるための必要十分条件は、$${a_{l}\equiv-1\pmod{2^{k-l+1}}}$$が成り立つこと」となります。

この事実を用いると、$${a_{0}}$$から$${a_{10}}$$まですべて基数である奇数である条件は$${a_{0}\equiv-1\pmod{2^{11}}}$$なので、求める最小の値は$${\bm{a_0=2047}}$$となります。