Shortlist 2019, C2¶
Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : Thailand
Concepts : Récurrence et constructions récursives · Principe extrémal
Solution officielle : Shortlist officielle 2019 (avec solutions), section C2 (livret PDF)
Énoncé¶
You are given a set of \(n\) blocks, each weighing at least \(1\); their total weight is \(2n\). Prove that for every real number \(r\) with \(0 \leq r \leq 2n - 2\) you can choose a subset of the blocks whose total weight is at least \(r\) but at most \(r + 2\).
Indices : les idées clés
- Renforcer l'énoncé (solution 1) : prouver le résultat pour un poids total \(s \leq 2n\) et tout \(r \in [-2, s]\), ce qui rend la récurrence possible.
- Récurrence : sur le nombre de blocs (solution 1), ou sur le nombre \(k\) de blocs déjà utilisés (solution 2).
- Principe extrémal (solution 1) : on retire le bloc le plus lourd, de poids \(x \geq s/n\).
- Pas des sommes partielles (solution 2) : avec les poids triés, il suffit que chaque \(x_k\) soit au plus la somme des précédents plus \(2\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2019 (deux solutions et une remarque).
Solution 1¶
On démontre par récurrence sur \(n\) l'énoncé plus général suivant.
Affirmation. On dispose de \(n\) blocs, chacun de poids au moins \(1\), de poids total \(s \leq 2n\). Alors pour tout \(r\) avec \(-2 \leq r \leq s\), on peut choisir certains blocs dont le poids total est au moins \(r\) et au plus \(r + 2\).
(Avec \(s = 2n\), cela contient l'énoncé, puisque \([0, 2n-2] \subset [-2, 2n]\).)
Preuve. Le cas \(n = 1\) est trivial. Pour l'hérédité, soit \(x\) le plus grand poids d'un bloc. On a \(x \geq s/n\), donc
Si on met de côté un bloc de poids \(x\), l'hypothèse de récurrence s'applique aux \(n - 1\) blocs restants (de poids total \(s - x \leq 2(n-1)\)) et donne l'affirmation pour tout \(-2 \leq r \leq s - x\). En ajoutant le bloc mis de côté à chacun de ces choix, on obtient l'affirmation pour \(x - 2 \leq r \leq s\). Si \(x - 2 \leq s - x\), on a donc couvert tout l'intervalle \([-2, s]\). Or chaque bloc pèse au moins \(1\), donc \(x \leq s - (n-1)\) et \(s - x \geq n - 1\), d'où
comme voulu. \(\blacksquare\)
Solution 2¶
Soient \(x_1 \leq x_2 \leq \cdots \leq x_n\) les poids rangés par ordre croissant. Soit \(S\) l'ensemble des sommes \(\sum_{j \in J} x_j\) pour \(J \subseteq \{1, \ldots, n\}\). On veut montrer que le pas de \(S\) — le plus grand écart entre deux éléments consécutifs — est au plus \(2\). (Comme \(0 \in S\) et \(2n \in S\), cela donne, pour tout \(r \in [0, 2n-2]\), un élément de \(S\) dans \([r, r+2]\).)
Pour \(0 \leq k \leq n\), soit \(S_k\) l'ensemble des sommes \(\sum_{i \in J} x_i\) pour \(J \subseteq \{1, \ldots, k\}\). Montrons par récurrence sur \(k\) que le pas de \(S_k\) est au plus \(2\). Le cas \(k = 0\) est trivial (\(S_0 = \{0\}\)). Pour \(k > 0\),
où \(x_k + S_{k-1} = \{x_k + s : s \in S_{k-1}\}\). Le plus grand élément de \(S_{k-1}\) est \(\sum_{j<k} x_j\) et le plus petit de \(x_k + S_{k-1}\) est \(x_k\) ; il suffit donc de prouver que
Sinon, on aurait pour tout \(l \geq k\) : \(x_l \geq x_k > \sum_{j<k} x_j + 2 \geq (k-1) + 2 = k + 1\), et donc
Cela se réécrit \(n > k(n + 1 - k)\), ce qui est faux pour \(1 \leq k \leq n\) (car \(k(n+1-k) - n = (k-1)(n-k) \geq 0\)). Contradiction. \(\blacksquare\)
Remarques¶
Remarque. Au lieu de faire la récurrence sur les ensembles de blocs de poids total \(s \leq 2n\), on pourrait ne prouver le résultat que pour \(s = 2n\) ; il faudrait alors, dans l'hérédité, multiplier les poids par un facteur convenable avant d'appliquer l'hypothèse de récurrence.