Shortlist 2019, A3¶
Domaine : Algèbre · Difficulté : ★★☆☆☆ · Proposé par : New Zealand
Concepts : Principe extrémal
Solution officielle : Shortlist officielle 2019 (avec solutions), section A3 (livret PDF)
Énoncé¶
Let \(n \geq 3\) be a positive integer and let \((a_1, a_2, \ldots, a_n)\) be a strictly increasing sequence of \(n\) positive real numbers with sum equal to \(2\). Let \(X\) be a subset of \(\{1, 2, \ldots, n\}\) such that the value of
is minimised. Prove that there exists a strictly increasing sequence of \(n\) positive real numbers \((b_1, b_2, \ldots, b_n)\) with sum equal to \(2\) such that
Indices : les idées clés
- Exploiter la minimalité de \(X\) : toute modification de \(X\) (échanger deux indices voisins, ajouter \(1\), etc.) ne peut pas faire baisser \(|\Delta|\) ; cela donne des inégalités sur les écarts \(a_{j+1} - a_j\). Les solutions 3 et 4 choisissent en outre un indice extrémal (le plus grand \(k\) vérifiant une propriété, le plus petit terme d'une somme).
- Perturber puis renormaliser (solutions 1 à 3) : on modifie légèrement quelques \(a_i\) pour obtenir \(\sum_{i \in X} c_i = \sum_{i \notin X} c_i\), puis on multiplie par un facteur pour ramener la somme à \(2\).
- Comparer \(X\) à son complémentaire (solutions 3 et 4) : par un appariement injectif \(i \mapsto j_i > i\), ou par l'ordre \(X \preceq Y\) sur les parties.
- Construction directe (solution 4) : une suite \(b_i = i\varepsilon + (\text{constante par morceaux})\) adaptée à la structure de \(X\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2019 (quatre solutions et une remarque).
Remarques communes. On dit qu'une partie \(X\) est \((a_i)\)-minimisante si elle a la propriété de l'énoncé pour la suite \((a_i)\). On note \(X^c\) le complémentaire de \(X\) et \([a, b]\) l'ensemble des entiers \(k\) tels que \(a \leq k \leq b\). Comme \(\left|1 - \sum_{i \in X} a_i\right| = \left|1 - \sum_{i \in X^c} a_i\right|\), on peut échanger \(X\) et \(X^c\) quand c'est commode. Posons
\(X\) est \((a_i)\)-minimisante si et seulement si elle minimise \(|\Delta|\), et \(\sum_{i \in X} a_i = 1\) si et seulement si \(\Delta = 0\). Certaines solutions utilisent une renormalisation : si l'on dispose d'une suite strictement croissante de réels positifs \(c_i\) (souvent obtenue en perturbant les \(a_i\)) telle que \(\sum_{i \in X} c_i = \sum_{i \in X^c} c_i\), on pose \(b_i = 2c_i / \sum_{j=1}^{n} c_j\). Il suffit donc de construire une telle suite sans se soucier que sa somme vaille \(2\). Les solutions 1 et 2 perturbent quelques \(a_i\) (avec renormalisation pour la 1, sans pour la 2). Les solutions 3 et 4 étudient les propriétés de \(X\) ; la 3 perturbe ensuite beaucoup de \(a_i\), la 4 construit directement \((b_i)\) à partir de \(X\) et décrit complètement les parties \(X\) qui sont \((a_i)\)-minimisantes pour au moins une suite \((a_i)\).
Solution 1¶
Sans perte de généralité, \(\sum_{i \in X} a_i \leq 1\), et on peut supposer l'inégalité stricte (sinon \(b_i = a_i\) convient) ; ainsi \(\Delta > 0\). Clairement, \(X\) n'est pas vide.
Si \(n \in X\), on ajoute \(\Delta\) à \(a_n\) : on obtient une suite strictement croissante \((c_i)\) avec \(\sum_{i \in X} c_i = \sum_{i \in X^c} c_i\), et on renormalise. Sinon, il existe \(k\) avec \(k \in X\) et \(k + 1 \in X^c\). Soit \(\delta = a_{k+1} - a_k\).
- Si \(\delta > \Delta\), on ajoute \(\Delta\) à \(a_k\) (la suite reste strictement croissante), puis on renormalise.
- Si \(\delta < \Delta\), la partie \(X \cup \{k+1\} \setminus \{k\}\) donne la valeur \(|\Delta - 2\delta| < \Delta\), ce qui contredit la minimalité de \(X\).
- Si \(\delta = \Delta\), on choisit un indice \(j \neq k, k+1\) (possible car \(n \geq 3\)) et un \(\varepsilon > 0\) plus petit que \(a_1\) et que tous les écarts \(a_{i+1} - a_i\). Si \(j \in X\), on ajoute \(\Delta - \varepsilon\) à \(a_k\) et \(\varepsilon\) à \(a_j\), puis on renormalise. Sinon, on ajoute \(\Delta\) à \(a_k\) et \(\varepsilon/2\) à \(a_{k+1}\), on retranche \(\varepsilon/2\) à \(a_j\), puis on renormalise.
Dans chaque cas, la somme sur \(X\) augmente de \(\Delta\) de plus que la somme sur \(X^c\), la suite reste strictement croissante et positive, d'où le résultat. \(\blacksquare\)
Solution 2¶
C'est une variante de la solution 1, sans renormalisation : on ajoute \(\Delta/2\) du côté de \(X\) et on retire \(\Delta/2\) du côté de \(X^c\), ce qui conserve la somme \(2\). Comme précédemment, on suppose \(\sum_{i \in X} a_i < 1\), donc \(\Delta > 0\).
Supposons qu'il existe \(1 \leq j \leq n - 1\) avec \(j \in X\) et \(j + 1 \in X^c\). Alors \(a_{j+1} - a_j \geq \Delta\), sinon \(X \cup \{j+1\} \setminus \{j\}\) contredirait la minimalité de \(X\).
Si \(a_{j+1} - a_j > \Delta\), on pose
Si \(a_{j+1} - a_j = \Delta\), on choisit \(\varepsilon > 0\) plus petit que \(\Delta/2\), que \(a_1\) et que tous les écarts \(a_{i+1} - a_i\). Si \(|X| \geq 2\), on choisit \(k \in X\) avec \(k \neq j\) et on pose
Sinon, \(|X^c| \geq 2\) ; on choisit \(k \in X^c\) avec \(k \neq j + 1\) et on pose
S'il n'existe aucun \(j\) avec \(j \in X\) et \(j + 1 \in X^c\), alors \(X = [k, n]\) pour un certain \(1 < k \leq n\) (\(X\) n'est pas vide). On a \(a_1 \geq \Delta\), sinon \(X \cup \{1\}\) contredirait la minimalité de \(X\). On pose alors
Dans tous les cas, \((b_i)\) est strictement croissante, positive, de somme \(2\), et \(\sum_{i \in X} b_i = 1\). \(\blacksquare\)
Le livret écrit \(a_1 > \Delta\) ; l'argument donne seulement \(a_1 \geq \Delta\) (si \(a_1 = \Delta\), ajouter \(1\) à \(X\) donne la même valeur), ce qui suffit pour avoir \(b_1 = a_1 - \Delta/2 > 0\).
Solution 3¶
Sans perte de généralité, \(\sum_{i \in X} a_i \leq 1\), donc \(\Delta \geq 0\). Si \(\Delta = 0\), on prend \(b_i = a_i\) ; supposons donc \(\Delta > 0\).
Supposons qu'il existe \(k \leq n\) tel que \(|X \cap [k, n]| > |X^c \cap [k, n]|\). En choisissant le plus grand tel \(k\), on a \(|X \cap [k, n]| - |X^c \cap [k, n]| = 1\). On obtient alors la suite cherchée en partant de \(c_i = a_i\) pour \(i < k\) et \(c_i = a_i + \Delta\) pour \(i \geq k\) (la somme sur \(X\) augmente alors d'exactement \(\Delta\) de plus que celle sur \(X^c\)), puis en renormalisant.
Si un tel \(k\) n'existe pas, on aboutit à une contradiction. Pour chaque \(i \in X\), on peut choisir \(j_i\) avec \(i < j_i \leq n\), de sorte que \(j_i \in X^c\) et que les \(j_i\) soient tous distincts. (Par exemple : nécessairement \(n \in X^c\) ; on descend, et chaque fois qu'on rencontre un \(i \in X\), on prend pour \(j_i\) le plus petit élément de \(X^c\) supérieur à \(i\) et pas encore utilisé.) Soit \(Y\) l'ensemble (éventuellement vide) des éléments de \(X^c\) qui ne sont aucun des \(j_i\). Alors
où chaque terme est strictement positif. Comme \(n \geq 3\), il y a au moins deux termes en tout. Prenons un plus petit terme. On forme \(Z\) à partir de \(X\) en retirant \(i\) et en ajoutant \(j_i\) (si c'est un terme du premier type), ou simplement en ajoutant \(j\) (si c'est un terme du second type). L'expression correspondante de \(\Delta\) pour \(Z\) est la même, avec le signe de ce plus petit terme changé : elle est donc encore positive ou nulle mais strictement inférieure à \(\Delta\), ce qui contredit la minimalité de \(X\). \(\blacksquare\)
Solution 4¶
Cette solution reprend des idées de la solution 3, mais décrit des propriétés de \(X\) suffisantes pour construire une suite \((b_i)\) qui ne dépend pas de \((a_i)\).
Pour deux parties \(X, Y\) de \([1, n]\), les conditions suivantes sont équivalentes :
- \(|X \cap [i, n]| \leq |Y \cap [i, n]|\) pour tout \(1 \leq i \leq n\) ;
- \(|Y| \geq |X|\) et, pour tout \(1 \leq j \leq |X|\), le \(j\)-ième plus grand élément de \(Y\) est au moins égal au \(j\)-ième plus grand élément de \(X\) ;
- il existe une injection \(f : X \to Y\) telle que \(f(i) \geq i\) pour tout \(i \in X\).
Le texte du livret écrit « pour tout \(1 \leq j \leq |Y|\) » dans la deuxième condition ; il faut lire \(1 \leq j \leq |X|\).
Si elles sont vérifiées, on écrit \(X \preceq Y\), et \(X \prec Y\) si de plus \(X \neq Y\). Si \(X \prec Y\), alors \(\sum_{i \in X} a_i < \sum_{i \in Y} a_i\) (la deuxième description le montre clairement).
Montrons d'abord que si \(n \geq 3\) et \(X \prec X^c\), il existe \(Y\) avec \(X \prec Y \prec X^c\). En effet, comme \(|X| \leq |X^c|\), on a \(|X^c| \geq 2\). Soit \(Y\) formé du plus grand élément de \(X^c\) et de tous les éléments de \(X\) sauf le plus grand. Alors \(Y\) est distinct de \(X\) et de \(X^c\), et \(X \preceq Y \preceq X^c\). Mais alors
donc \(\left|1 - \sum_{i \in Y} a_i\right| < \left|1 - \sum_{i \in X} a_i\right|\). Ainsi, si \(X\) est \((a_i)\)-minimisante, on n'a pas \(X \prec X^c\), ni (de même) \(X^c \prec X\). Avec la première description, on en déduit immédiatement :
Affirmation. Il existe \(1 \leq k, \ell \leq n\) tels que \(|X \cap [k, n]| > \frac{n - k + 1}{2}\) et \(|X \cap [\ell, n]| < \frac{n - \ell + 1}{2}\).
Construisons maintenant \((b_i)\). Soient \(k\) et \(\ell\) les plus grandes valeurs vérifiant l'affirmation ; sans perte de généralité \(k = n\) et \(\ell < n\) (sinon on remplace \(X\) par son complémentaire). Par maximalité de \(\ell\), \(n - \ell\) est pair et \(|X \cap [\ell, n]| = \frac{n - \ell}{2}\). Pour \(\varepsilon > 0\) assez petit, on pose
Soit \(M = \sum_{i \in X} i\). On veut
On en tire
et, pour \(\varepsilon > 0\) assez petit, la résolution en \(\gamma\) et \(\delta\) donne \(0 < \delta < \gamma\) (car pour \(\varepsilon = 0\), on obtient \(\delta = 1/\left(\frac{n - \ell}{2} + 1\right)\) et \(\gamma = 2\delta\)). La suite est donc strictement croissante, à valeurs positives, de somme \(2\), et \(\sum_{i \in X} b_i = 1\). \(\blacksquare\)
Remarques¶
Remarque (sur la solution 4). Cette solution montre aussi que l'affirmation décrit complètement les parties \(X\) qui sont \((a_i)\)-minimisantes pour au moins une suite \((a_i)\).
Une autre façon de prouver l'affirmation : montrons l'existence de \(\ell\) (celle de \(k\) s'en déduit en passant au complémentaire). Supposons par l'absurde que \(|X \cap [\ell, n]| \geq \left\lceil \frac{n - \ell + 1}{2} \right\rceil\) pour tout \(1 \leq \ell \leq n\). Si l'inégalité est stricte au moins une fois, considérons \(Y = \{n, n-2, n-4, \ldots\}\). On peut obtenir \(Y\) à partir de \(X\) en retirant éventuellement des éléments et en diminuant d'autres (prendre le plus grand \(k \in X \setminus Y\), s'il existe, le retirer et le remplacer par le plus grand \(j \in X^c\) avec \(j < k\), s'il existe ; ces étapes préservent l'inégalité, et on peut les répéter jusqu'à atteindre \(Y\)). Donc, si l'inégalité est stricte (et ainsi \(X \neq Y\)), on a \(\sum_{i \in X} a_i > \sum_{i \in Y} a_i > 1\), ce qui contredit la minimalité de \(X\). Sinon, on a toujours égalité, c'est-à-dire \(X = Y\). Mais alors, avec \(Z = Y \cup \{n-1\} \setminus \{n\}\), comme \(n \geq 3\),
et \(Z\) contredit la minimalité de \(X\).