Shortlist 2025, A2¶
Domaine : Algèbre · Difficulté : ★☆☆☆☆ · Proposé par : China
Concepts : Principe extrémal
Solution officielle : Shortlist officielle 2025 (avec solutions), section A2 (livret PDF)
Énoncé¶
The sunshine cost of a sequence \(a_1, a_2, \ldots, a_{100}\) of integers is the largest possible value of
as \(i\) and \(j\) vary over all integers \(1, 2, \ldots, 100\).
Determine the smallest possible sunshine cost over all sequences \(a_1, a_2, \ldots, a_{100}\) of pairwise distinct integers.
Indices : les idées clés
- Principe extrémal : regarder le plus grand terme \(M\) et le plus petit terme \(m\) de la suite, qui vérifient \(M - m \geq 99\).
- Symétrie \(a_i \mapsto -a_i\) : elle conserve le coût et permet de supposer \(M + m \geq 0\) (solution 1) ou qu'un terme \(a_i\) avec \(i \geq 2\) vérifie \(a_i \geq 50\) (solution 2).
- Additionner deux inégalités bien choisies pour faire disparaître les sommes partielles (solution 1), ou inégalité triangulaire sur les sommes partielles extrêmes (solution 2).
- Construction : alterner termes positifs et négatifs pour que toutes les sommes partielles restent dans \([-25, 25]\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2025 (deux solutions et une remarque).
Solution 1¶
Réponse : le plus petit coût d'ensoleillement possible est \(75\).
Fixons une suite \(a_1, \ldots, a_{100}\) d'entiers deux à deux distincts et notons \(C\) son coût. Montrons d'abord que \(C \geq 75\).
Notons \(M\) et \(m\) la plus grande et la plus petite valeur de la suite (principe extrémal), et \(u, v\) les indices tels que \(a_u = M\) et \(a_v = m\). Comme les \(a_i\) sont distincts, \(M - m \geq 99\). Quitte à remplacer la suite par \(-a_1, \ldots, -a_{100}\) (qui a le même coût \(C\)), on peut supposer \(M + m \geq 0\). On distingue selon \(m\) et \(u\).
-
Si \(m \geq -49\). Avec \(i = 100\) et \(j = v\),
\[C \geq |a_1 + \cdots + a_{100} - a_v| \geq a_1 + \cdots + a_{100} - a_v.\]Les \(99\) termes autres que \(a_v\) sont des entiers distincts strictement supérieurs à \(m\), donc
\[a_1 + \cdots + a_{100} - a_v \geq 99m + (1 + 2 + \cdots + 99) = 99(m + 50),\]et ainsi \(C \geq 99\).
-
Si \(m \leq -50\) et \(u = 1\). Avec \(i = 1\) et \(j = v\), on a \(C \geq |a_1 - a_v| = M - m \geq 99\).
-
Si \(m \leq -50\) et \(u \geq 2\). Avec \(i = u - 1\) et \(j = u\), on obtient \(C \geq a_u - (a_1 + \cdots + a_{u-1})\), puisque \(|x| \geq \pm x\). Avec \(i = u\) et \(j = v\), on a aussi \(C \geq (a_1 + \cdots + a_u) - a_v\). En additionnant :
\[2C \geq a_u - (a_1 + \cdots + a_{u-1}) + (a_1 + \cdots + a_u) - a_v = 2a_u - a_v = 2M - m = 2(M + m) - 3m \geq 150,\]donc \(C \geq 75\).
Dans tous les cas, \(C \geq 75\).
Construction. Considérons la suite
Pour cet exemple, \(-25 \leq a_1 + \cdots + a_i \leq 25\) pour tout \(i\), et \(|a_j| \leq 50\), donc \(|(a_1 + \cdots + a_i) - a_j| \leq 75\), avec égalité pour \(i = 1\), \(j = 2\). Son coût vaut donc \(75\).
Un autre exemple est
qui vérifie aussi \(-25 \leq a_1 + \cdots + a_i \leq 25\) pour tout \(i\) et \(|(a_1 + \cdots + a_i) - a_j| \leq 75\) ; l'égalité est atteinte pour \(i = 50\), \(j = 51\) (ou \(i = 51\), \(j = 50\)). \(\blacksquare\)
Solution 2¶
On donne un autre argument pour la minoration \(C \geq 75\), avec les notations de la solution 1.
Premier cas : \(|a_i| \leq 49\) pour tout \(i \geq 2\). Alors \(\{a_2, \ldots, a_{100}\} = \{-49, -48, \ldots, 48, 49\}\) et, les \(a_i\) étant distincts, \(|a_1| \geq 50\). Si \(a_1 > 0\), en prenant \(i = 1\) et \(j\) l'indice (unique) tel que \(a_j = -49\), on obtient \(C \geq |a_1 - a_j| \geq 99\). Si \(a_1 < 0\), on prend \(j\) tel que \(a_j = 49\) et on obtient de même \(C \geq 99\).
Second cas : \(|a_i| \geq 50\) pour un certain \(i \geq 2\). Quitte à changer tous les signes, on peut supposer \(a_i \geq 50\). Notons \(S\) et \(s\) la plus grande et la plus petite des sommes partielles \(a_1,\ a_1 + a_2,\ \ldots,\ a_1 + \cdots + a_{100}\). Avec cette notation,
On a
Avec l'inégalité triangulaire et \(M - m \geq 99\), on obtient
Comme \(C\) est entier, \(C \geq 75\). \(\blacksquare\)
Remarques¶
Remarque 1. On peut remplacer \(100\) par n'importe quel entier \(n \geq 1\). Le plus petit coût possible pour une suite d'entiers deux à deux distincts est alors
Par exemple, pour \(n \in \{2700, 2701\}\), la réponse est \(2025\). Des solutions analogues fonctionnent en général, mais certaines étapes sont un peu plus fastidieuses quand \(n\) n'est pas multiple de \(4\).