Aller au contenu

Shortlist 2014, A2

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

Concepts : Suites et récurrences · Invariants et monovariants

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

Énoncé

Define the function \(f : (0, 1) \to (0, 1)\) by

\[f(x) = \begin{cases} x + \frac{1}{2} & \text{if } x < \frac{1}{2}, \\ x^2 & \text{if } x \geq \frac{1}{2}. \end{cases}\]

Let \(a\) and \(b\) be two real numbers such that \(0 < a < b < 1\). We define the sequences \(a_n\) and \(b_n\) by \(a_0 = a\), \(b_0 = b\), and \(a_n = f(a_{n-1})\), \(b_n = f(b_{n-1})\) for \(n > 0\). Show that there exists a positive integer \(n\) such that

\[(a_n - a_{n-1})(b_n - b_{n-1}) < 0.\]
Indices : les idées clés
  • Traduire la conclusion : \(f(x) - x > 0\) sur \(I_1 = \left(0, \frac{1}{2}\right)\) et \(f(x) - x < 0\) sur \(I_2 = \left[\frac{1}{2}, 1\right)\) ; il faut donc qu'à un moment \(a_{n-1}\) et \(b_{n-1}\) soient dans des intervalles différents.
  • Monovariant : par l'absurde, la distance \(d_k = \lvert a_k - b_k \rvert\) ne diminue jamais, et elle est multipliée par au moins \(1 + d_0\) toutes les deux étapes.
  • Suite géométrique : \(d_{2m} \geq d_0 (1 + d_0)^m\) dépasse \(1\), alors que \(a_{2m}\) et \(b_{2m}\) sont dans \((0, 1)\).
Solutions

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

Solution

On remarque que \(f(x) - x = \frac{1}{2} > 0\) si \(x < \frac{1}{2}\), et \(f(x) - x = x^2 - x < 0\) si \(x \geq \frac{1}{2}\). Découpons donc \((0, 1)\) en deux intervalles \(I_1 = \left(0, \frac{1}{2}\right)\) et \(I_2 = \left[\frac{1}{2}, 1\right)\). L'inégalité

\[(a_n - a_{n-1})(b_n - b_{n-1}) = \big(f(a_{n-1}) - a_{n-1}\big)\big(f(b_{n-1}) - b_{n-1}\big) < 0\]

est vraie si et seulement si \(a_{n-1}\) et \(b_{n-1}\) sont dans des intervalles différents.

Supposons au contraire que \(a_k\) et \(b_k\) soient toujours dans le même intervalle, et considérons la distance \(d_k = \lvert a_k - b_k \rvert\). Si \(a_k\) et \(b_k\) sont tous deux dans \(I_1\), alors

\[d_{k+1} = \lvert a_{k+1} - b_{k+1} \rvert = \left\lvert a_k + \tfrac{1}{2} - b_k - \tfrac{1}{2} \right\rvert = d_k.\]

Si au contraire \(a_k\) et \(b_k\) sont tous deux dans \(I_2\), alors \(\min(a_k, b_k) \geq \frac{1}{2}\) et \(\max(a_k, b_k) = \min(a_k, b_k) + d_k \geq \frac{1}{2} + d_k\), ce qui donne

\[d_{k+1} = \lvert a_{k+1} - b_{k+1} \rvert = \lvert a_k^2 - b_k^2 \rvert = \lvert (a_k - b_k)(a_k + b_k) \rvert \geq \lvert a_k - b_k \rvert \left(\tfrac{1}{2} + \tfrac{1}{2} + d_k\right) = d_k (1 + d_k) \geq d_k.\]

La distance \(d_k\) est donc croissante (au sens large), et en particulier \(d_k \geq d_0 > 0\) pour tout \(k\).

On peut en dire plus. Si \(a_k\) et \(b_k\) sont dans \(I_2\), alors

\[d_{k+2} \geq d_{k+1} \geq d_k(1 + d_k) \geq d_k(1 + d_0).\]

Si \(a_k\) et \(b_k\) sont tous deux dans \(I_1\), alors \(a_{k+1}\) et \(b_{k+1}\) sont tous deux dans \(I_2\), et

\[d_{k+2} \geq d_{k+1}(1 + d_{k+1}) \geq d_{k+1}(1 + d_0) = d_k(1 + d_0).\]

Dans les deux cas \(d_{k+2} \geq d_k (1 + d_0)\), et par récurrence

\[d_{2m} \geq d_0 (1 + d_0)^m.\]

Pour \(m\) assez grand, le membre de droite dépasse \(1\) ; mais \(a_{2m}\) et \(b_{2m}\) sont dans \((0, 1)\), donc \(d_{2m} < 1\), ce qui est absurde.

Il existe donc un entier \(n \geq 1\) tel que \(a_{n-1}\) et \(b_{n-1}\) ne sont pas dans le même intervalle, ce qui prouve le résultat. \(\blacksquare\)