Shortlist 2024, A2¶

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

Concepts : Principe extrémal · Récurrence et constructions récursives · Bijections et dénombrement

Solution officielle : Shortlist officielle 2024 (avec solutions), section A2 (livret PDF)

Énoncé¶

Let \(n\) be a positive integer. Find the minimum possible value of

\[S = 2^0 x_0^2 + 2^1 x_1^2 + \cdots + 2^n x_n^2,\]

where \(x_0, x_1, \ldots, x_n\) are nonnegative integers such that \(x_0 + x_1 + \cdots + x_n = n\).

Indices : les idées clés

Principe extrémal (solution 1) : une suite qui réalise le minimum est décroissante (sinon échanger deux termes diminue la somme).
Récurrence (solution 1) : en isolant \(x_0\), le minimum vérifie \(g(n) = \min_{x_0} \big(x_0^2 + 2g(n - x_0)\big)\), et l'on prouve \(g(n) = \frac{n(n+1)}{2}\) par récurrence.
Bijections et dénombrement (solution 2) : le tableau \(a_{i,j} = 2^i(2j+1)\) contient chaque entier strictement positif exactement une fois, et \(2^k x_k^2\) est la somme des \(x_k\) premiers nombres de la ligne \(k\).
Somme des premiers impairs : \(1 + 3 + \cdots + (2x - 1) = x^2\).

Solutions

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

Réponse. La valeur minimale est \(\dfrac{n(n+1)}{2}\).

Solution 1¶

Pour \(n\) fixé, notons \(f(n)\) la valeur minimale de \(S\). Considérons la variante suivante : parmi toutes les suites infinies d'entiers positifs ou nuls \(x_0, x_1, \ldots\), dont un nombre fini seulement sont non nuls, avec \(x_0 + x_1 + \cdots = n\), notons \(g(n)\) la valeur minimale de

\[T = 2^0 x_0^2 + 2^1 x_1^2 + 2^2 x_2^2 + \cdots.\]

Clairement \(g(n) \leq f(n)\). Réciproquement, si une suite \(x_0, x_1, \ldots\) réalise le minimum \(g(n)\), alors \(x_0 \geq x_1 \geq \cdots\), et donc \(x_{n+1} = x_{n+2} = \cdots = 0\). En particulier \(f(n) = g(n)\).

Précision ajoutée : si \(x_i < x_{i+1}\), échanger \(x_i\) et \(x_{i+1}\) diminue \(T\) de \((2^{i+1} - 2^i)(x_{i+1}^2 - x_i^2) > 0\) ; une suite minimale est donc décroissante, et comme la somme vaut \(n\), au plus \(n\) termes sont non nuls.

Cherchons maintenant une formule de récurrence pour \(g(n)\). Pour \(n \geq 1\), une suite minimale vérifie \(x_0 \geq 1\), puisqu'elle est décroissante. Le minimum de

\[2^1 x_1^2 + 2^2 x_2^2 + \cdots = 2\left(2^0 x_1^2 + 2^1 x_2^2 + \cdots\right)\]

sur toutes les suites d'entiers positifs ou nuls avec \(x_1 + x_2 + \cdots = m\) vaut exactement \(2g(m)\). Par conséquent, pour \(n \geq 1\),

\[g(n) = \min_{x_0 \in \{1, 2, \ldots, n\}} \big(x_0^2 + 2g(n - x_0)\big).\]

Montrons \(g(n) = \frac{n(n+1)}{2}\) par récurrence. Clairement \(g(0) = 0\). Supposons le résultat établi pour \(n = 0, 1, \ldots, N-1\). Alors

\[\begin{aligned} x_0^2 + 2g(N - x_0) &= x_0^2 + (N - x_0)(N - x_0 + 1) \\ &= 2x_0^2 - (2N+1)x_0 + N(N+1) \\ &= \tfrac{1}{2}\big[(2x_0 - N)(2x_0 - N - 1) + N^2 + N\big]. \end{aligned} \tag{1}\]

Le produit de deux entiers consécutifs \((2x_0 - N)(2x_0 - N - 1)\) est toujours positif ou nul, et il est nul exactement quand \(2x_0\) est le nombre pair de \(\{N, N+1\}\). Le minimum de la dernière expression de (1) est donc \(\frac{1}{2}(N^2 + N)\), d'où \(g(N) = \frac{N(N+1)}{2}\), ce qui achève la récurrence. \(\blacksquare\)

Solution 2¶

Considérons le tableau suivant, dont les lignes et colonnes sont indexées à partir de \(0\), avec \(a_{i,j} = 2^i(2j+1)\) pour \(i, j \geq 0\) :

	\(j = 0\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)
\(i = 0\)	\(1\)	\(3\)	\(5\)	\(7\)	\(9\)	\(11\)
\(1\)	\(2\)	\(6\)	\(10\)	\(14\)	\(18\)	\(22\)
\(2\)	\(4\)	\(12\)	\(20\)	\(28\)	\(36\)	\(44\)
\(3\)	\(8\)	\(24\)	\(40\)	\(56\)	\(72\)	\(88\)
\(4\)	\(16\)	\(48\)	\(80\)	\(112\)	\(144\)	\(176\)
\(\vdots\)

Tout entier strictement positif s'écrit de façon unique comme produit d'une puissance de \(2\) et d'un nombre impair, donc chaque entier strictement positif apparaît exactement une fois dans ce tableau. Les nombres de chaque ligne et de chaque colonne sont strictement croissants. Comme la somme des \(x\) premiers impairs vaut \(x^2\), la somme des \(x_k\) premiers nombres de la ligne \(k\) vaut \(2^k x_k^2\) : c'est le \(k\)-ième terme de \(S\).

Ainsi \(S\) s'interprète comme la somme de \(n\) nombres pris dans les lignes \(0\) à \(n\) du tableau, en prenant les \(x_k\) nombres les plus à gauche de la ligne \(k\) (avec \(\sum_{k=0}^{n} x_k = n\)). En particulier, ce sont \(n\) entiers strictement positifs distincts, donc \(S \geq 1 + 2 + \cdots + n\). Inversement, la valeur minimale de \(S\) est la somme des \(n\) plus petits nombres du tableau, puisque lignes et colonnes sont strictement croissantes.

Le livret écrit « les \(n\) premières lignes » et \(\sum_{k=1}^{n} x_k = n\) ; avec l'indexation à partir de \(0\), il faut lire les lignes \(0\) à \(n\) et \(\sum_{k=0}^{n} x_k = n\).

De plus, les \(n\) plus petits nombres, à savoir \(1, 2, \ldots, n\), se trouvent dans ces lignes ; donc le minimum de \(S\) vaut

\[1 + 2 + \cdots + n = \frac{n(n+1)}{2}. \qquad \blacksquare\]

Remarques¶

Remarque 1 (cas d'égalité). D'après le tableau de la solution 2, le cas d'égalité est donné par

\[x_i = \left\lfloor \frac{n}{2^{i+1}} + \frac{1}{2} \right\rfloor,\]

c'est-à-dire que \(x_i\) est l'arrondi à l'entier le plus proche de \(\frac{n}{2^{i+1}}\). On en déduit l'identité

\[n = \sum_{i=0}^{\infty} \left\lfloor \frac{n}{2^{i+1}} + \frac{1}{2} \right\rfloor,\]

que l'on peut aussi démontrer par récurrence sur \(n\) : quand \(n\) augmente de \(1\), exactement un terme du membre de droite, celui d'indice \(i = v_2(n)\), augmente de \(1\), les autres restant inchangés.

Remarque 2 (version réelle). Si l'on autorise les \(x_i\) à être des réels positifs, l'inégalité de Cauchy-Schwarz donne

\[\left(2^0 + 2^{-1} + \cdots + 2^{-n}\right)\left(2^0 x_0^2 + 2^1 x_1^2 + \cdots + 2^n x_n^2\right) \geq (x_0 + \cdots + x_n)^2 = n^2,\]

donc \(2^0 x_0^2 + \cdots + 2^n x_n^2 \geq \dfrac{n^2}{2 - 2^{-n}}\), avec égalité pour

\[x_i = \frac{2^{-i} n}{2 - 2^{-n}} \approx \left\lfloor \frac{n}{2^{i+1}} + \frac{1}{2} \right\rfloor.\]

En arrondissant à l'entier le plus proche les termes de la suite optimale réelle, on obtient la suite optimale du problème original. Cette version réelle peut guider vers le cas d'égalité, mais ne semble pas pouvoir se prolonger facilement en une solution complète.