Problem 2

Let

a_1, a_2, \dots

be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer

n

the numbers

a_1, a_2, \dots, a_n

leave

n

different remainders upon division by

n

. Prove that every integer occurs exactly once in the sequence.

Step 3 of 5: The first

n

terms are

n

consecutive integers

Previous step Next step

In plain words

Induction: a block of consecutive integers can only be extended by exactly one more integer at one of its two open ends.

\{a_1,\dots,a_n\}=\{k+1,\dots,k+n\}\ \text{for some integer }k

Detailed analysis

Induct on $n$ (base case $n=1$ is trivial). If $\{a_1,\dots,a_n\}=\{k+1,\dots,k+n\}$ , this block together with $k$ forms $n+1$ consecutive integers $k,k+1,\dots,k+n$ , which realizes every residue mod $n+1$ exactly once; the block $\{a_1,\dots,a_n\}$ is missing exactly the residue of $k$ . Since $a_1,\dots,a_{n+1}$ must also realize all $n+1$ residues mod $n+1$ , we need $a_{n+1}\equiv k\pmod{n+1}$ . By the previous step, $|a_{n+1}-a_1|<n+1$ with $a_1\in\{k+1,\dots,k+n\}$ , so the only integers congruent to $k$ mod $n+1$ that close to $a_1$ are $k$ and $k+n+1$ . Either choice extends the block by exactly one consecutive integer.