International Mathematical Olympiad

The conditions of the problem can be reformulated by saying that for every positive integer $n$, the numbers $a_1, a_2, \dots, a_n$ form a complete set of residues modulo $n$. We proceed our proof as the following.

(1) First, we claim that the sequence consists of distinct integers; that is, if $1 \le i < j$, then $a_i \ne a_j$. Otherwise the set $\{a_1, a_2, \dots, a_j\}$ would contain at most $j-1$ distinct residues modulo $j$, violating our new formulation of the conditions of the problem.

(2) Second, we show that numbers in the sequence are fairly close to each other. More precisely, we claim that if $1 \le i < j \le n$, then $|a_i - a_j| \le n - 1$. For if $m = |a_i - a_j| \ge n$, then the set $\{a_1, a_2, \dots, a_m\}$ would contain two numbers congruent modulo $m$, violating our new formulation of the conditions of the problem.

(3) Third, we show that the set $\{a_1, a_2, \dots, a_n\}$ contains a block of consecutive numbers. Indeed, for every positive integer $n$, let $i_n$ and $j_n$ be the indices such that $a_{i_n}$ and $a_{j_n}$ are respectively the smallest and the largest number among $a_1, a_2, \dots, a_n$. By (2), we conclude that $a_{j_n} - a_{i_n} = |a_{j_n} - a_{i_n}| \le n - 1$. By (1), we conclude that $\{a_1, a_2, \dots, a_n\}$ consists of all integers between $a_{i_n}$ and $a_{j_n}$ (inclusive).

(4) Finally, we show that every integer appears in the sequence. Let $x$ be an arbitrary integer. Because $a_k < 0$ for infinitely many indices $k$ and the terms of the sequence are distinct, it follows that there exists $i$ such that $a_i < x$. Likewise, there exists $j$ such that $x < a_j$. Let $n$ be an integer with $n \ge \max\{i, j\}$. By (3), we conclude that every number between $a_i$ and $a_j$, including $x$ in particular, is in $\{a_1, a_2, \dots, a_n\}$. Our proof is thus complete.