IMO 2009 · Problem 3

Suppose that \(s_1,s_2,s_3,\ldots\) is a strictly increasing sequence of positive integers such that the subsequences \[ s_{s_1},s_{s_2},s_{s_3},\ldots \qquad\text{and}\qquad s_{s_1+1},s_{s_2+1},s_{s_3+1},\ldots \] are both arithmetic progressions. Prove that the sequence \(s_1,s_2,s_3,\ldots\) is itself an arithmetic progression.

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

Solution

Let \(A\) and \(B\) be the common differences of the first and second given arithmetic progressions, respectively. Both are positive integers.

Since \(s_n+1\le s_{n+1}\), strict increase gives \[ s_{s_n}<s_{s_n+1}\le s_{s_{n+1}}. \] Consequently, \[ 1\le s_{s_n+1}-s_{s_n}\le A. \] But the middle expression equals \[ \bigl(s_{s_1+1}-s_{s_1}\bigr)+(n-1)(B-A). \] Being bounded for all positive integers \(n\), it must have \(B-A=0\). Thus there is a fixed positive integer \(c\) such that \[ s_{s_n+1}-s_{s_n}=c\qquad(n\ge1). \]

Define the positive integer gaps \[ d_n=s_{n+1}-s_n. \] For every \(n\), \[ A=s_{s_{n+1}}-s_{s_n} =\sum_{k=s_n}^{s_{n+1}-1}d_k. \tag{1} \] This sum contains \(d_n\) terms, all at least \(1\), so \(d_n\le A\). Therefore the gaps have an attained minimum \(m\) and maximum \(M\), with \[ 1\le m\le M\le A. \] Moreover, the first term in every sum (1) is \(d_{s_n}=c\).

Choose an index \(i\) with \(d_i=m\). The corresponding sum (1) has first term \(c\) and \(m-1\) remaining terms, each at most \(M\). Hence \[ A\le c+(m-1)M. \] Similarly, choosing an index \(j\) with \(d_j=M\) gives \[ A\ge c+(M-1)m. \] These inequalities also hold when a sum has no remaining terms. Combining them yields \[ (M-1)m\le(m-1)M, \] which simplifies to \(M\le m\). Thus \(M=m\), and every gap \(d_n\) equals \(m\).

It follows that \[ s_n=s_1+(n-1)m\qquad(n\ge1), \] so the original sequence is an arithmetic progression. \(\square\)

The solution was checked against the official IMO shortlist solutions.