東大 2014年度理系数学第5問｜問題・解答・解説

方針

(1) から (3) は文科第4問と同じく、余りだけで漸化式を追い、非零の共通余りを素数 $p$ のもとで割り戻す。(4) は背理法を用いる。もし $a_{1}$ が $p$ で割り切れるなら $b_{1} = 0$ 、一方で仮定から $b_{k} > 0$ が $k ≧ 2$ で成り立つ。有限個しかない正の余りの隣接ペア $(b_{k}, b_{k + 1})$ を考えると同じペアが現れるので、(3) を1つずつ過去へ戻して $b_{1}$ が後の正の余りに等しいという矛盾を導く。

解答

(1) $b_{n}$ は $a_{n}$ を $p$ で割った余りであるから $a_{n} \equiv b_{n} (m o d p), a_{n + 1} \equiv b_{n + 1} (m o d p)$ である。したがって $a_{n} + 1 \equiv b_{n} + 1 (m o d p)$ であり、積をとって $a_{n + 1} (a_{n} + 1) \equiv b_{n + 1} (b_{n} + 1) (m o d p)$ を得る。

漸化式より $a_{n + 2} = a_{n + 1} (a_{n} + 1)$ であるから、 $a_{n + 2}$ を $p$ で割った余り $b_{n + 2}$ は、 $b_{n + 1} (b_{n} + 1)$ を $p$ で割った余りと一致する。

(2) $r = 2$ より $b_{1} = 2, b_{2} = 3$ である。(1) を用いて順に計算する。 $b_{3} \equiv 3 (2 + 1) = 9 (m o d 17)$ より $b_{3} = 9$ である。 $b_{4} \equiv 9 (3 + 1) = 36 \equiv 2 (m o d 17)$ より $b_{4} = 2$ である。 $b_{5} \equiv 2 (9 + 1) = 20 \equiv 3 (m o d 17)$ より $b_{5} = 3$ である。

ここで $(b_{4}, b_{5}) = (2, 3) = (b_{1}, b_{2})$ となったので、以後は同じ計算が繰り返される。したがって $\begin{array}{ccccccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ b_{n} & 2 & 3 & 9 & 2 & 3 & 9 & 2 & 3 & 9 & 2 \end{array}$ である。

(3) $b_{n + 1} = b_{m + 1} > 0, b_{n + 2} = b_{m + 2}$ とする。 $c = b_{n + 1} = b_{m + 1}$ とおくと、 $c$ は $p$ で割った余りであり、 $0 < c < p$ である。

(1) より $b_{n + 2} \equiv c (b_{n} + 1) (m o d p)$ であり、同様に $b_{m + 2} \equiv c (b_{m} + 1) (m o d p)$ である。 $b_{n + 2} = b_{m + 2}$ だから $c (b_{n} + 1) \equiv c (b_{m} + 1) (m o d p)$ すなわち $c (b_{n} - b_{m}) \equiv 0 (m o d p)$ である。 $p$ は素数で、 $0 < c < p$ だから $c$ は $p$ で割り切れない。よって $b_{n} - b_{m} \equiv 0 (m o d p)$ である。 $b_{n}, b_{m}$ はどちらも $0$ 以上 $p - 1$ 以下なので $b_{n} = b_{m}$ である。

(4)

背理法で示す。 $a_{1}$ が $p$ で割り切れると仮定する。このとき $b_{1} = 0$ である。一方、問題の仮定より $a_{2}, a_{3}, a_{4}, \dots$ には $p$ で割り切れる数が現れないので $b_{k} > 0 (k ≧ 2)$ である。 $k ≧ 2$ について、隣接する2つの余りの組 $(b_{k}, b_{k + 1})$ を考える。各成分は $1, 2, \dots, p - 1$ のいずれかであるから、このような組は高々 $(p - 1)^{2}$ 通りしかない。したがって無限に続く組 $(b_{2}, b_{3}), (b_{3}, b_{4}), (b_{4}, b_{5}), \dots$ の中には、同じ組が2回現れる。すなわち、ある $2 ≦ n < m$ が存在して $b_{n} = b_{m}, b_{n + 1} = b_{m + 1}$ となる。

ここで $b_{n} = b_{m} > 0$ かつ $b_{n + 1} = b_{m + 1}$ であるから、(3) を添字 $n - 1, m - 1$ に適用すると $b_{n - 1} = b_{m - 1}$ が従う。さらに $b_{n - 1} > 0$ であれば、同じ議論を1つ前の添字に繰り返せる。 $n ≧ 2$ なので、この操作を順に行うと $b_{1} = b_{m - n + 1}$ を得る。

ところが $m - n + 1 ≧ 2$ であるから、仮定より $b_{m - n + 1} > 0$ である。一方、最初に仮定した通り $b_{1} = 0$ である。これは矛盾である。

したがって $a_{1}$ は $p$ で割り切れない。すなわち $a_{1} も p で割り切れない$ である。

総評

難度7、計算量6。目安時間は28分。(1) から (3) は剰余漸化式の基本操作だが、(4) は有限性と逆向き一意性を組み合わせる発想が必要である。 $a_{2}$ 以降が $p$ で割り切れないという仮定から、 $b_{k} > 0$ の隣接ペアが有限集合内を動くと見る。重複したペアを見つけた後、(3) を過去方向へ反復して $b_{1} = 0$ と後の正の余りが等しい矛盾に持ち込むのが採点上の核心である。

出典: 東京大学 2014年度前期第2次学力試験数学（大学公式の問題PDF）。問題文はHTML表示のために再入力・数式組版しています。

東京大学 2014年度 前期日程 第2次学力試験理系数学 第5問

方針

解答

総評

東京大学 2014年度前期日程第2次学力試験理系数学第5問