横浜国立大学 2018年度理系数学第4問解答・解説

問題

$c$ を $5$ で割り切れない $2$ 以上の整数とする。数列 ${a_{n}}, {b_{n}}$ は以下の条件をみたす。

(i) $a_{n} (n = 1, 2, 3, \dots)$ は $0, 1, \dots, c - 1$ のいずれかである。

(ii) $b_{n}$ は

b_{1} = 1, c b_{n + 1} = 5 a_{n} + b_{n} (n = 1, 2, 3, \dots)

をみたす整数である。

次の問いに答えよ。

(1) $c = 3$ のとき、 $a_{n}, b_{n} (n = 1, 2, 3, \dots)$ を求めよ。

(2) $n = 1, 2, 3, \dots$ に対して、 $0 < b_{n} < 5$ を示せ。

(3) $c = 5 l + 4$ （ $l$ は $0$ 以上の整数）のとき、 $a_{n}, b_{n} (n = 1, 2, 3, \dots)$ を求めよ。

出典：横浜国立大学 2018年度前期理系第4問

方針

解法1

$c$ と $5$ が互いに素であることから、 $c b_{n + 1} = 5 a_{n} + b_{n}$ の割り切れ条件で $a_{n}$ が一意に定まる。(2) は $0 < b_{n} < 5$ を仮定して次の $b_{n + 1}$ が $1, 2, 3, 4$ に入ることを帰納法で示す。(3) は $c \equiv - 1 (mod 5)$ を使って $b_{n}$ の交代を出す。

解法2

各 $b_{n} \in {1, 2, 3, 4}$ に対し、合同式 $5 a_{n} \equiv - b_{n} (mod c)$ の唯一の代表 $0 ≦ a_{n} < c$ を選ぶ「状態遷移」として数列を見る。(1)は4状態の表、(3)は2状態の直接計算で周期を確定する。

解答

解法1

(1)

$c = 3$ のとき、 $3 b_{n + 1} = 5 a_{n} + b_{n}$ であり、 $a_{n}$ は $0, 1, 2$ のいずれかである。よって

a_{n} \equiv b_{n} (mod 3)

をみたす $a_{n}$ が一意に定まる。 $b_{1} = 1$ から

(a_{1}, b_{2}) = (1, 2), (a_{2}, b_{3}) = (2, 4), (a_{3}, b_{4}) = (1, 3), (a_{4}, b_{5}) = (0, 1)

となるので、以後これを繰り返す。したがって

(a_{n}, b_{n}) = ⎩ ⎨ ⎧ (1, 1) (2, 2) (1, 4) (0, 3) (n \equiv 1 (mod 4)), (n \equiv 2 (mod 4)), (n \equiv 3 (mod 4)), (n \equiv 0 (mod 4))

である。

(2)

$c$ は $5$ で割り切れないから、 $5$ と $c$ は互いに素である。したがって $5 a_{n} + b_{n}$ が $c$ で割り切れるような $a_{n} \in {0, 1, \dots, c - 1}$ は一意に定まる。

$0 < b_{n} < 5$ と仮定する。このとき $0 ≦ a_{n} ≦ c - 1$ より

0 < 5 a_{n} + b_{n} < 5 c

である。さらに $5 a_{n} + b_{n} = c b_{n + 1}$ であるから、 $b_{n + 1}$ は整数で

0 < b_{n + 1} < 5

をみたす。 $b_{1} = 1$ であるから、数学的帰納法によりすべての $n$ で

0 < b_{n} < 5

である。

(3)

$c = 5 l + 4$ のとき $c \equiv - 1 (mod 5)$ である。 $c b_{n + 1} = 5 a_{n} + b_{n}$ を $5$ で割った余りで見ると

- b_{n + 1} \equiv b_{n} (mod 5)

である。(2)より $b_{n}, b_{n + 1}$ は $1, 2, 3, 4$ のいずれかなので、 $b_{n + 1}$ は $5 - b_{n}$ に等しい。 $b_{1} = 1$ から

b_{n} = {14 (n が奇数), (n が偶数)

である。

したがって、 $n$ が奇数のとき

a_{n} = \frac{c b _{n + 1} - b _{n}}{5} = \frac{4 c - 1}{5} = 4 l + 3

であり、 $n$ が偶数のとき

a_{n} = \frac{c b _{n + 1} - b _{n}}{5} = \frac{c - 4}{5} = l

である。よって

(a_{n}, b_{n}) = {(4 l + 3, 1) (l, 4) (n が奇数), (n が偶数)

である。

解法2

(1)

$c = 3$ のとき

5 a_{n} + b_{n} \equiv 0 (mod 3)

である。 $5 \equiv 2 (mod 3)$ だから

a_{n} \equiv b_{n} (mod 3) .

後の (2) と同じ評価から $b_{n} \in {1, 2, 3, 4}$ であり、各状態の遷移は

b_{n} 1243 a_{n} 1210 b_{n + 1} 2431

となる。 $b_{1} = 1$ からこの表をたどれば

(a_{n}, b_{n}) = ⎩ ⎨ ⎧ (1, 1) (2, 2) (1, 4) (0, 3) (n \equiv 1 (mod 4)), (n \equiv 2 (mod 4)), (n \equiv 3 (mod 4)), (n \equiv 0 (mod 4)) .

(2)

$5 ∤ c$ なので $g cd (5, c) = 1$ である。したがって、各整数 $b_{n}$ に対して

5 a_{n} \equiv - b_{n} (mod c)

を満たす $a_{n} \in {0, 1, \dots, c - 1}$ はただ1つ存在する。

いま $1 ≦ b_{n} ≦ 4$ とする。すると

0 < 5 a_{n} + b_{n} ≦ 5 (c - 1) + 4 = 5 c - 1 < 5 c .

しかも $5 a_{n} + b_{n} = c b_{n + 1}$ だから

0 < b_{n + 1} < 5.

初項 $b_{1} = 1$ から帰納的に

0 < b_{n} < 5

がすべての $n$ で成り立つ。

(3)

$c = 5 l + 4$ とする。 $b_{n} = 1$ のとき

5 (4 l + 3) + 1 = 20 l + 16 = 4 c

だから、一意性により

a_{n} = 4 l + 3, b_{n + 1} = 4.

一方、 $b_{n} = 4$ のとき

5 l + 4 = c

だから

a_{n} = l, b_{n + 1} = 1.

初項が $b_{1} = 1$ なので、この2状態が交互に現れる。よって

(a_{n}, b_{n}) = {(4 l + 3, 1) (l, 4) (n が奇数), (n が偶数) .

なお

0 ≦ l < c, 0 ≦ 4 l + 3 < 5 l + 4 = c

なので、得られた $a_{n}$ は指定された範囲にも入っている。

横浜国立大学 2018年度理系数学 第4問

問題

方針

解法1

解法2

解答

解法1

(1)

(2)

(3)

解法2

(1)

(2)

(3)

横浜国立大学 2018年度
理系数学第4問