MO ARCHIVE
問題一覧/EGMO 2020/PROBLEM 1

MATHEMATICAL OLYMPIAD ARCHIVE

EGMO 2020
問題 1

DIFFICULTY1
EGMO 2020 問題1の英語問題文

PROBLEM WORKSPACE

ヒント

PUBLIC
ヒント 1

愚直に v2(an)v_2(a_n) を追いかけましょう．

略解

略解を表示

aia_i が 22 で割り切れる最大の回数を bnb_n とすると以下が成り立つ．

{bn+1−bn<2⟹bn+2−bn+1=−1bn+1−bn>2⟹bn+2−bn+1<−1bn+1−bn=2⟹bn+2−bn+1≥0\begin{cases} 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}

特に bn+1−bn≤0⟹bn+2−bn+1<0b_{n+1}-b_n\leq 0\Longrightarrow b_{n+2}-b_{n+1}\lt 0 なので，ある 0≤M≤30300\leq M\leq 3030 が存在して，b0,b1,b2,…,bMb_0,b_1,b_2,\dots,b_M は広義単調増加，bM,bM+1,…,b3030b_M,b_{M+1},\dots,b_{3030} は狭義単調減少である．


i=0,1,…,M−2i=0,1,\dots,M-2 に対して bn+2−bn+1≥0b_{n+2}-b_{n+1}\geq 0 であるために，bn+1−bn=2b_{n+1}-b_n=2 が必要なので bM−1=b0+2(M−1)≥2M−2b_{M-1}=b_0+2(M-1)\geq 2M-2 を得る．これと，bM≥b3030+(3030−M)≥3030−Mb_M\geq b_{3030}+(3030-M)\geq 3030-M より，

max⁡{bM−1,bM}≥max⁡{2M−2,3030−M}≥2020\max\{b_{M-1},b_M\}\geq \max\{2M-2,3030-M\}\geq 2020

なので題意は示された．

← 問題一覧に戻る