京都大学理系 2024 年・第 4 問

与えられた自然数 a_0 に対して,自然数からなる数列 a_0,a_1,a_2,\cdots を次のように定める。

a_{n+1} = \dfrac{a_n}{2}(a_n が偶数のとき)

a_{n+1} = \dfrac{3a_n+1}{2}(a_n が奇数のとき)

次の問いに答えよ。

(1) a_0,a_1,a_2,a_3 がすべて奇数であるような最小の自然数 a_0 を求めよ。

(2) a_0,a_1,\cdots,a_{10} がすべて奇数であるような最小の自然数 a_0 を求めよ。

奇数が続くあいだは下の式しか使わない

a_0 を決めると数列は決まります。偶数なら半分にし、奇数なら \dfrac{3a_n+1}{2} にします。

たとえば a_0 = 7 なら 7 \to 11 \to 17 \to 26 で、a_2 までが奇数、a_3 で偶数に落ちます。

聞かれているのは奇数が何個続くかです。続いているあいだは下の式しか通らないので、下の式だけを調べれば足ります。

a_0 を 1 ずつ増やして数えていく手も (1) までは通りますが、(2) の a_0 は 4 桁になるので間に合いません。

1 を足すと \dfrac{3}{2} 倍になる

奇数のときの式の両辺に 1 を足します。a_{n+1}+1 = \dfrac{3a_n+1}{2}+1 = \dfrac{3a_n+3}{2} = \dfrac{3}{2}(a_n+1) です。

a_n そのものは扱いにくい形でしたが、a_n+1 は \dfrac{3}{2} 倍ずつ増えるだけになりました。

奇数が続くあいだこの関係が続くので、a_n+1 = \left(\dfrac{3}{2}\right)^n (a_0+1)、つまり a_n = \dfrac{3^n}{2^n}(a_0+1)-1 です。

3^n は奇数なので、2 で何回割れるかを決めているのは a_0+1 だけです。

a_0+1 が 2 で何回割れるか

a_n が奇数であることは、a_n+1 が偶数であることと同じです。

a_n+1 = \dfrac{3^n(a_0+1)}{2^n} ですから、これが偶数になるのは a_0+1 が 2^{n+1} で割り切れるときです。

a_0 から a_k までを全部奇数にしたいなら、いちばんきつい n = k を満たせば足ります。条件は a_0+1 が 2^{k+1} の倍数であることです。

逆に a_0+1 が 2^{k+1} の倍数なら、n = 0 から n = k まで a_n+1 はどれも偶数になり、その範囲の a_n はすべて奇数になります。

答えは 15 と 2047

(1) は a_3 までなので k = 3 です。a_0+1 が 2^4 = 16 の倍数、最小の自然数は a_0 = 2^4-1 = 15 です。

たしかめると 15 \to 23 \to 35 \to 53 で 4 つとも奇数、次は \dfrac{3 \cdot 53+1}{2} = 80 で偶数です。

(2) は a_{10} までなので k = 10 です。a_0+1 が 2^{11} = 2048 の倍数、最小は a_0 = 2^{11}-1 = 2047 です。

このとき a_n+1 = 2^{11-n} \cdot 3^n で、2 の指数が 1 ずつ減っていきます。n = 11 で指数が 0 になり、そこではじめて a_n が偶数になります。

2026
2025
2024
2023
2022
2021