Aller au contenu

Shortlist 2018, C1

Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : Iceland

Concepts : Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2018 (avec solutions), p. 24 (page 26 du PDF)

Énoncé

Soit \(n \geq 3\) un entier. Montrer qu'il existe un ensemble \(S\) de \(2n\) entiers strictement positifs ayant la propriété suivante : pour tout \(m = 2, 3, \ldots, n\), l'ensemble \(S\) peut être partagé en deux parties de même somme, dont l'une a pour cardinal \(m\).

Énoncé original (anglais)

Let \(n \geq 3\) be an integer. Prove that there exists a set \(S\) of \(2n\) positive integers satisfying the following property: For every \(m = 2, 3, \ldots, n\) the set \(S\) can be partitioned into two subsets with equal sums of elements, with one of subsets of cardinality \(m\).

Indices : les idées clés
  • Se ramener à une demi-somme : il suffit de trouver, pour chaque \(m\), une partie à \(m\) éléments dont la somme vaut la moitié de la somme totale.
  • Puissances de 3 : les nombres \(3^k\) et \(2 \cdot 3^k\) permettent d'écrire \(3^n\) comme somme de \(m\) éléments pour chaque \(m\), grâce à \(3^{k+1} = 3^k + 2 \cdot 3^k\).
  • Constructions récursives (remarque) : une suite vérifiant \(s_{2i+1} = s_{2i} + s_{2i-1}\) fournit une construction générale, par exemple avec les nombres de Fibonacci.
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2018 (une solution et une remarque).

Solution

Montrons que l'ensemble

\[S = \{1 \cdot 3^k,\ 2 \cdot 3^k : k = 1, 2, \ldots, n-1\} \cup \left\{1,\ \frac{3^n + 9}{2} - 1\right\}\]

convient. On vérifie aisément que ses \(2n\) éléments sont des entiers positifs distincts (les deux derniers ne sont pas divisibles par \(3\), contrairement aux autres).

La somme des éléments de \(S\) vaut

\[\Sigma = 1 + \left(\frac{3^n + 9}{2} - 1\right) + \sum_{k=1}^{n-1} (1 \cdot 3^k + 2 \cdot 3^k) = \frac{3^n + 9}{2} + \sum_{k=1}^{n-1} 3^{k+1} = \frac{3^n + 9}{2} + \frac{3^{n+1} - 9}{2} = 2 \cdot 3^n.\]

Il suffit donc de trouver, pour tout \(m = 2, 3, \ldots, n\), une partie \(A_m \subset S\) à \(m\) éléments dont la somme vaut \(3^n\) (son complémentaire aura alors la même somme). Une telle partie est

\[A_m = \{2 \cdot 3^k : k = n-m+1, n-m+2, \ldots, n-1\} \cup \{1 \cdot 3^{n-m+1}\}.\]

On a clairement \(|A_m| = m\) (et \(n - m + 1 \geq 1\), donc ces éléments sont bien dans \(S\)). La somme des éléments de \(A_m\) vaut

\[3^{n-m+1} + \sum_{k=n-m+1}^{n-1} 2 \cdot 3^k = 3^{n-m+1} + \frac{2 \cdot 3^n - 2 \cdot 3^{n-m+1}}{2} = 3^n,\]

comme voulu. \(\blacksquare\)

Remarques

Remarque 1 (une construction plus générale). Soit \(s_1, s_2, \ldots, s_{2n-1}\) une suite d'entiers positifs deux à deux distincts telle que \(s_{2i+1} = s_{2i} + s_{2i-1}\) pour tout \(i = 2, 3, \ldots, n-1\), et posons \(s_{2n} = s_1 + s_2 + \cdots + s_{2n-4}\). Si \(s_{2n}\) est distinct des autres termes, l'ensemble \(S = \{s_1, s_2, \ldots, s_{2n}\}\) convient. En effet, la somme de ses éléments vaut

\[\Sigma = \sum_{i=1}^{2n-4} s_i + (s_{2n-3} + s_{2n-2}) + s_{2n-1} + s_{2n} = s_{2n} + s_{2n-1} + s_{2n-1} + s_{2n} = 2 s_{2n} + 2 s_{2n-1},\]

donc

\[\frac{\Sigma}{2} = s_{2n} + s_{2n-1} = s_{2n} + s_{2n-2} + s_{2n-3} = s_{2n} + s_{2n-2} + s_{2n-4} + s_{2n-5} = \cdots,\]

ce qui montre qu'on peut prendre

\[A_m = \{s_{2n}, s_{2n-2}, \ldots, s_{2n-2m+4}, s_{2n-2m+3}\}.\]

La seule condition à assurer est \(s_{2n} \notin \{s_1, \ldots, s_{2n-1}\}\), ce qui s'obtient de nombreuses façons (par exemple en choisissant convenablement \(s_1\) après avoir fixé \(s_2, \ldots, s_{2n-1}\)). La solution ci-dessus en est un cas particulier ; un autre, pour \(n > 3\), est l'ensemble

\[\{F_1, F_2, \ldots, F_{2n-1},\ F_1 + \cdots + F_{2n-4}\},\]

où \(F_1 = 1\), \(F_2 = 2\), \(F_{n+1} = F_n + F_{n-1}\) est la suite de Fibonacci usuelle.

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 A2 ★☆☆☆☆ : Le plus petit ensemble de réels dont chaque élément est somme de \(k\) autres éléments.
  • 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\) ?