Shortlist 2022, A2¶
Domaine : Algèbre · Difficulté : ★☆☆☆☆ · Proposé par : Slovakia
Concepts : Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2022 (avec solutions), p. 10 (page 12 du PDF)
Énoncé¶
Soit \(k \geq 2\) un entier. Trouver le plus petit entier \(n \geq k + 1\) pour lequel il existe un ensemble de \(n\) nombres réels distincts dont chaque élément s'écrit comme somme de \(k\) autres éléments distincts de l'ensemble.
Énoncé original (anglais)
Let \(k \geq 2\) be an integer. Find the smallest integer \(n \geq k + 1\) with the property that there exists a set of \(n\) distinct real numbers such that each of its elements can be written as a sum of \(k\) other distinct elements of the set.
Indices : les idées clés
- Regarder les extrêmes : le plus petit élément est au moins la somme des \(k\) plus petits autres, le plus grand au plus la somme des \(k\) plus grands autres.
- Symétrie : un ensemble symétrique \(\{\pm 1, \ldots, \pm(l+2)\}\) permet de ne traiter que les éléments positifs ; les paires \(\{-j, j\}\) de somme nulle servent de « remplissage ».
- Récurrence et constructions récursives : le cas \(k\) impair se déduit du cas pair en ajoutant \(0\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2022 (une solution).
Réponse : \(n = k + 4\).
Solution 1¶
Minoration \(n \geq k + 4\). Supposons qu'un tel ensemble à \(n\) éléments existe, et notons ses éléments \(a_1 < a_2 < \cdots < a_n\). Pour écrire \(a_1\) comme somme de \(k\) autres éléments distincts, il faut
(c'est la plus petite somme possible de \(k\) éléments distincts autres que \(a_1\)). De même, pour \(a_n\), il faut \(a_{n-k} + \cdots + a_{n-1} \geq a_n\). On sait aussi que \(n \geq k + 1\).
- Si \(n = k + 1\) : \(a_{k+1}\) est forcément la somme de tous les autres, donc \(a_1 \geq a_2 + \cdots + a_{k+1} > a_1 + \cdots + a_k = a_{k+1}\) (en comparant terme à terme), ce qui contredit \(a_1 < a_{k+1}\).
- Si \(n = k + 2\) : \(a_1 \geq a_2 + \cdots + a_{k+1} \geq a_{k+2}\), contradiction.
- Si \(n = k + 3\) : on a \(a_1 \geq a_2 + \cdots + a_{k+1}\) et \(a_3 + \cdots + a_{k+2} \geq a_{k+3}\). En additionnant et en simplifiant les termes communs \(a_3, \ldots, a_{k+1}\), on obtient \(a_1 + a_{k+2} \geq a_2 + a_{k+3}\), ce qui est absurde car \(a_1 < a_2\) et \(a_{k+2} < a_{k+3}\).
Donc \(n \geq k + 4\).
Construction pour \(k\) pair, \(k = 2l\) (\(l \geq 1\)). Posons \(A_i = \{-i, i\}\) et prenons l'ensemble \(A_1 \cup \cdots \cup A_{l+2}\), qui a exactement \(2l + 4 = k + 4\) éléments. Si un nombre \(i\) s'écrit de la façon voulue, alors \(-i\) aussi (on change tous les signes). Il suffit donc de traiter \(1 \leq i \leq l + 2\).
- Si \(i < l + 2\) : on prend les nombres des \(l - 1\) ensembles \(A_j\) avec \(j \in \{2, \ldots, l+2\} \setminus \{i, i+1\}\) (il en reste au moins \(l-1\) ; on en prend \(l - 1\)), plus les nombres \(i + 1\) et \(-1\). On a bien \(2(l-1) + 2 = k\) nombres distincts, tous différents de \(i\), de somme \(0 + (i + 1) - 1 = i\).
- Si \(i = l + 2\) : on prend les nombres des \(l - 1\) ensembles \(A_2, \ldots, A_l\), plus les nombres \(l + 1\) et \(1\). Leur somme est \(0 + (l+1) + 1 = l + 2\), avec \(k\) termes distincts différents de \(l+2\).
Construction pour \(k\) impair, \(k = 2l + 1\) (\(l \geq 1\)). On ajoute \(0\) à l'ensemble précédent (construit pour \(2l\)), ce qui donne \(2l + 5 = k + 4\) éléments. Pour un élément non nul, on ajoute \(0\) à l'expression construite ci-dessus, ce qui donne \(k\) termes. Et \(0\) s'écrit
soit \(3 + 2(l - 1) = 2l + 1 = k\) termes distincts non nuls.
Donc le plus petit \(n\) cherché est \(n = k + 4\). \(\blacksquare\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2024 C2 ★☆☆☆☆ : Pour quels \(n\) pairs peut-on remplir un tableau pour qu'aucun bloc \(d \times d\) n'ait une somme multiple de \(d\) ?
- 2023 C2 ★☆☆☆☆ : Quelle longueur maximale pour une suite d'entiers bornés sans bloc consécutif annulé par un choix de signes ?
- 2022 C1 ★☆☆☆☆ : Dans toute suite de \(\pm 1\), une sous-suite à sauts d'au plus \(2\) a une somme au moins \(C\) en valeur absolue : quel \(C\) ?
- 2020 C1 ★☆☆☆☆ : Combien de permutations vérifient \(a_1 \leq 2a_2 \leq \cdots \leq n a_n\) ?