Aller au contenu

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é

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

\[a_1 \geq a_2 + \cdots + a_{k+1}\]

(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

\[0 = 1 + 2 + (-3) + (\text{tous les nombres de } A_4, A_5, \ldots, A_{l+2}),\]

soit \(3 + 2(l - 1) = 2l + 1 = k\) termes distincts non nuls.

Donc le plus petit \(n\) cherché est \(n = k + 4\). \(\blacksquare\)