Shortlist 2014, A1

Domaine : Algèbre · Difficulté : ★☆☆☆☆ · Proposé par : Austria

Concepts : Suites et récurrences · Principe extrémal

Solution officielle : Shortlist officielle 2014 (avec solutions), p. 10 (page 11 du PDF)

Problème 1 de l'OIM 2014

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

Énoncé

Let \(z_0 < z_1 < z_2 < \cdots\) be an infinite sequence of positive integers. Prove that there exists a unique integer \(n \geq 1\) such that

\[z_n < \frac{z_0 + z_1 + \cdots + z_n}{n} \leq z_{n+1}. \tag{1}\]

Indices : les idées clés

• Une suite auxiliaire : \(d_n = (z_0 + \cdots + z_n) - n z_n\) ; la première inégalité équivaut à \(d_n > 0\) et la seconde à \(d_{n+1} \leq 0\).
• Suite strictement décroissante : \(d_{n+1} - d_n = n(z_n - z_{n+1}) < 0\), et \(d_1 = z_0 > 0\).
• Principe extrémal : une suite d'entiers strictement décroissante finit par devenir négative ; l'indice cherché est celui du dernier terme positif.

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2014 (une solution et une remarque).

Solution

Pour \(n = 1, 2, \ldots\), posons

\[d_n = (z_0 + z_1 + \cdots + z_n) - n z_n.\]

Le signe de \(d_n\) indique si la première inégalité de (1) est vraie : elle l'est si et seulement si \(d_n > 0\).

On remarque que

\[n z_{n+1} - (z_0 + z_1 + \cdots + z_n) = (n+1) z_{n+1} - (z_0 + z_1 + \cdots + z_n + z_{n+1}) = -d_{n+1},\]

donc la seconde inégalité de (1) équivaut à \(d_{n+1} \leq 0\). Il s'agit donc de montrer qu'il existe un unique indice \(n \geq 1\) tel que \(d_n > 0 \geq d_{n+1}\).

Par définition, les \(d_n\) sont des entiers, et

\[d_1 = (z_0 + z_1) - 1 \cdot z_1 = z_0 > 0.\]

De plus,

\[d_{n+1} - d_n = \big((z_0 + \cdots + z_n + z_{n+1}) - (n+1) z_{n+1}\big) - \big((z_0 + \cdots + z_n) - n z_n\big) = n(z_n - z_{n+1}) < 0,\]

donc \(d_{n+1} < d_n\) : la suite est strictement décroissante.

On a donc une suite d'entiers strictement décroissante \(d_1 > d_2 > \cdots\) dont le premier terme est positif. Elle devient négative à partir d'un certain rang, et il existe donc un unique indice \(n\), celui du dernier terme strictement positif, qui vérifie \(d_n > 0 \geq d_{n+1}\). \(\blacksquare\)

Remarque

Si l'on ne suppose plus que les \(z_i\) sont des entiers, les \(d_n\) peuvent être tous strictement positifs, et l'indice \(n\) cherché n'existe pas. C'est le cas par exemple pour \(z_n = 2 - \frac{1}{2^n}\) pour tout entier \(n \geq 0\).