Shortlist 2022, A4¶

Domaine : Algèbre · Difficulté : ★★☆☆☆ · Proposé par : Trinidad and Tobago

Solution officielle : Shortlist officielle 2022 (avec solutions), p. 15 (page 17 du PDF)

Énoncé¶

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

\[2^{j-i} x_i x_j > 2^{s-3}.\]

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

\[x_{a+t} \leq 2^t x_a \ \text{ pour } 1 - a \leq t \leq b - a - 1, \qquad x_{b-t} \leq 2^t x_b \ \text{ pour } b - n \leq t \leq b - a - 1.\]

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

\[\sum_{i=1}^{a+u-1} x_i \leq 2^u x_a \left(\frac12 + \frac14 + \cdots + \frac{1}{2^{a+u-1}}\right) < 2^u x_a \leq 1,\]

et de même

\[\sum_{i=b-v+1}^{n} x_i \leq 2^v x_b \left(\frac12 + \frac14 + \cdots + \frac{1}{2^{n-b+v}}\right) < 2^v x_b \leq 1.\]

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

\[s < 2^{u+1} x_a + 2^{v+1} x_b + \big((b - v) - (a + u) - 1\big) = b - a + \big(2^{u+1-\alpha} + 2^{v+1-\beta} - (u + v + 1)\big).\]

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

\[2^{u+1-\alpha} + 2^{v+1-\beta} - u - v - 1 \leq \big(1 + (u + 1 - \alpha)\big) + \big(1 + (v + 1 - \beta)\big) - u - v - 1 = 3 - \alpha - \beta.\]

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

\[2^{s-3} < 2^{b-a-\alpha-\beta} = 2^{b-a} x_a x_b. \qquad \blacksquare\]

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

\[\max_{i<j} 2^{j-i} x_i x_j = 2^2 \left(\frac12 + \frac{1}{2^k}\right)^2,\]

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

\[\max_{i<j} 2^{j-i} x_i x_j > c \, 2^s.\]

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 à

\[s < 2^{u+1} x_a + 2^{v+1} x_b + \big((b - v) - (a + u) - 1\big) = b - a + \big(2^{u+1-\alpha} + 2^{v+1-\beta} - (u + v + 1)\big).\]

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

\[s < b - a + (2 + 2 - u - v - 1) = b - a - u - v + 3.\]

Le livret écrit « \(= b - a - u - v - 3\) » en fin de calcul ; il faut lire \(b - a - u - v + 3\).