EGMO 2020
問題 1

$a_i$ が $2$ で割り切れる最大の回数を $b_n$ とすると以下が成り立つ．

b_{n+1}-b_n\lt 2\Longrightarrow b_{n+2}-b_{n+1}=-1\\ b_{n+1}-b_n\gt 2\Longrightarrow b_{n+2}-b_{n+1}\lt-1\\ b_{n+1}-b_n= 2\Longrightarrow b_{n+2}-b_{n+1}\geq 0\\ \end{cases}$$ 特に $b_{n+1}-b_n\leq 0\Longrightarrow b_{n+2}-b_{n+1}\lt 0$ なので，ある $0\leq M\leq 3030$ が存在して，$b_0,b_1,b_2,\dots,b_M$ は広義単調増加，$b_M,b_{M+1},\dots,b_{3030}$ は狭義単調減少である． $i=0,1,\dots,M-2$ に対して $b_{n+2}-b_{n+1}\geq 0$ であるために，$b_{n+1}-b_n=2$ が必要なので $b_{M-1}=b_0+2(M-1)\geq 2M-2$ を得る．これと，$b_M\geq b_{3030}+(3030-M)\geq 3030-M$ より，

\max{b_{M-1},b_M}\geq \max{2M-2,3030-M}\geq 2020

$$なので題意は示された．$$