International Mathematical Olympiad Shortlisted Problems

For every indices $m⩽n$ we will denote $S(m,n)=a_m+a_{m+1}+\cdots +a_{n-1}$; thus $S(n,n)=0$. Let us start with the following lemma.

Lemma. Let $b_0,b_1,\dots$ be an infinite sequence. Assume that for every nonnegative integer $m$ there exists a nonnegative integer $n\in [m+1,m+r]$ such that $b_m=b_n$. Then for every indices $k⩽\ell$ there exists an index $t\in [\ell ,\ell +r-1]$ such that $b_t=b_k$. Moreover, there are at most $r$ distinct numbers among the terms of $(b_i)$.

Proof. To prove the first claim, let us notice that there exists an infinite sequence of indices $k_1=k,k_2,k_3,\dots$ such that $b_{k_1}=b_{k_2}=\cdots =b_k$ and $k_i<k_{i+1}⩽k_i+r$ for all $i⩾1$. This sequence is unbounded from above, thus it hits each segment of the form $[\ell ,\ell +r-1]$ with $\ell ⩾k$, as required.

To prove the second claim, assume, to the contrary, that there exist $r+1$ distinct numbers $b_{i_1},\dots ,b_{i_{r+1}}$. Let us apply the first claim to $k=i_1,\dots ,i_{r+1}$ and $\ell =\max \{i_1,\dots ,i_{r+1}\}$; we obtain that for every $j\in \{1,\dots ,r+1\}$ there exists $t_j\in [s,s+r-1]$ such that $b_{t_j}=b_{i_j}$. Thus the segment $[s,s+r-1]$ should contain $r+1$ distinct integers, which is absurd.

Setting $s=0$ in the problem condition, we see that the sequence $(a_i)$ satisfies the condition of the lemma, thus it attains at most $r$ distinct values. Denote by $A_i$ the ordered $r$-tuple $(a_i,\dots ,a_{i+r-1})$; then among $A_i$'s there are at most $r^r$ distinct tuples, so for every $k⩾0$ two of the tuples $A_k,A_{k+1},\dots ,A_{k+r^r}$ are identical. This means that there exists a positive integer $p⩽r^r$ such that the equality $A_d=A_{d+p}$ holds infinitely many times. Let $D$ be the set of indices $d$ satisfying this relation.

Now we claim that $D$ coincides with the set of all nonnegative integers. Since $D$ is unbounded, it suffices to show that $d\in D$ whenever $d+1\in D$. For that, denote $b_k=S(k,p+k)$. The sequence $b_0,b_1,\dots$ satisfies the lemma conditions, so there exists an index $t\in [d+1,d+r]$ such that $S(t,t+p)=S(d,d+p)$. This last relation rewrites as $S(d,t)=S(d+p,t+p)$. Since $A_{d+1}=A_{d+p+1}$, we have $S(d+1,t)=S(d+p+1,t+p)$, therefore we obtain $$a_d=S(d,t)-S(d+1,t)=S(d+p,t+p)-S(d+p+1,t+p)=a_{d+p}$$ and thus $A_d=A_{d+p}$, as required.

Finally, we get $A_d=A_{d+p}$ for all $d$, so in particular $a_d=a_{d+p}$ for all $d$, QED.