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 + \dots + 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} = \dots = 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 \pmod 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} = \dots = a_{k_{m-1}} = a_{k_{m-1}+m}$, completes the proof.