2023年 日本数学オリンピック本選 第３問 解答例
$${c}$$を非負整数とする。正の整数からなる数列$${a_1, a_2, \cdots}$$であって、正の整数$${n}$$に対して次の条件をみたすものをすべて求めよ。
$${a_i\leqq a_{n+1} + c}$$をみたす正の整数$${i}$$がちょうど$${a_n}$$個存在する。
考え方：
条件がややこしくて混乱しますが、
丁寧に紐解けば$${\{a_i\}}$$が狭義単調増加であることが導けます。
$${\{a_i\}}$$が公差$${1}$$の等差数列で条件を満たすものがあるのはわかるので、
$${i}$$が$${1}$$増えた時に$${a_i}$$が$${2}$$以上増えることがあるかを調べてみると、
なかなかうまくいかないことがわかります。
これをうまく言語化する方法を考えましょう。
$${a_{k+1}}$$と$${a_k}$$の差が大きいとき、
$${a_{k+2}+ c}$$と$${a_{k+1} +c}$$の間にたくさんの$${a_i}$$が入る余地が必要なことから、
$${a_{k+2}}$$と$${a_{k+1}}$$の差を大きくとる必要がありそうです。
これはどんどん伝搬していくので、
大きい$${i}$$において$${a_{i+1}-a_i}$$はどんどん大きくなります。
一方で、$${a_{k+2}+ c}$$と$${a_{k+1} +c}$$が決まった場合、
この２つの間にたくさんの$${a_i}$$を入れるには
大きい$${i}$$において$${a_{i+1}-a_i}$$を小さくしたくなります。
この相反する２つの要素を正確に表現して、
範囲を絞れば解にたどり着けます。
解答例：
ある正の整数$${k}$$について$${a_k < a_{k+1}}$$とすると、
$${a_i\leqq a_k +c}$$なる$${i}$$の個数より
$${a_i\leqq a_{k+1} +c}$$なる$${i}$$の個数は多くなるため、
$${a_{k-1} < a_k}$$である。
また、$${a_i\leqq a_{k+1} +c}$$となる$${i}$$の個数より
$${a_i\leqq a_{k+2} +c}$$となる$${i}$$の個数が多くなる必要があるため、
$${a_{k+1} < a_{k+2}}$$となる。
つまり、$${a_1 < a_2 < \cdots}$$となる。
同様に、ある正の整数$${k}$$について$${a_k > a_{k+1}}$$とすると、
$${a_1 > a_2 > \cdots}$$となり、
ある正の整数$${k}$$について$${a_k = a_{k+1}}$$となるとき、
$${a_1 = a_2 = \cdots}$$となる。
$${a_1 = a_2 = \cdots}$$または$${a_1 > a_2 > \cdots}$$のとき、
$${a_i\leqq a_2 + c}$$を満たす$${i}$$の個数は無限となるため
条件に合わない。
よって、$${a_1 < a_2 < \cdots}$$である。
以下、任意の正の整数$${k}$$について$${m_k = a_{k+1} - a_k}$$とする。
$${a_i\leqq a_{k+2} +c}$$となる$${i}$$の個数は
$${a_i\leqq a_{k+1} +c}$$となる$${i}$$の個数より$${m_k}$$多い。
$${a_i}$$の中に値が重複するものはないため、
$${a_{k+1} + m_k \leqq a_{k+2} = a_{k+1} + m_{k+1}}$$が成り立つ。
よって、$${m_1 \leqq m_2 \leqq \cdots}$$である。
$${a_i\leqq a_{k+2} +c}$$となる$${i}$$の個数は
$${a_i\leqq a_{k+1} +c}$$となる$${i}$$の個数より多いので、
$${a_{k+1}+c < a_l \leqq a_{k+2} + c}$$となる整数$${l ( > k+1)}$$が存在する。
このとき、$${a_{k+2} + c = a_{k+1} + m_{k+1} + c}$$より、
$${a_{l+1} = a_l + m_l > a_{k+1} + c + m_{k+1} = a_{k+2} + c}$$
$${a_{l-1} = a_l - m_{l-1} \leqq a_{k+2} + c + m_{k+1} = a_{k+1} + c}$$
であるから、
$${a_{l-1} \leqq a_{k+1} + c < a_l \leqq a_{k+2} +c < a_{l+1}}$$
となるので、
$${a_{k+1}+c < a_l \leqq a_{k+2} + c}$$となる$${l}$$は1つしかない。
よって、すべての$${k}$$について$${m_k = 1}$$である。
つまり、$${a_k = a_1 + k -1}$$となる。
$${a_i \leqq a_2 + c}$$ を満たす$${i}$$が$${a_1}$$となるように$${a_1}$$を選ぶと
$${a_1 = c + 2}$$となる。
よって答えは$${a_k = c + k + 1}$$
お知らせ：
少しでも興味深い、楽しいと感じたらぜひスキやコメント、フォローください！
他に公開している記事などの一覧はこちら
ぜひ初めに見てください。｜光捷 (note.com)
この記事が気に入ったらサポートをしてみませんか？