Shortlist 2022, A4¶
Domaine : Algèbre · Difficulté : ★★☆☆☆ · Proposé par : Trinidad and Tobago
Concepts : Principe extrémal
Solution officielle : Shortlist officielle 2022 (avec solutions), p. 15 (page 17 du PDF)
Énoncé¶
Soit \(n \geq 3\) un entier, et soient \(x_1, x_2, \ldots, x_n\) des nombres réels de l'intervalle \([0, 1]\). On pose \(s = x_1 + x_2 + \cdots + x_n\), et l'on suppose que \(s \geq 3\). Montrer qu'il existe des entiers \(i\) et \(j\) avec \(1 \leq i < j \leq n\) tels que
Énoncé original (anglais)
Let \(n \geq 3\) be an integer, and let \(x_1, x_2, \ldots, x_n\) be real numbers in the interval \([0, 1]\). Let \(s = x_1 + x_2 + \cdots + x_n\), and assume that \(s \geq 3\). Prove that there exist integers \(i\) and \(j\) with \(1 \leq i < j \leq n\) such that
Indices : les idées clés
- Principe extrémal : on choisit \(a < b\) qui maximisent \(2^{b-a} x_a x_b\) ; la maximalité donne \(x_{a+t} \leq 2^t x_a\) et \(x_{b-t} \leq 2^t x_b\).
- Sommes géométriques : les termes à l'extérieur de \([a+u, b-v]\) sont majorés par des séries géométriques de somme \(< 1\) de chaque côté.
- Inégalité de Bernoulli : \(2^y \leq 1 + y\) pour \(y \in [0, 1]\), appliquée aux exposants \(u + 1 - \alpha\) et \(v + 1 - \beta\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2022 (une solution et deux remarques).
Solution¶
Soient \(1 \leq a < b \leq n\) tels que \(2^{b-a} x_a x_b\) soit maximal. Ce choix de \(a\) et \(b\) implique que
Le livret écrit « \(b - n \leq t \leq b - a + 1\) » pour la seconde condition ; il faut lire \(b - a - 1\). (Par exemple, pour \(t \geq 1\), si \(x_{a+t} > 2^t x_a\), la paire \((a+t, b)\) donnerait \(2^{b-a-t} x_{a+t} x_b > 2^{b-a} x_a x_b\) ; de même dans les autres cas.)
Supposons maintenant que \(x_a \in \left(\frac{1}{2^{u+1}}, \frac{1}{2^u}\right]\) et \(x_b \in \left(\frac{1}{2^{v+1}}, \frac{1}{2^v}\right]\) avec \(u, v\) entiers \(\geq 0\), et écrivons \(x_a = 2^{-\alpha}\), \(x_b = 2^{-\beta}\). Alors
et de même
Autrement dit, la somme des \(x_i\) pour \(i\) hors de l'intervalle \([a+u, b-v]\) est strictement inférieure à \(2\). Comme la somme totale est au moins \(3\) et que chaque terme est au plus \(1\), cet intervalle contient au moins deux entiers, c'est-à-dire \(a + u < b - v\). Ainsi, en majorant comme ci-dessus la somme des \(x_i\) pour \(i \in [1, a+u] \cup [b-v, n]\) (on obtient \(< 2^{u+1}x_a\) et \(< 2^{v+1}x_b\)), et en majorant trivialement par \(1\) chaque \(x_i\) pour \(i \in (a+u, b-v)\), on obtient
Rappelons que \(\alpha \in [u, u+1)\) et \(\beta \in [v, v+1)\), donc \(u + 1 - \alpha\) et \(v + 1 - \beta\) sont dans \((0, 1]\) ; l'inégalité de Bernoulli (\(2^y \leq 1 + y\) pour \(0 \leq y \leq 1\)) donne
Le livret écrit \(\alpha \in (u, u+1]\) et \(\beta \in (v, v+1]\) ; comme \(x_a = 2^{-\alpha} \in \left(2^{-u-1}, 2^{-u}\right]\), il faut lire \(\alpha \in [u, u+1)\), ce qui ne change pas l'argument.
Il s'ensuit que \(s - 3 < b - a - \alpha - \beta\), et donc
Remarques¶
Remarque 1 (l'inégalité est optimale). Supposons \(n = 2k + 1\) et posons \(x_{k+1} = 1\), \(x_k = x_{k+2} = \frac12 + \frac{1}{2^k}\), et \(x_{k+1-t} = x_{k+1+t} = \frac{1}{2^t}\) pour \(2 \leq t \leq k\). Alors \(s = 3\) (donc le membre de droite vaut \(1\)), et
qui peut être rendu arbitrairement proche de \(1\). On peut augmenter \(s\) en ajoutant des \(1\) au milieu (ce qui permet aussi de traiter \(n\) pair).
Remarque 2 (variante avec une constante). Une autre formulation demande de montrer qu'il existe une constante \(c > 0\) (ou de trouver la meilleure) telle que
Ce qui précède montre que \(c = 1/8\) est optimal. Pour \(c = 1/32\), on peut terminer plus simplement : on arrive comme plus haut à
Or \(2^{b-a} x_a x_b \geq 2^{b-a} 2^{-u-1} 2^{-v-1}\), donc il suffit de montrer \(s - 5 < b - a - u - v - 2\), soit \(s < b - a - u - v + 3\). Comme \(u + 1 - \alpha \leq 1\) et \(v + 1 - \beta \leq 1\), on a \(2^{u+1-\alpha} + 2^{v+1-\beta} \leq 4\), et donc
Le livret écrit « \(= b - a - u - v - 3\) » en fin de calcul ; il faut lire \(b - a - u - v + 3\).
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2019 A3 ★★☆☆☆ : La partie qui approche le mieux \(1\) pour une suite croissante de somme \(2\) l'atteint exactement pour une autre suite.
- 2011 C2 ★★☆☆☆ : \(1000\) élèves en cercle : un groupe de \(2k\) élèves consécutifs a autant de filles dans chaque moitié, avec \(100 \leq k \leq 300\).
- 2007 A1 ★★☆☆☆ · OIM P1 : Approcher une suite quelconque par une suite croissante : l'écart minimal vaut exactement \(d/2\).
- 2007 C2 ★★☆☆☆ : Un carré découpé en rectangles sans droite de coupe traversante contient un rectangle qui ne touche pas le bord.