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)

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

É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\)