ねしゃ～のブログ

数学オリンピック本選2023 第3問

$f$ を $f(x)=$ ( $a_i\leq x+c$ となる $i$ の個数)として定義するとこれは広義単調増加である

数列のすべての項が等しいとすると $a_{n+1}+c$ 以下の $a_i$ の個数は $0$ または無数にあるから明らかに矛盾

ある $k$ において $a_k\gt a_{k+1}$ だと仮定すると、 $f(a_{k+1})=a_k,f(a_{k+2})=a_{k+1}$ であり $f$ の広義単調増加性から $a_{k+1}\gt a_{k+2}$ となるので帰納的に $a_k$ 以降は狭義単調減少、よって $a_{k+a_k}\leq 0$ より矛盾

したがって数列は広義単調増加

また同様にしてある $k$ において $a_k\lt a_{k+1}$ だと仮定すると、 $a_{k+1}\lt a_{k+2}$ が示せるから、 $a_i\lt a_{i+1}$ を満たす最も小さい $i+1$ を $m$ とおくと、帰納的に $m$ 項目以降は狭義単調増加であり $a_m$ 以上の項は数列内で高々1個

したがって $f$ は $x\geq a_m-c$ を満たす $x$ において $f(x+1)-f(x)\leq 1$

ゆえに任意の $i\geq m$ において、 $a_{i+1}-a_i=f(a_{i+2})-f(a_{i+1})\leq a_{i+2}-a_{i+1}$

したがって帰納的に任意の $j\gt i\geq m$ において、 $a_{i+1}-a_i\lt a_{j+1}-a_j\cdots (*)$

ここで $a_{l+1}-a_l\geq 2$ を満たす $l\geq m$ があったと仮定し $a_{l+1}-a_l=f(a_{l+2})-f(a_{l+1})=p\geq 2$ 、 $a_{l+2}-a_{l+1}=q\geq p$ とする

$a_{l+1}+c,a_{l+2}+c\geq a_{l+1}$ だから $(*)$ より $p=f(a_{l+2})-f(a_{l+1})\leq ( (a_{l+2}+c)-(a_{l+1}+c) ) /q=(a_{l+2}-a_{l+1})/q=q/q=1$ となり矛盾

したがって $m$ 項目以降は公差 $1$ の等差数列となる

広義単調増加性から $m$ 項目までは $a_{m+1}$ 以下であるので $1$ ～ $m+c+1$ 項目のみかつこれら全てが $a_{m+1}+c$ 以下となり、 $a_m=m+c+1$

同様に条件を満たすようにとっていくと、 $a_{m-1}=m+c,a_{m-2}=m+c-1,\dots ,a_{1}=c+2$ と順に定まる

したがって考えられる数列は初項 $c+2$ 公差 $1$ の等差数列のみであり、逆にこれが条件を満たすことは明らか