Great problem. Before I present my solution, two remarks: 1. I think the level of difficulty of this problem is larger than a typical A1. 2. Disappointed to see this was not chosen over the inequality problem for the contest. Oh well. Solution: Let $a_0+a_1+\cdots+a_n = k_n \cdot n$, where $k_n$ is an integral sequence (due to divisibility). A simple observation, that turns out to be useful, is $a_n\in\{1,2,\dots,n\}$ for $n\ge 1$. We compute the difference $k_{n+1}-k_n$: after some algebra, we obtain \[ k_{n+1}-k_n = \frac{na_{n+1}-S_n}{n(n+1)}\quad\text{where}\quad S_n = \sum_{0\le k\le n}a_k. \]We now claim $k_{n+1}-k_n\le 0$ for every $n$. To do so, note that \[ a_0+\cdots+a_n=k_n \cdot n \equiv -k_n\pmod{n+1} \implies a_{n+1}\equiv k_n\pmod{n+1}. \]Now, if $k_n\le n+1$, $a_{n+1}=k_{n+1}$. Otherwise, $a_{n+1}<k_n$ as $a_{n+1}\in\{1,2,\dots,n+1\}$. Hence, $a_{n+1}\le k_n$. This yields $k_{n+1}\le k_n$ for $n\ge 1$. Now, as $(k_n)_{n\ge 1}$ is a non-increasing sequence of positive integers (thus is bounded below), it must be eventually constant: there exists $N,c\in\mathbb{N}$ so that $k_n = c$ for $n\ge N$. Hence, $k_{n+1}-k_n=0$ for $n\ge N$, bringing $n a_{n+1}=S_n$ for $n\ge N$. Hence, $a_{N+1}=S_N/N$, \[ a_{N+2} = \frac{S_{N+1}}{N+1} = \frac{S_N+a_{N+1}}{N+1} = \frac{(N+1)a_{N+1}}{N+1} = a_{N+1}, \]and so on; hence the sequence is indeed constant from $N$ onwards.

This proof is probably similar to the above one, but I'm posting it regardless Main Claim: $\dfrac{a_0 + a_1 + \cdots + a_n}{n}$ is a non-increasing monovariant Observe that if this is not true, we have that $n(a_0 + \cdots + a_{n+1}) > (n+1)(a_0 + \cdots + a_n)$ Or $n a_{n+1} > a_0 + a_1 + \cdots + a_n$ However, since $a_0 + a_1 + \cdots + a_n + \dfrac{a_0 + a_1 + \cdots + a_n}{n} = \dfrac{a_0 + a_1 + \cdots + a_n}{n+1} \times (n+1)$ is a multiple of $n+1$, this can't happen Since it's non-increasing sequence of natural numbers, it's eventually constant, say at $t$. In this case we see that $a_{m+1} = t(m+1) - tm = t$ is constant for large $t$

Unless I'm misunderstanding something, isnt this problem the same as this USAMO 2007 P1 ? (For example compare any of the "average sequence is non decreasing" sols in linked thread to @above's sol).

Aryan-23 wrote: Unless I'm misunderstanding something, isnt this problem the same as this USAMO 2007 P1 ? (For example compare any of the "average sequence is non decreasing" sols in linked thread to @above's sol). I had it no idea that this problem it was before. I will remove that I'm proposer since it is already was on a competetion before.

Can we find complete shortlist somewhere?

Can someone point out an error in this solution? I apologise if it is too hastily written/details are not clear Let $s_n = a_0 + a_1 + a_2 + \cdots a_n$. We will show that for some $n$, $s_n = n^2$. This is sufficient because it will imply $a_k = n ~~ \forall k > n$ by simple induction (details at end of proof). Suppose $s_2 = 2 \cdot k_2$, and define $k_r = \frac{s_r}{r}$. Obviously, $s_2 \geq 2^2 = 4$. Claim: If we have $s_n < n^2$, then there must have been a perfect square in the sequence before $s_n$. Proof: Suppose $s_n = n(n-t)$ for positive integer $t$. We must also have $s_{n-1} = (n-1)(n-t)$ because if $s_{n-1} = (n-1)(n-t+r)$ for positive integer $r$, it would imply either $s_{n-1} > s_n$ or $rn - r + t < n$ but both are impossible (the second is impossible since it would mean $r(n-1) < r-t<r$). Hence $s_{n-1} = (n-1)(n-t)$. Similarly, $s_{n-2} = (n-2)(n-t), \cdots s_{n-t} = (n-t)(n-t) = (n-t)^2$, a perfect square, as desired. Now we may assume that $k_2 > 2$ and show that for some $m$, $k_m = m$ (i.e. there is a perfect square in the sequence $s_i$), since we already established that if there is $t$ such that $k_t < t$, there must be a perfect square in the sequence $s_i$. Choose the largest nonnegative integer $r_2$ such that $k_2 > 3 \cdot r_2$. This will also satisfy $3(k_2 - r_2) > s_2 = 2k_2$ and clearly it is the smallest positive integer greater than $s_2$ which is divisible by $3$, due to our choice of $r_2$. So $s_3 = 3(k_2 - r_2)$. So $k_3 = k_2 - r_2 < k_2$. Choose the largest nonnegative integer $r_3$ satisfying $k_3 > 4 \cdot r_3$. Again, this satisfies $4(k_3 - r_3) > 3 \cdot k_3 = s_3$ and is the smallest positive integer greater than $s_3$ divisible by 4, hence is $s_4$. Note that $r_2, r_3, \cdots$ is strictly decreasing, since $k_2, k_3 \cdots$ is also strictly decreasing. Hence, at some point we must have $r_t = 0$. This means $s_t = t \cdot k_t, s_{t+1} = (t+1) \cdot k_t, \cdots $ (since we had $r_t = 0 \implies r_{t+1} = 0, \cdots $). Eventually we will have $s_{k_t} = k_t \cdot k_t = (k_t)^2$. Hence there must always be $d$ such that $s_d = d^2$. Now $s_{d+1} = d(d+1) \implies a_{d+1} = d$. Similarly $s_{d+2} = d(d+2) \implies a_{d+2} = d$. It is easy to see that $a_{d+r} = d ~~ \forall $ positive integers $r$ and we are done.

Let $S_k=a_0+a_1+\cdots+a_k=kT_k$, for any $k$, it is clearly $1\leq a_k\leq k$ for $k>0$, we can select a large enough $n$, $T_n \leq n$, we know $0 \equiv nT_n+a_{n+1}\equiv a_{n+1}-T_n \pmod{n+1}$, then $a_{n+1}=T_n$ because $1\leq a_{n+1}\leq n+1$ and $T_n \leq n$. Now $S_{n+1}=(n+1)T_n$, we can get $a_{n+2}=T_n$ similarly, we have done.

This is just USAMO 07/1

dangerousliri wrote: Let $a_0$ be an arbitrary positive integer. Consider the infinite sequence $(a_n)_{n\geq 1}$, defined inductively as follows: given $a_0, a_1, ..., a_{n-1}$ define the term $a_n$ as the smallest positive integer such that $a_0+a_1+...+a_n$ is divisible by $n$. Prove that there exist a positive integer a positive integer $M$ such that $a_{n+1}=a_n$ for all $n\geq M$. Let $a_1 + a_2 + a_3 \dots a_{n-1} + a_n = nb_n$. We see that $(n+1)b_{n+1} - nb_n = a_{n+1} < n \implies (n+1)b_{n+1} < n(b_n + 1)$ and so $b_n$ sequence is weakly decreasing for all sufficiently large $n$. However, we see that $b_n > 0$ and so eventually $b_n$ is constant, implying that $a_{n+1} = (n+1)b_{n+1} - nb_n = b_n$ will be eventually constant as desired.

Take some $n\in \mathbb{Z}^+$. We have $a_0 + a_1 + \dots + a_n = nb_n$ for some positive integer $b_n$. Let $b_n\equiv c_n \pmod{n+1}$. We have $nb_n \equiv -b_n \equiv -c_n \pmod{n+1} \implies a_{n+1} = c_n$. So $a_0 + a_1 + \dots + a_n + a_{n+1} = nb_n + c_n = (n+1)b_{n+1} \implies b_{n+1} = \frac{nb_n + c_n}{n+1} < b_n + 1$. So we have $b_n \geq b_{n+1} \geq b_{n+2} \dots$ and so there exist a positive integer $M$ such that $b_k = b_{k+1}$ for all $k\geq M$. And thus, we have $a_{k+1} = b_{k+1}$ for all $k\geq M$, implying the result. $\square$

dangerousliri wrote: Let $a_0$ be an arbitrary positive integer. Consider the infinite sequence $(a_n)_{n\geq 1}$, defined inductively as follows: given $a_0, a_1, ..., a_{n-1}$ define the term $a_n$ as the smallest positive integer such that $a_0+a_1+...+a_n$ is divisible by $n$. Prove that there exist a positive integer a positive integer $M$ such that $a_{n+1}=a_n$ for all $n\geq M$. Let be $a_{0}=b$ it is clear that for all $n>0$ $a_{n}$$\le$ $n$ Then $S_{b+2}$$<$$(b+2)^2$ Let be $S_{b+2}=(b+2)×k$ $(k<b+2)$ $(b+3)|S_{b+2}+k$ $k<b+3$ then $a_{b+3}=k$ $(b+4)|S_{b+3}+k$ $k<b+4$ then $a_{b+4}=k$ . . Then all $n$$\ge$$b+3$ $a_{n}=k$

Say that $a_0+a_1+...+a_n = x_n \cdot n$. See that $a_i\le i$ for $i\ge1$. If we prove that for some $n$ : $x_n\le n+1$ we are done because, we will have $a_{n+1} = a_{n+2} =...= x_n$. See that there is some $n$ that $a_0\le \frac{n \cdot (n+1)}{2}$. This means $a_0+a_1+...+a_n \le a_0 + \frac{n \cdot (n+1)}{2} \le n \cdot (n+1)$. So we are done. And we have that $M = n+1$