Shortlist 2020, A7¶

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

Concepts : Sommes, télescopage et transformation d'Abel · Cauchy-Schwarz et lemme de Titu

Solution officielle : Shortlist officielle 2020 (avec solutions), p. 24 (page 26 du PDF)

Pas encore relu

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

Énoncé¶

Let \(n\) and \(k\) be positive integers. Prove that for \(a_1, \ldots, a_n \in [1, 2^k]\) one has

\[\sum_{i=1}^{n} \frac{a_i}{\sqrt{a_1^2 + \cdots + a_i^2}} \leq 4\sqrt{kn}.\]

Indices : les idées clés

Découpage dyadique (solution 1) : on regroupe les indices selon l'intervalle \([2^{j-1}, 2^j]\) qui contient \(a_\ell\) ; dans chaque groupe le dénominateur croît comme \(\sqrt{i}\).
Télescopage : \(\frac{1}{\sqrt{i}} \leq 2(\sqrt{i} - \sqrt{i - 1})\) (solution 1), et le produit \(\prod (1 - x_\ell^2)\) se simplifie en cascade (solution 2).
Cauchy-Schwarz / inégalité QM-AM : \(\sum_{j=1}^{k} \sqrt{|M_j|} \leq \sqrt{k\sum |M_j|}\) (solution 1), et \(\sum x_\ell \leq \sqrt{t \sum x_\ell^2}\) (solution 2).
Récurrence en coupant en deux (solution 2) : la seconde moitié contribue au plus \(\sqrt{2kt}\), grâce à \(1 - y \leq e^{-y}\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2020 (deux solutions et deux remarques).

Solution 1¶

Partitionnons l'ensemble des indices \(\{1, 2, \ldots, n\}\) en sous-ensembles disjoints \(M_1, M_2, \ldots, M_k\) tels que \(a_\ell \in [2^{j-1}, 2^j]\) pour \(\ell \in M_j\) (découpage dyadique). Si \(|M_j| =: p_j\), on a

\[\sum_{\ell \in M_j} \frac{a_\ell}{\sqrt{a_1^2 + \cdots + a_\ell^2}} \leq \sum_{i=1}^{p_j} \frac{2^j}{2^{j-1}\sqrt{i}} = 2\sum_{i=1}^{p_j} \frac{1}{\sqrt{i}},\]

car \(a_\ell \leq 2^j\) et, dans le dénominateur, chaque indice de \(M_j\) déjà rencontré (y compris \(\ell\)) apporte au moins \((2^{j-1})^2\) : si \(\ell\) est le \(i\)-ème élément de \(M_j\), le dénominateur est au moins \(2^{j-1}\sqrt{i}\).

Ensuite, \(\sqrt{i} - \sqrt{i - 1} = \frac{1}{\sqrt{i} + \sqrt{i - 1}} \geq \frac{1}{2\sqrt{i}}\), d'où par télescopage

\[\sum_{\ell \in M_j} \frac{a_\ell}{\sqrt{a_1^2 + \cdots + a_\ell^2}} \leq 2\sum_{i=1}^{p_j} \frac{1}{\sqrt{i}} \leq 2\sum_{i=1}^{p_j} 2\left(\sqrt{i} - \sqrt{i - 1}\right) = 4\sqrt{p_j}.\]

En sommant sur \(j = 1, \ldots, k\) et en utilisant l'inégalité QM-AM (ou Cauchy-Schwarz), on obtient

\[\sum_{\ell=1}^{n} \frac{a_\ell}{\sqrt{a_1^2 + \cdots + a_\ell^2}} \leq 4\sum_{j=1}^{k} \sqrt{|M_j|} \leq 4\sqrt{k\sum_{j=1}^{k} |M_j|} = 4\sqrt{kn}. \ \blacksquare\]

Solution 2¶

On raisonne par récurrence sur \(n\). Si \(n \leq 16\), c'est clair : chaque terme est au plus \(1\), donc la somme ne dépasse pas \(n \leq 4\sqrt{nk}\) (car \(n \leq 16 \leq 16k\)). Pour l'hérédité, de \(1, \ldots, n - 1\) à \(n \geq 17\), on distingue deux cas semblables. Notons

\[x_\ell = \frac{a_\ell}{\sqrt{a_1^2 + \cdots + a_\ell^2}}.\]

Cas 1 : \(n = 2t\). Comme \(1 - y \leq e^{-y}\),

\[\exp\left(-x_{t+1}^2 - \cdots - x_{2t}^2\right) \geq \left(1 - x_{t+1}^2\right)\cdots\left(1 - x_{2t}^2\right) = \frac{a_1^2 + \cdots + a_t^2}{a_1^2 + \cdots + a_{2t}^2} \geq \frac{1}{1 + 4^k}.\]

En effet, \(1 - x_\ell^2 = \frac{a_1^2 + \cdots + a_{\ell-1}^2}{a_1^2 + \cdots + a_\ell^2}\), donc le produit est télescopique ; puis on utilise \(a_{t+i} \leq 2^k a_i\) pour \(i = 1, \ldots, t\), d'où \(a_{t+1}^2 + \cdots + a_{2t}^2 \leq 4^k(a_1^2 + \cdots + a_t^2)\). Par conséquent

\[x_{t+1}^2 + \cdots + x_{2t}^2 \leq \log(4^k + 1) \leq 2k\]

(\(\log\) désignant le logarithme népérien). Par Cauchy-Schwarz, \(x_{t+1} + \cdots + x_{2t} \leq \sqrt{t \cdot 2k} = \sqrt{2kt}\). Avec l'hypothèse de récurrence pour \(n = t\) :

\[\sum_{\ell=1}^{2t} x_\ell \leq 4\sqrt{kt} + \sqrt{2kt} \leq 4\sqrt{2kt}.\]

Cas 2 : \(n = 2t + 1\). De la même façon (en comparant \(a_{t+1+i}\) à \(a_i\)), on obtient \(x_{t+2}^2 + \cdots + x_{2t+1}^2 \leq \log(4^k + 1) \leq 2k\), et, avec l'hypothèse de récurrence pour \(n = t + 1\),

\[\sum_{\ell=1}^{2t+1} x_\ell \leq 4\sqrt{k(t + 1)} + \sqrt{2kt} \leq 4\sqrt{k(2t + 1)}.\]

La dernière inégalité est vraie pour tout \(t \geq 8\) (ce qui est le cas car \(n \geq 17\)), puisque

\[4\sqrt{2t + 1} - \sqrt{2t} \geq 3\sqrt{2t} = \sqrt{18t} \geq \sqrt{16t + 16} = 4\sqrt{t + 1}. \ \blacksquare\]

Remarques¶

Remarque 1 (ranger dans l'ordre croissant). Considérons \(f(a_1, \ldots, a_n) = \sum_{i=1}^{n} \frac{a_i}{\sqrt{a_1^2 + \cdots + a_i^2}}\). Réordonner les variables dans l'ordre croissant ne peut qu'augmenter \(f\). En effet, si \(a_j > a_{j+1}\) pour un indice \(j\), en notant \(a = a_j\), \(b = a_{j+1}\) et \(S = \sqrt{a_1^2 + \cdots + a_{j+1}^2}\),

\[f(a_1, \ldots, a_{j-1}, a_{j+1}, a_j, a_{j+2}, \ldots, a_n) - f(a_1, \ldots, a_n) = \frac{a}{S} + \frac{b}{\sqrt{S^2 - a^2}} - \frac{b}{S} - \frac{a}{\sqrt{S^2 - b^2}},\]

et cette quantité est positive car

\[\frac{b}{\sqrt{S^2 - a^2}} - \frac{b}{S} = \frac{a^2b}{S\sqrt{S^2 - a^2}\left(S + \sqrt{S^2 - a^2}\right)} > \frac{ab^2}{S\sqrt{S^2 - b^2}\left(S + \sqrt{S^2 - b^2}\right)} = \frac{a}{\sqrt{S^2 - b^2}} - \frac{a}{S}.\]

Remarque 2 (optimalité). Si \(k < n\), l'exemple \(a_m := 2^{k(m-1)/n}\) montre que l'énoncé est optimal à une constante multiplicative près. Si \(k \geq n\), c'est la majoration triviale par \(n\) qui est optimale à une constante multiplicative près.