Shortlist 2009, A6

Domaine : Algèbre · Difficulté : ★★★☆☆ · Proposé par : United States of America

Concepts : Suites et récurrences · Sommes, télescopage et transformation d'Abel · Principe extrémal

Solution officielle : Shortlist officielle 2009 (avec solutions), p. 21 (page 23 du PDF)

Problème 3 de l'OIM 2009

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2009, où il était le problème 3 (jour 1).

Énoncé

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 \(s_1, s_2, s_3, \ldots\) is itself an arithmetic progression.

Indices : les idées clés

• Différences bornées : \(d_n = s_{n+1} - s_n \geq 1\) et \(d_n \leq d_{s_n} + \cdots + d_{s_{n+1} - 1} = D\), la raison de \((s_{s_n})\).
• Sommes télescopiques : avec \(m = \min d_n\) et \(M = \max d_n\) (extrémalité), on obtient \(D \leq mM\) et \(D \geq Mm\), donc \(d_n = m \Rightarrow d_{s_n} = M\) et inversement.
• Alternance : la suite \((d_{s_n})\), différence de deux progressions arithmétiques, est arithmétique, mais prend alternativement les valeurs \(M\) et \(m\), donc \(m = M\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2009 (deux solutions).

Solution 1

Soit \(D\) la raison de la progression \(s_{s_1}, s_{s_2}, \ldots\). Posons, pour \(n = 1, 2, \ldots\),

\[d_n = s_{n+1} - s_n.\]

Il faut prouver que \(d_n\) est constant. Montrons d'abord que les nombres \(d_n\) sont bornés. En effet, par hypothèse \(d_n \geq 1\) pour tout \(n\). On a donc, pour tout \(n\),

\[d_n = s_{n+1} - s_n \leq d_{s_n} + d_{s_n + 1} + \cdots + d_{s_{n+1} - 1} = s_{s_{n+1}} - s_{s_n} = D.\]

Le caractère borné implique l'existence de

\[m = \min\{d_n : n = 1, 2, \ldots\} \qquad \text{et} \qquad M = \max\{d_n : n = 1, 2, \ldots\}.\]

Il suffit de montrer que \(m = M\). Supposons \(m < M\). Choisissons \(n\) tel que \(d_n = m\). En considérant une somme télescopique de \(m = d_n = s_{n+1} - s_n\) termes au plus égaux à \(M\), on obtient

\[D = s_{s_{n+1}} - s_{s_n} = s_{s_n + m} - s_{s_n} = d_{s_n} + d_{s_n + 1} + \cdots + d_{s_n + m - 1} \leq mM, \tag{1}\]

avec égalité si et seulement si tous les termes de la somme valent \(M\). Choisissons maintenant \(n\) tel que \(d_n = M\). De la même façon, en considérant une somme télescopique de \(M\) termes au moins égaux à \(m\), on obtient

\[D = s_{s_{n+1}} - s_{s_n} = s_{s_n + M} - s_{s_n} = d_{s_n} + d_{s_n + 1} + \cdots + d_{s_n + M - 1} \geq Mm, \tag{2}\]

avec égalité si et seulement si tous les termes de la somme valent \(m\). Les inégalités (1) et (2) impliquent \(D = Mm\) et

\[\begin{aligned} d_{s_n} = d_{s_n + 1} = \cdots = d_{s_{n+1} - 1} &= M \quad \text{si } d_n = m, \\ d_{s_n} = d_{s_n + 1} = \cdots = d_{s_{n+1} - 1} &= m \quad \text{si } d_n = M. \end{aligned}\]

Donc \(d_n = m\) implique \(d_{s_n} = M\). Remarquons que \(s_n \geq s_1 + (n - 1) \geq n\) pour tout \(n\), et de plus \(s_n > n\) si \(d_n = m\) : en effet, si \(s_n = n\), on aurait \(m = d_n = d_{s_n} = M\), ce qui contredit l'hypothèse \(m < M\). De même, \(d_n = M\) implique \(d_{s_n} = m\) et \(s_n > n\). Par conséquent, il existe une suite strictement croissante \(n_1, n_2, \ldots\) telle que

\[d_{s_{n_1}} = M, \quad d_{s_{n_2}} = m, \quad d_{s_{n_3}} = M, \quad d_{s_{n_4}} = m, \quad \ldots\]

Or la suite \(d_{s_1}, d_{s_2}, \ldots\) est la suite des différences terme à terme de \(s_{s_1+1}, s_{s_2+1}, \ldots\) et de \(s_{s_1}, s_{s_2}, \ldots\) ; c'est donc aussi une progression arithmétique. Donc \(m = M\). \(\blacksquare\)

Solution 2

Soient \(D\) et \(E\) les raisons des progressions \(s_{s_1}, s_{s_2}, \ldots\) et \(s_{s_1+1}, s_{s_2+1}, \ldots\) respectivement. Posons \(A = s_{s_1} - D\) et \(B = s_{s_1+1} - E\). Alors, pour tout entier \(n > 0\),

\[s_{s_n} = A + nD, \qquad s_{s_n+1} = B + nE.\]

Comme la suite \(s_1, s_2, \ldots\) est strictement croissante, on a pour tout entier \(n > 0\)

\[s_{s_n} < s_{s_n+1} \leq s_{s_{n+1}},\]

ce qui implique

\[A + nD < B + nE \leq A + (n + 1)D,\]

et donc

\[0 < B - A + n(E - D) \leq D,\]

ce qui implique \(D - E = 0\) et ainsi

\[0 \leq B - A \leq D. \tag{3}\]

Soit \(m = \min\{s_{n+1} - s_n : n = 1, 2, \ldots\}\). Alors

\[B - A = (s_{s_1+1} - E) - (s_{s_1} - D) = s_{s_1+1} - s_{s_1} \geq m \tag{4}\]

et

\[D = A + (s_1 + 1)D - (A + s_1D) = s_{s_{s_1+1}} - s_{s_{s_1}} = s_{B+D} - s_{A+D} \geq m(B - A). \tag{5}\]

D'après (3), on considère deux cas.

Cas 1 : \(B - A = D\). Alors, pour tout entier \(n > 0\), \(s_{s_n+1} = B + nD = A + (n + 1)D = s_{s_{n+1}}\), donc \(s_{n+1} = s_n + 1\) et \(s_1, s_2, \ldots\) est une progression arithmétique de raison \(1\).

Cas 2 : \(B - A < D\). Choisissons un entier \(N > 0\) tel que \(s_{N+1} - s_N = m\). Alors

\[\begin{aligned} m(A - B + D - 1) &= m\big((A + (N + 1)D) - (B + ND + 1)\big) \\ &\leq s_{A + (N+1)D} - s_{B + ND + 1} = s_{s_{s_{N+1}}} - s_{s_{s_N+1}+1} \\ &= (A + s_{N+1}D) - (B + (s_N + 1)D) = (s_{N+1} - s_N)D + A - B - D \\ &= mD + A - B - D, \end{aligned}\]

c'est-à-dire

\[(B - A - m) + (D - m(B - A)) \leq 0. \tag{6}\]

Les inégalités (4) à (6) impliquent

\[B - A = m \qquad \text{et} \qquad D = m(B - A).\]

Supposons qu'il existe un entier \(n > 0\) tel que \(s_{n+1} > s_n + m\). Alors

\[m(m + 1) \leq m(s_{n+1} - s_n) \leq s_{s_{n+1}} - s_{s_n} = (A + (n + 1)D) - (A + nD) = D = m(B - A) = m^2,\]

ce qui est une contradiction. Donc \(s_1, s_2, \ldots\) est une progression arithmétique de raison \(m\). \(\blacksquare\)