IMO 2005 · Problem 2

Let \(a_1,a_2,\ldots\) 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,\ldots,a_n\) leave \(n\) different remainders upon division by \(n\). Prove that every integer occurs exactly once in the sequence \(a_1,a_2,\ldots\).

Official text of the problem. Official problem paper (PDF)

Solution

For any indices \(i<j\), we have \(a_i\ne a_j\), because the first \(j\) terms have different remainders modulo \(j\). Moreover, \[ |a_i-a_j|<j. \tag{1} \] Indeed, if \(d=|a_i-a_j|\ge j\), then \(a_i\) and \(a_j\) are among the first \(d\) terms and have the same remainder modulo \(d\), a contradiction.

We prove by induction that the first \(n\) terms form a set of \(n\) consecutive integers. This is immediate for \(n=1\). Suppose \(n\ge2\) and \[ \{a_1,\ldots,a_{n-1}\}=\{L,L+1,\ldots,R\}, \qquad R-L=n-2. \] Applying (1) to \(a_n\) and the earlier occurrences of \(L\) and \(R\), we obtain \[ |a_n-L|\le n-1,\qquad |a_n-R|\le n-1. \] Consequently, \[ L-1=R-(n-1)\le a_n\le L+(n-1)=R+1. \] Since \(a_n\) differs from all earlier terms, it cannot lie in \(\{L,\ldots,R\}\). Thus \(a_n=L-1\) or \(a_n=R+1\), completing the induction.

All terms are distinct, so infinitely many positive terms imply that the sequence is unbounded above. Likewise, infinitely many negative terms imply that it is unbounded below.

Now let \(t\) be any integer. Choose indices \(p,q\) such that \[ a_p<t<a_q, \] and set \(N=\max\{p,q\}\). The first \(N\) terms form a set of consecutive integers containing both \(a_p\) and \(a_q\), so they also contain \(t\). Therefore every integer occurs, and the previously established distinctness shows that it occurs exactly once. \(\square\)

The solution was checked against Evan Chen's published IMO solution notes.