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é

On définit la fonction \(f : (0, 1) \to (0, 1)\) par

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

Soient \(a\) et \(b\) deux nombres réels tels que \(0 < a < b < 1\). On définit les suites \(a_n\) et \(b_n\) par \(a_0 = a\), \(b_0 = b\), et \(a_n = f(a_{n-1})\), \(b_n = f(b_{n-1})\) pour \(n > 0\). Montrer qu'il existe un entier \(n\) strictement positif tel que

\[(a_n - a_{n-1})(b_n - b_{n-1}) < 0.\]
Énoncé original (anglais)

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

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2017 A4 ★★☆☆☆ : Une suite définie par \(a_n = -\max_{i+j=n}(a_i + a_j)\) au-delà d'un certain rang est bornée.
  • 2017 C3 ★★☆☆☆ : On place des puissances de \(2\) et on fusionne les égales sur \(9\) cases : combien de coups au plus pour finir avec \(2^n\) ?
  • 2015 N4 ★★☆☆☆ : Avec \(a_{n+1} = \gcd(a_n, b_n) + 1\) et \(b_{n+1} = \operatorname{lcm}(a_n, b_n) - 1\), la suite \((a_n)\) finit par être périodique.
  • 2011 A2 ★★☆☆☆ : Trouver les suites de \(2011\) entiers telles que \(x_1^n + 2x_2^n + \cdots + 2011 x_{2011}^n\) soit toujours de la forme \(a^{n+1} + 1\).