Problem:
Let n be a positive integer. Define a sequence by setting a1​=n and, for each k>1, letting ak​ be the unique integer in the range 0≤ak​≤k−1 for which a1​+a2​+⋯+ak​ is divisible by k. For instance, when n=9 the obtained sequence is 9,1,2,0,3,3,3,…. Prove that for any n the sequence a1​,a2​,a3​,… eventually becomes constant.
Solution:
First Solution: For k≥1, let
sk​=a1​+a2​+⋯+ak​
We have
k+1sk+1​​<ksk+1​​=ksk​+ak+1​​≤ksk​+k​=ksk​​+1
On the other hand, for each k,sk​/k is a positive integer. Therefore
k+1sk+1​​≤ksk​​
and the sequence of quotients sk​/k is eventually constant. If sk+1​/(k+1)=sk​/k, then
ak+1​=sk+1​−sk​=k(k+1)sk​​−sk​=ksk​​
showing that the sequence ak​ is eventually constant as well.
Second Solution: For k≥1, let
sk​=a1​+a2​+⋯+ak​ and ksk​​=qk​
Since ak​≤k−1, for k≥2, we have
sk​=a1​+a2​+a3​+⋯+ak​≤n+1+2+⋯+(k−1)=n+2k(k−1)​
Let m be a positive integer such that n≤2m(m+1)​ (such an integer clearly exists). Then
qm​=msm​​≤mn​+2m−1​≤2m+1​+2m−1​=m
We claim that
qm​=am+1​=am+2​=am+3​=am+4​=…
This follows from the fact that the sequence a1​,a2​,a3​,… is uniquely determined and choosing am+i​=qm​, for i≥1, satisfies the range condition
0≤am+i​=qm​≤m≤m+i−1
and yields
sm+i​=sm​+iqm​=mqm​+iqm​=(m+i)qm​
Third Solution: For k≥1, let
sk​=a1​+a2​+⋯+ak​
We claim that for some m we have sm​=m(m−1). To this end, consider the sequence which computes the differences between sk​ and k(k−1), i.e., whose k-th term is sk​−k(k−1). Note that the first term of this sequence is positive (it is equal to n ) and that its terms are strictly decreasing since
(sk​−k(k−1))−(sk+1​−(k+1)k)=2k−ak+1​≥2k−k=k≥1
Further, a negative term cannot immediately follow a positive term. Suppose otherwise, namely that sk​>k(k−1) and sk+1​<(k+1)k. Since sk​ and sk+1​ are divisible by k and k+1, respectively, we can tighten the above inequalities to sk​≥k2 and sk+1​≤ (k+1)(k−1)=k2−1. But this would imply that sk​>sk+1​, a contradiction. We conclude that the sequence of differences must eventually include a term equal to zero.
Let m be a positive integer such that sm​=m(m−1). We claim that
m−1=am+1​=am+2​=am+3​=am+4​=…
This follows from the fact that the sequence a1​,a2​,a3​,… is uniquely determined and choosing am+i​=m−1, for i≥1, satisfies the range condition
0≤am+i​=m−1≤m+i−1
and yields
sm+i​=sm​+i(m−1)=m(m−1)+i(m−1)=(m+i)(m−1)
This problem was suggested by Sam Vandervelde.
The problems on this page are the property of the MAA's American Mathematics Competitions