Let $a_0$ be an arbitrary positive integer. Let $(a_n)$ be infinite sequence of positive integers such that for every positive integer $n$, the term $a_n$ is the smallest positive integer such that $a_0 + a_1 +... + a_n$ is divisible by $n$. Prove that there exist $N$ such that $a_{n+1} = a_n$ for all $n \ge N$
Problem
Source: 2019 Saudi Arabia IMO TST II p1
Tags: number theory, divides, divisible
31.07.2020 05:48
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.
21.04.2024 21:42
Let $a_0+\ldots+a_n=nb_n$. Then if $b_n \leq n+1$, then $b_n=a_{n+1}=a_{n+2}=\ldots$. Now suppose that $b_n \geq n+2$, so $a_0+a_1+\ldots+a_n \geq n^2+2n$ Now because $a_i \leq i$ for $i \geq 2$, $a_0+\ldots+a_n \leq a_0+2+\ldots+n=a_0-1+\frac{n(n+1)}{2}$, so eventually it will get smaller than $n^2+2n$, which finishes the proof.
29.05.2024 16:10
parmenides51 wrote: Let $a_0$ be an arbitrary positive integer. Let $(a_n)$ be infinite sequence of positive integers such that for every positive integer $n$, the term $a_n$ is the smallest positive integer such that $a_0 + a_1 +... + a_n$ is divisible by $n$. Prove that there exist $N$ such that $a_{n+1} = a_n$ for all $n \ge N$ Let $a_0+a_1+ \cdots +a_n = b_n*n $. Then $n*b_n + a_{n+1} =(n+1)*b_{n+1}$. İf $b_{n+1} \geq b_n +1 $ for some $n$, then we have $(b_n+1)(n+1) \leq a_{n+1}+ nb_n$, which means that $a_{n+1} \geq b_n +n+1$. This gives a contradiction as $a_{n+1}$ should be $ \leq n+1 $. So, the sequence $(b_n)$ is non-increasing. This gives us that $b_n=C$ constant for all $n \geq N$. This in turn means that $a_{n+1}= (n+1)b_{n+1}- nb_n=C $ for all $n \geq N$