Shortlist 2014, A3¶
Domaine : Algèbre · Difficulté : ★★☆☆☆ · Proposé par : Georgia
Concepts : Principe extrémal · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2014 (avec solutions), p. 12 (page 13 du PDF)
Énoncé¶
For a sequence \(x_1, x_2, \ldots, x_n\) of real numbers, we define its price as
Given \(n\) real numbers, Dave and George want to arrange them into a sequence with a low price. Diligent Dave checks all possible ways and finds the minimum possible price \(D\). Greedy George, on the other hand, chooses \(x_1\) such that \(\lvert x_1 \rvert\) is as small as possible; among the remaining numbers, he chooses \(x_2\) such that \(\lvert x_1 + x_2 \rvert\) is as small as possible, and so on. Thus, in the \(i\)-th step he chooses \(x_i\) among the remaining numbers so as to minimise the value of \(\lvert x_1 + x_2 + \cdots + x_i \rvert\). In each step, if several numbers provide the same value, George chooses one at random. Finally he gets a sequence with price \(G\).
Find the least possible constant \(c\) such that for every positive integer \(n\), for every collection of \(n\) real numbers, and for every possible sequence that George might obtain, the resulting values satisfy the inequality \(G \leq cD\).
Indices : les idées clés
- L'exemple \(1, -1, 2, -2\) : Dave obtient \(D = 1\) (avec \(1, -2, 2, -1\)) et George peut obtenir \(G = 2\), donc \(c \geq 2\).
- Deux minorations de \(D\) : \(D \geq S\), la valeur absolue de la somme totale, et \(D \geq \frac{M}{2}\), où \(M\) est le plus grand \(\lvert x_i \rvert\) (inégalité triangulaire).
- Récurrence : chaque somme partielle de George vérifie \(\lvert h_i \rvert \leq \max(M, S)\) ; quand il reste des nombres des deux signes, le choix glouton est au moins aussi bon que d'ajouter un nombre de signe opposé à \(h_{i-1}\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2014 (une solution et deux remarques).
Solution¶
Réponse : \(c = 2\).
Si les nombres de départ sont \(1, -1, 2, -2\), Dave peut les ranger en \(1, -2, 2, -1\), tandis que George peut obtenir la suite \(1, -1, 2, -2\) ; on a alors \(D = 1\) et \(G = 2\). Donc \(c \geq 2\).
Il reste à montrer que \(G \leq 2D\). Soient \(x_1, x_2, \ldots, x_n\) les nombres dont disposent Dave et George, et supposons qu'ils les rangent respectivement en \(d_1, d_2, \ldots, d_n\) et \(g_1, g_2, \ldots, g_n\). Posons
On affirme que
Ces inégalités donnent l'estimation voulue, car \(G \leq \max\{M, S\} \leq \max\{M, 2S\} \leq 2D\).
L'inégalité (1) découle directement de la définition du prix.
Pour (2), considérons un indice \(i\) tel que \(\lvert d_i \rvert = M\). Alors
Il reste à établir (3). Posons \(h_i = g_1 + g_2 + \cdots + g_i\). Montrons par récurrence sur \(i\) que \(\lvert h_i \rvert \leq N\). Le cas \(i = 1\) est vrai, car \(\lvert h_1 \rvert = \lvert g_1 \rvert \leq M \leq N\). Notons aussi que \(\lvert h_n \rvert = S \leq N\).
Pour l'hérédité, supposons \(\lvert h_{i-1} \rvert \leq N\). On distingue deux cas.
Cas 1 : parmi les nombres \(g_i, g_{i+1}, \ldots, g_n\), il n'y en a pas deux de signes opposés. Quitte à changer tous les signes, on peut supposer qu'ils sont tous positifs ou nuls. Alors \(h_{i-1} \leq h_i \leq \cdots \leq h_n\), donc
Cas 2 : parmi les nombres \(g_i, g_{i+1}, \ldots, g_n\), il y en a des positifs et des négatifs. Il existe alors un indice \(j \geq i\) tel que \(h_{i-1} g_j \leq 0\). Par définition de la suite de George,
la deuxième inégalité venant de ce que \(h_{i-1}\) et \(g_j\) sont de signes opposés. L'hérédité est établie. \(\blacksquare\)
Remarques¶
Remarque 1. On peut aussi établir les inégalités plus faibles \(D \geq \frac{M}{2}\) et \(G \leq D + \frac{M}{2}\), dont le résultat découle également.
Remarque 2. On peut chercher plus précisément la meilleure constante \(c\) quand \(n\) est fixé. Pour \(n = 1\) ou \(2\), la réponse est \(c = 1\). Pour \(n = 3\), la réponse est \(c = \frac{3}{2}\), atteinte par exemple pour \(1, 2, -4\). Enfin, pour \(n \geq 4\), la réponse est \(c = 2\) : les arguments de la solution s'appliquent, et la valeur est atteinte par exemple pour la même collection \(1, -1, 2, -2\) complétée par des zéros.