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é

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.