2017年 日本数学オリンピック本選 第２問 解答例
$${N}$$を正の整数とする。正の整数$${a_1, a_2,\cdots ,a_N}$$が与えられており、これらはいずれも$${2^{N+1}}$$の倍数ではない。$${N+1}$$以上の整数$${n}$$について、$${a_n}$$を次のように順次定める：
$${k = 1, 2, \cdots, n-1}$$の中で$${a_k}$$を$${2^n}$$で割った余りが
最も小さくなるような$${k}$$を選び、$${a_n=2a_k}$$とする。
ただし、そのような$${k}$$が複数ある場合は、そのうち最も
大きい$${k}$$を選ぶ。
このとき、$${n\geqq M}$$においてつねに$${a_n=a_M}$$が成り立つような正の整数$${M}$$が存在することを示せ。
考え方：
説明のため、$${a_1, a_2, \cdots, a_N}$$の中で最小のものを$${a_{\text{min}}}$$とおきます。
余りが最も小さい$${a_k}$$として$${a_{\text{min}}}$$が一度選ばれると、
その後もずっと選ばれ続け、
新しく作られる$${a_n}$$は$${2a_{\text{min}}}$$となることは明らかです。
よって、$${n}$$が大きくなるとあるタイミングで必ず$${a_{\text{min}}}$$が選ばれることを示すことになります。
最初は余りが最も小さい$${a_k}$$として
$${a_{\text{min}}}$$以外のもの（$${a_{k_0}}$$とする）が選ばれるかもしれませんが、
$${n}$$が大きくなると、あるタイミングで$${a_{k_0}}$$が選ばれなくなること、
それまでに作られる$${a_n}$$も余りを小さくすることはないことがわかります。
つまり、選ばれる$${a_{k}}$$が次々に切り替わっていきながら
余りがどんどん大きくなり、
これが続いて最終的に必ず$${a_{\text{min}}}$$が選ばれるようになることを示します。
以上のイメージはそこまで難なくつかめると思います。
これを数学的に正確に表現することがやや面倒な問題でした。
以下の解答例では「操作」を定義し、これを繰り返すことで最終的に
$${a_{\text{min}}}$$が選ばれることを示しています。
解答例：
$${a_1, a_2, \cdots, a_{n-1}}$$の中で最小のものを$${a_{\text{min}}}$$とおく。
$${a_n = 2a_k > a_{\text{min}}}$$なので、
新たに作られる$${a_n}$$によらずこれは常に最小値となる。
正の整数を$${2^{n+1}}$$で割った余りが$${2^n}$$で割った余りより
小さくなることはないため、
ある$${n = M}$$に対して$${2^n}$$で割った余りが最小となるものとして
$${a_\text{min}}$$が選ばれると、
$${n\geqq M}$$なるすべての$${n}$$に対して$${a_\text{min}}$$が選ばれ$${a_n = a_M}$$となる。
よって、ある正の整数$${n_0}$$を十分大きくとることで、
$${2^{n_0}}$$で割った余りが最小となる$${a_k}$$が$${a_\text{min}}$$になることを示せばよい。
任意に取った$${n_0}$$に対し、$${k = 1, 2, \cdots, n_0-1}$$の中で
$${a_k}$$を$${2^{n_0}}$$で割った余りが最も小さいものを$${a_{k_0}}$$とし、
その余りを$${b_{n_0}}$$とおく。
$${a_{k_0} = a_{\text{min}}}$$の場合は明らかに条件を満たすので、
$${a_{k_0} \neq a_{\text{min}}}$$とする。
条件より$${b_{n_0}\leqq a_{\text{min}}}$$である。
任意の正の整数は0以上の整数$${p, q}$$を用いて
$${2^{p}(2q+1)}$$という形で一意に表すことができる。
よって、
$${a_{k_0} = 2^{n_0}\cdot 2^p(2q + 1) + b_{n_0} = 2^{n_0 + p + 1} + 2^{{n_0}+p} + b_{n_0}}$$
と書け、$${a_{k_0}}$$を$${n_0 + p +1}$$で割った余りは$${2^{{n_0}+p} + b_{n_0}}$$となり、
$${b_{n_0}}$$より大きくなる。
また、$${n_0\leqq n \leqq n_0+p}$$の範囲では
$${a_n = 2a_{k_0} = 2^{n_0 + p + 1} + 2b_{n_0}}$$となる。
これらを$${2^{n_0 + p + 1}}$$で割った余りは$${2b_{n_0}}$$であり、
$${b_{n_0}}$$より大きい。
そこで、$${n_0 + p + 1}$$を改めて$${n_0}$$とおき、
新しく求めた$${n_0}$$に対して$${k = 1, 2, \cdots, n_0-1}$$の中で
$${a_k}$$を$${2^{n_0}}$$で割った余りが最も小さいものを
改めて$${a_{k_0}}$$とおく操作を考える。
(i)
操作前の$${n_0, k_0}$$について$${2^{n_0 + p + 1}}$$で割った余りが$${b_{n_0}}$$となるような$${a_n}$$が
$${a_{k_0}}$$以外に存在しない場合、
操作によって$${b_{n_0}}$$は増加する。
(ii)
操作前の$${n_0, k_0}$$について$${2^{n_0 + p + 1}}$$で割った余りが$${b_{n_0}}$$となるような$${a_n}$$が
$${a_{k_0}}$$以外に存在する場合、
操作によって$${b_{n_0}}$$は変化せず$${k_0}$$が減少するが、
$${a_n}$$は項数が有限であるため、これを繰り返すことで、
(i)のケースに帰着する。
条件より$${b_{n_0} < a_{\text{min}}}$$となる場合であっても
操作を繰りかえすことにより$${b_{n_0} = a_{\text{min}}}$$となる$${n_0}$$を得る。
$${a_n}$$は項数が有限であるため、
更に操作を繰り返すことで$${k_0}$$を減らすことができ、
$${a_{k_0} = a_{\text{min}}}$$とすることができる。
お知らせ：
少しでも興味深い、楽しいと感じたらぜひスキやコメント、フォローください！
間違いを見つけた方は早めに連絡下さるとうれしいです。
他に公開している記事などの一覧はこちら
ぜひ初めに見てください。｜光捷 (note.com)