2018年度 京大特色 第4問(2)

整数 受験数学

2018年度 京大特色 第4問(2)の解答です。

問題

自然数kとnは互いに素で,k\lt nを満たすとする。n項からなる数列a_{1}, a_{2},\cdots a_{n} が次の3条件(イ),(ロ),(ハ)を満たすとき,性質\mbox{P}(k,n)を持つということにする。

(イ) a_{1}, a_{2},\cdots a_{n} はすべて整数。

(ロ) 0\leq a_{1}\lt a_{2}\lt\cdots\lt a_{n}\lt 2^{n}-1

(ハ) a_{n+1},\cdots ,a_{n+k} を a_{n+j}=a_{j}\,\,\,(1\leq j\leq k) で定めたとき,n以下のすべての自然数mに対して 2a_{m}-a_{m+k}は2^{n}-1 で割り切れる。

(1) k=2かつn=5の場合を考える。性質\mbox{P}(2,5)を持つ数列a_{1},a_{2},\cdots,a_{5}をすべて求めよ。

(2) 数列a_{1}, a_{2},\cdots a_{n} が性質\mbox{P}(k,n)を持つとする。a_{k+1}-a_{k}=1 であることを示せ。

まさに(1)で実験をして(2)に持っていくというスタイルです。(ですが(1)の解答は省略します。)

解答

正の整数 p,q に対して, p\equiv q \,\,\, (\mbox{mod} n) ならば a_p=a_q となるように定めてもよい。m=1,2,\cdots ,n-k であれば, 条件(ロ)より 不等式 { -(2^{n}-1) \lt 0-a_{n} \leq 2a_{m}-a_{n}\leq 2a_{m}-a_{m+k} \lt 2a_{m}-a_{m} = a_m \lt 2^{n}-1 } が成立し, 条件(ハ)より 2^{n}-1|2a_{m} - a_{m+k} であるため,

2a_{m}-a_{m+k}=0 \,\,\,(m=1,2,\cdots ,n-k)

が成立する。同様に, m=n-k+1, n-k+2, \cdots ,n であるときは,不等式

0\le a_{m+k}=2a_{m+k}-a_{m+k}\lt 2a_m-a_{m+k}\lt 2a_{m}\lt 2(2^{n}-1) \tag{1}

が成り立ち,さらに 2^{n}-1|2a_{m}-a_{m+k} であるから, \begin{eqnarray} 2a_m-a_{m+k}=2^{n}-1\,\,\, (m=n-k+1, n-k+2,\cdots n) \tag{2} \end{eqnarray} が成立する。正の整数 i に対して, b_iを b_i=a_{i+1}-a_i と置く。

この際, p\equiv q \,\,\,(\mbox{mod} n) ならば b_p=b_q であることに注意する。

(1),(2) を用いて数列 a_1,a_2,\cdots の階差をとるように引くと {} $$ 2b_{m}-b_{m+k} = \left\{ \begin{array}{} 0 & (1\leq m\leq n, m\neq n-k)\\ 2^{n}-1 & (m=n-k) \end{array} \right.\tag{3} $$

という式を得る。1\le m\le n, m\neq n-kのとき, n,k が互いに素であることから, ある 2\leq r\leq n-1 を満たす整数 rであって, m\equiv (r-1)k\,\,\, (\mbox{mod} n)を満たすものがただ一つ存在する。また,m=n-kのときは m\equiv (n-1)k\,\,\, (\mbox{mod} n) であるから,r=n と定める。このような $r$ を用いて$(3)$は

${}$ $$ 2b_{m}-b_{m+k} = 2b_{(r-1)k}-b_{rk}= \left\{ \begin{array}{} 0 & (2\leq r\leq n-1)\\ 2^{n}-1 & (r=n) \end{array} \right.\tag{4} $$

と同値である。$(4)$ で $r=2,3,\cdots n-1$ の場合, $b_{rk}=2b_{(r-1)k}$ となり, 右辺に更に式を適用させることで

$b_{rk}=2b_{(r-1)k}=4b_{(r-2)k}= \cdots =2^{r-1}b_k$

を得る。この結果とr=nの場合の式から b_{nk}=2b_{(n-1)k}-(2^{n}-1) = 2\times2^{(n-1)-1}b_k -(2^{n}-1)=2^{n-1}b_k-(2^{n}-1) を得る。これらの式をr=2,3,\cdots, n について足せば \displaystyle\sum_{r=2}^{n}b_{rk}=\left(\displaystyle\sum_{r=2}^{n}2^{r-1}\right)b_k -(2^{n}-1)

となり, 両辺に b_{1k}=2^{1-1}b_k を加えて整理することで

\displaystyle\sum_{r=1}^{n}b_{rk}=\left(\displaystyle\sum_{r=1}^{n}2^{r-1}\right)b_{k} -(2^{n}-1)=(2^{n}-1)(b_{k}-1)

となる。n,k は互いに素であることより 数列 k,2k,\cdots,rk\cdots,(n-1)k,nkは 数列 1,2,3,\cdots i \cdots,n-1,n のある置換になっているので

\displaystyle\sum_{r=1}^{n}b_{rk}=\displaystyle\sum_{i=1}^{n}b_{i}=\displaystyle\sum_{i=1}^{n}(a_{i+1}-a_{i})=0

以上より 0=(2^{n}-1)(b_k-1) となるから,b_k=a_{k+1}-a_k=1 (証明終)

コメント

分野的には整数問題ですが,京大などの一般入試の整数と比べても非常に難しい。n,kが互いに素という条件の扱い方が特に。どちゃ楽評価は☆10ぐらいでしょうか。ですが結果はとても美しく,「整数論の本気」と表現したくなるぐらいです。京大特色、恐るべし……… あとはてなブログのtexクソ使いにくい…挫折しそう…