$m_{k}= \frac{a_{1}+...+a_{k}}{k}\le \frac{n}{k}+\frac{k-1}{2}$ For sufficiently large $k$ (say, $k = n$) we have $m_{n}= \frac{n+1}{2}\le n$ And $a_{1}+...+a_{n}+im_{n}= (n+i) m_{n}$ Hence $a_{n+i}= m_{n}, i = 1, 2, ...$.

Exactly for $k\ge \sqrt{2n}$ we get $a_{k}=a_{k+1}=...$

Not sure if revival of these topics is allowed or not, but I've come up with a solution and wouldn't mind having it evaluated.

yankeesrule007 wrote: By the properties of this sequence, we know that $b_n = n d_n$ for some positive integers $b_n$ and $d_$ for all $k \in \mathbb{N}$. Specifically what properties of the sequence did you use to determine that?

In ThinkFlow's solution, why does $b_i$ have to become constant? I am sorry if this is a dumb question.

ThinkFlow wrote: Let $b_i = \frac{a_1+\cdots +a_i}{i}$. Because $b_{i+1} = \frac{a_1+\cdots +a_{i}+a_{i+1}}{i+1}< \frac{a_1+\cdots +a_i+i}{i} = b_i+1$, the sequence $\{b_i\} _{i=1}^\infty$ is nonincreasing. Because the $b_i$ are positive integers, $b_i$ eventually becomes constant, so $\{a_1+\cdots +a_i\}_{i=1}^\infty$ eventually becomes arithmetic, so $a_i$ becomes constant, as desired. 1. $b_i = \frac{a_1+\cdots +a_i}{i}$ is a positive integer, precisely by the way $a_i$ is chosen; 2. $a_{i+1} \leq (i+1) - 1 = i$, so $b_{i+1} = \frac{a_1+\cdots +a_i + a_{i+1}}{i+1} \leq$ $ \frac{a_1+\cdots +a_i + i}{i+1} <$ $ \frac{a_1+\cdots +a_i + i}{i} = $ $\frac{a_1+\cdots +a_i}{i} + 1 = b_i + 1$; 3. Since the sequence $(b_i)_{i\geq 1}$ is made of positive integers, from $b_{i+1} < b_i +1$ follows $b_{i+1} \leq b_i$, hence the sequence is non-increasing; 4. Therefore the sequence $(b_i)_{i\geq 1}$ must become eventually constant, since there are only a finite number of times (namely $b_1=a_1=n$ times) when it may strictly decrease (by at least $1$ at each step).

Let us define $S_i= \Sigma a_i$ Consider the number ${D_x= \frac {S_x + \frac{S_x}{x}}{x+1} =\frac{S_x}{x}}$ Since ${\frac{S_x}{x}}$ is an integer $D_x$ is an integer .But since $a_{x+1}$ is the unique integer such that $0 \le a_{x+1} \le x$ and $S_{x+1}$ is divisible by $x+1$ if ${a_{x+1}\not= \frac{S_x}{x}}$ for all x we would have ${{\frac{S_{x+1}}{x+1}}=\frac{S_x+a_{x+1}}{x+1}} >D_x$ .Therefore ${\frac{S_x}{x}} > x (\frac{S_x}{x} also satisfies \frac{S_x+r}{x+1} is an integer)$ for all $x$ . But we can choose sufficiently large $x$ such that ${\frac{S_x}{x}} \le x(since a_x <x)$ Hence for a sufficiently large $x$ we would have ${a_{x+1}= \frac{S_x}{x}}$ Hence ${{\frac{S_x}{x}}=\frac{S_{x+1}}{x+1}} =a_{x+1}$ Now if we proceed by induction we would get ${{\frac{S_{x+i}}{x+i}}=\frac{S_x}{x}}$ for all $i \ge 0((x+i)^2 \ge S_{x+i})$ and this gives the desired result $a_{x+i}= a_{x+1}$ for all $ i \ge 0$

All the above solutions are more elegant than my Inductive solution. Still i didn't find anyone posting this one so just providing a sketch. Key Observation Let $S_n(k)=\sum_{i=1}^ka_{n_i}$. We claim $S_n(k)=S_{n-1}(k)$ or $S_n(k)=S_{n-1}(k) + k$. Prove this by induction on $k$. Now if the former happens then we get $a_{{n-1}_{k+1}}=a_{n_{k+1}}$. If the latter happens see that $a_{n_{k+1}}==a_{{n-1}_{k+1}} - 1 ($mod $ k+1)$ which gives $\boxed{a_{n_{k+1}}=a_{{n-1}_{k+1}} + 1}$ for $a_{{n-1}_{k+1}}\neq k$ and $a_{n_{k+1}}=0$ for $a_{{n-1}_{k+1}}=k$ Now show base case $n=1$ true , trivially by induction. Assume the problem for $n=N$. For $N+1$ see that if for some $k$, $S_n(k)=S_{n-1}(k)$ then we are done (by Induction Hypothesis). Else by Induction Hypothesis there exists $m \in N$ such that $k\geq m \implies a_{{n-1}_{k}}=a_{{n-1}_m}$. By above , we get the same value of $a_{n_{k}}$ from a fixed value of $a_{{n-1}_{k}}$ regardless of $k$. Combining we get $\boxed{{a_{n_k}}=a_{n_m}}$ for all $k\geq m$.

Let $b_i$ be the average of the first $i$ terms of the sequence. Then $a_{k+1} + kb_k \equiv 0 \pmod{k+1}$ so $a_{k+1} \equiv b_k \pmod{k+1}$. So this establishes an interesting relationship: $a_{k+1} = b_k \% (k+1)$ where the % operator is "remainder". So notice that since $a_{k+1} \le b_k$, we must have $b_k$ non-increasing. If the $a_k$ sequence did not become constant, that means $b_k$ would decrease indefinitely, which is a contradiction since $b_k > 0$ for all $k$.

My solution uses induction that For any $n\in N$ in sequence there is $k\in N$ such that $a_1+a_2+...+a_{k-1}=(k-1)a_k$

Pretty funny: If $a_1+\cdots+a_k=rk$ where $r\le k$, then we are done as the sequence will now be $(r,r,\ldots)$. But we have that $a_1+\cdots+a_k\le n+k(k-1)/2$, which eventually becomes at most $k^2$, as desired.

The problem is finished if there exists $k$ satisfying $a_1 + a_2 + \dots + a_k = xk$ where $k \le k.$ Then note that you can have $x = a_{k+1} = a_{k+2} = \dots.$ Now, we can bound $(\ell-1)^2 < n \le \ell^2$, so $a_1 + a_2 + \dots a_m \le n + \frac{m(m-1)}{2} \le (\ell-1)^2 + \frac{m(m-1)}{2} \le m^2$ for some choice of $\ell$, as desired. $\blacksquare$

Let $f(k) = \frac{1}{k}\sum_{i = 1}^ka_i$ for each integer $k > 0$. Note that $a_{k+1} = k + 1 - kf(k) + (k+1)\lfloor kf(k)/(k+1)\rfloor$. Then, \[f(k+1)\le f(k)\iff \frac{k}{k+1}f(k) + \frac{a_{k+1}}{k+1}\le f(k)\iff f(k)\ge a_{k+1}\]\[ \iff f(k)\ge k+1 - kf(k) + (k+1)\lfloor kf(k)/(k+1)\rfloor\iff f(k)\ge 1 + \lfloor kf(k)/(k+1)\rfloor,\]which clearly holds for $k$ sufficiently large. Thus, $f$ is nonincreasing for all $k$ sufficiently large, meaning $f$ is eventually constant (keeping in mind that its codomain is $\mathbb{N}$). It follows that $(a_k)_{k\ge 1}$ is also eventually constant, as desired.

I claim that there must exist some k such that a(1) + .... + a(k) is less than k^2 regardless of what you start with. To prove this, assume for the maximization that for each a(i) = i-1 for i≥2. Then this becomes a(1) + (1+...+(k-1)) = k(k-1)/2 + a(1). If you increase k enough then this will be true. Now define the first k for which this value is true has a(1) + .... + a(k) = ck, for c some positive integer. Then we show that all a(i) afterwards must have a(i) = c. This now becomes an induction problem. For the inductive step, we assume that a(1) + ..... + a(n) = cn for n ≥ k. Then by taking mod n+1, this becomes -c mod n+1. c<n+1< n+1+c, so a(n+1) must be c. Thus after this k the sequence becomes constant with all terms = c.

Pretty funny problem. Claim. If $a_k = rk \leq k^2$, then $a_{k+1} = a_{k+2} = \cdots = r$. Proof. Note that $r \leq k$, and $r$ also creates multiples of $i > k$ at every juncture. $\blacksquare$ On the other hand, we must have $a_k < k^2$ at some point, because $$a_k < n + 1 + 2 + \cdots + (k-2) = n+\frac{k(k-1)}2.$$

nice Let $S_i=a_1+a_2+\cdots a_n$ Claim. if $m\mid S_m=m\cdot k$ and $0\leq k\leq m$ for some $k$ we are done Proof: This is true since in the following steps we may choose $k$ as $m+i\mid S_{m+i}=S_m+ik=mk+ik=k(m+i)$ So note that this would be impossible only if $S_m=mk>m\cdot m=m^2$ for every $m$. Now $$S_m=a_1+a_2+a_3+\cdots a_m\leq n+1+2+\cdots (m-1)=n+\frac{m(m-1)}{2}$$But $S_m\leq n+\frac{m(m-1)}{2}\leq m^2$ for enough large $m$

Note that for large $k$, we have $a_1 + a_2 + \dots + a_k \le a_1 + 1 + 2 + \dots + (k-1) \le a_1 + \frac{k(k-1)}{2} \le k^2$. Let $s = \frac{a_1 + a_2 + \dots + a_k}{k}$, then $s \le k$. Then we get $a_{k+1} = a_{k+2} = \dots = s$, so we're done. $\blacksquare$

If $b_k = \tfrac{a_1 + a_2 + \dots + a_k}{k}$, then the recurrence for $a_n$ translates to $b_n$ as \[ b_k = \left \lceil b_{k-1} \cdot \frac{k-1}{k} \right \rceil, \]so $b_i$ is nonincreasing. It is also bounded below by $0$, so $b_k$ is eventually constant. When this happens, $a_k$ is also constant, so we are done. oops my writeup is word for word identical to #45 :skull:

Clearly the idea is to define the new sequence $b_k = (a_1 + a_2 + \cdots + a_k)/k$. Now one can proceed in two diferent ways Approach 1. Be optimistic and try to show $(b_k)$ is non-increasing. One can show that $(b_k)$ is not increasing. To do this, notice how $$b_{k+1} = \frac{k}{k+1}b_k + \frac{a_k}{k+1} \leq \frac{k}{k+1}(b_k+1) < b_k+1.$$As $b_{k+1}$ is a positive integer this implies that $b_{k+1} \leq b_k$, implying that $(b_k)$ is eventually constant Approach 2 Look at differences. We will look at the values of $b_{k+1} - b_k$. We will show this is eventually always $0$. To do this notice that $$b_{k+1}-b_{k} = (a_1 + a_2 + \cdots a_k - ka_{k+1})/k(k+1) < (n + 1 + 2 + \cdots + (k-1))/k(k+1) = 1/2 + o(1).$$So for $k$ big enough this must be $0$, as it is an integer smaller than $1$. So from a point on $a_1 + a_2 + \cdots + a_k - ka_{k+1} = 0$, so $a_{k+1}$ must be the average of the $a_i's$ before him, and applying this law from a point on gives us that the $a_i's$ are eventually constant. Remark It is almost too good to be true that one can show so easily that $(b_k)$ is non-increasing, as it destroys the problem immediately. That is why maybe one overlooks this idea and thinks of Approach 2. In my eyes the problem almost guarantees you that Approach 2 works, as it is telling you that $(b_{k+1} - b_{k})$ is eventually $0$, so it will take finitely many values before reaching this point, which motivates you to look at its growth.

Denote $S_{n, k}$ as the $k$th partial sum for the sequence where $a_1 = n$; i.e., $S_{n, k} = a_1 + a_2 + \dots + a_k$, $a_1 = n$. From the problem statement, we know that $\forall k$, $k \mid S_{n, k}$. This means that for all values of $k$ and $n$, $S_{n, k}$ can be written as $km$. We will now show that if there exists $S_{n, k}$ such that $m \leq k$, the sequence becomes constant. First, we will demonstrate that $\forall c \in \mathbb{Z}^{+}$, $a_{k + c} = m$ via induction. Base Case In order to find $a_{k + 1}$ such that $k + 1 \mid km + a_{k + 1}$, we can simply choose $a_{k + 1} = m$; this is valid because we are given that $m \leq k$ and $a_{k + 1} \leq k$. Obviously, $k + 1 \mid m(k + 1)$. Inductive Step We assume that $a_{k + i} = m$ for $i \leq c$. We can also write $S_{n, k + c}$ as $S_{n, k} + mc$. Since $S_{n, k} = km$, we have $S_{n, k + c} = km + mc = m(k + c)$. Similar to before, in order to find $a_{k + c + 1}$ such that $k + c + 1 \mid m(k + c) + a_{k + c + 1}$, we have $a_{k + c + 1} = m$, as desired. We will now show that $\forall n$, $\exists k \text{ s.t. } S_{n, k} = km$ for $m \leq k$. Assume for the sake of contradiction that $\forall k$, $S_{n, k} = mk$ where $m > k$. Since $a_{k} \leq k - 1$, we have a bound of $S_{n, k}$. \[S_{n, k} \leq n + 1 + 2 + \dots + (k - 1)\]\[S_{n, k} \leq n + \frac{k(k - 1)}{2}\]\[2S_{n, k} \leq 2n + k(k - 1)\] We now write $S_{n, k} = mk$ (where $m > k$): \[2mk \leq 2n + k(k - 1)\]\[k(2m - k + 1) \leq 2n\] Since $m > k$, we know $b \geq k + 1$; we are then allowed to plug in $b = k + 1$ into the LHS (as it will simply decrease the value of it). \[k(2(k + 1) - k + 1) \leq 2n \]\[k(k + 3) \leq 2n\] But $2n$ is constant, so we just need to find $k$ (which clearly always exists) such that $k(k + 3) > 2n$. This contradicts our initial assumption that $\exists n \text{ s.t. } \forall k$, $S_{n, k} = mk$ where $m > k$. We can then conclude that $\forall n$, $\exists k \text{ s.t. } S_{n, k} = km$ for $m \leq k$, as desired. Since we showed earlier that all $S_{n, k}$ that satisfy the form stated earlier, $a_k$ will eventually become constant $\forall n$, as desired.

Pick a $k>n$ and denote $S=a_1+a_2+\ldots+a_{k-1}$. Note that $S\le n+\frac{(k-2)(k-1)}{2}$ and $S=(k-1)p$ where $p$ is a natural number. We also have $S+a_k=kq$ where $q$ is a natural number. So we have $$kq=S+a_k\le S+k-1=(k-1)p+k-1\iff k(p-q+1)\ge 1+p>0$$ So we have $p-q \ge 0$. On the other hand, we have $$kq=S+a_k\ge S=(k-1)p\iff k(p-q)\le p$$ Now notice that $p\le \frac{n}{k-1}+\frac{k-2}{2}$ so for $k>n$ we have $p<k$ so we must have $p-q=0$. So we get $p=q$ for all $k>n$ hence $\frac{a_1+a_2+\ldots+a_k}{k}$ is eventually constant and equal to $p$ from where we easily get that $a_k=p$ for all $k>n$. $\square$

Consider the sequence. \[b_i= \frac{a_1+a_2+\dots +a_i}{i}\] We get that the sequence $(b_i)$ is nonincreasing, hence it will eventually be constant. Implying that $(a_i)$ will also be constant.

Define the sequence $b_1, b_2, \dots $ where $b_i=\frac{a_i}{i}$, I will prove that $b_i$ is eventually constant, if $b_i\leq i$ then we have that $i+1 \mid ib_i+b_i$ and as $b_i<i+1$ this is the unique value less than $i$, so we have that $b_{i+1}=b_i$ and thus the sequence is constant, if $b_i>i$, then we have that $a_{i+1}=ib_{i}+k$ where $k<b_i$ so we have that $b_{i+1}<b_i$ if $b_i>i$ which suffices.

Let $b_k = \frac{a_1+a_2+\cdots+a_k}{k}$. Then, notice that: $$b_{k+1} = \frac{k b_k+a_{k+1}}{k+1} < \frac{k b_k + k}{k} = b_k+1.$$Thus, the sequence $b_i$ is a non-increasing positive integer sequence, which implies it eventually attains a constant value.

Let $\{b_k\} = a_1 + a_2 + \dots + a_k$. The sequence $b_k$ jumps up to the nearest multiple of $k$. Claim: $\left\{\frac{b_k}{k}\right\}$ is eventually constant. Note that this sequence starts at $n$. Suppose $\frac{b_k}{k} > \frac{b_{k-1}}{k-1}$. Let $b_{k-1} = a(k-1)$ so that $b_k \geq (a+1)k$. Then $a_k = b_k - b_{k-1} \geq k + a \geq k$, contradiction. Therefore, $\left\{\frac{b_k}{k}\right\}$ is a nonincreasing infinite sequence of positive integers. Thus, it is eventually constant. So, $\{b_k\}$ eventually forms an arithmetic progression, and thus $\{a_k\}$ is eventually constant.

Notice that there exists some number $k$ such that the first $k$ terms is less than or equal to $k^2$. This is because the upper bound on the sum is $n + \frac{k(k+1)}{2}$ which when compared to $k^2$ is small. Let this sum be $s$. Then, set every other term equal to $\frac{s}{k}$, which works.