Mongolian Mathematical Olympiad

Suppose that $a_0,a_1,\dots ,a_{mn-1}$ is a nice sequence, where we take indices modulo $mn$. First of all, we claim that if $a_t=\max \{a_0,a_1,\dots ,a_{mn-1}\}$ then $a_{t+1-m}=a_{t+1},a_{t+2-m}=a_{t+2},\dots ,a_{t-1}=a_{t+(m-1)}$ (call these $2(m-1)$ terms $(m-1)$-pairs). Let $S_i=a_i+\cdots +a_{i+m-1}$ for each $0\le i\le mn-1$. Then $S_{i+1}-S_i=a_{i+m}-a_i$. If there are indices $t-m+1\le i,j\le t$ such that $S_i>S_j$ then $S_i-S_j\ge S_j(m-1)$ since $S_i$ and $S_j$ are powers of $m$. Therefore, it follows from $m{a}_t\ge S_i>S_j>a_t$ that $$m{a}_t-a_t\ge S_i-S_j\ge S_j(m-1)>a_t(m-1),$$ a contradiction. Thus $S_{t-m+1}=S_{t-m+2}=\cdots =S_t$ and hence $a_i=a_{m+i}$ for each $t-m+1\le i\le t-1$.

(1) Let $k\ge 2$ and let $a_0,a_1,\dots ,a_{mk-1}$ be a nice sequence. Denote by $a_t$ the largest term of the sequence and delete the terms $a_t,a_{t+1},\dots ,a_{t+m-1}$ in the given sequence. Then the remaining sequence $a_0,a_1,\dots ,a_{t-1},a_{t+m},a_{s+m+1},\dots ,a_{mk-1}$ is nice by the claim.

(2) From the claim and (1), it follows that the number of $(m-1)$-pairs in a given nice sequence is at least $m-1$. Therefore, there are $(m-1{)}^2$ pairs of the form $(a_i,a_{i+m})$ with $a_i=a_{i+m}$. Now consider the remainders, modulo $m$, of the indices of all $(m-1)$-pairs in the sequence. By the pigeonhole principle, there is a remainder $j$ modulo $m$ such that the number of pairs whose indices are exactly $j$ modulo $m$ is at least $[(m-1{)}^2/m]+1=m-1$. Let $(a_{k_i},a_{k_i+m})$ be such pairs, i.e., $a_{k_i}=a_{k_i+m}$, $k_i<k_{i+1}$ and $k_i\equiv j(\mathrm{mod}m)$ for each $1\le i\le m-1$. Since $m^2>j_{m-1}+m$ and $$k_{m-1}+m=m+k_1+\sum _{i=2}^{m-1}(k_i-k_{i-1})=m+k_1+m\sum _{i=2}^{m-1}\frac{k_i-k_{i-1}}{m}$$ we obtain $k_i-k_{i-1}=m$ for each $i$. Thus $a_{k_1}=a_{k_2}=\cdots =a_{k_{m-1}}=a_{k_{m-1}+m}$, completes the proof.