Aller au contenu

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é

On dispose de \(n\) blocs, chacun de masse au moins \(1\), de masse totale \(2n\). Montrer que, pour tout nombre réel \(r\) vérifiant \(0 \leq r \leq 2n - 2\), on peut choisir un ensemble de blocs dont la masse totale est au moins \(r\) et au plus \(r + 2\).

Énoncé original (anglais)

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

\[s - x \leq \frac{n-1}{n}\, s \leq 2(n-1).\]

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ù

\[x - 2 \leq \big(s - (n-1)\big) - 2 = s - \big(2n - (n-1)\big) \leq s - \big(s - (n-1)\big) = n - 1 \leq s - x,\]

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\),

\[S_k = S_{k-1} \cup (x_k + S_{k-1}),\]

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

\[x_k \leq \sum_{j<k} x_j + 2.\]

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

\[2n = \sum_{j=1}^n x_j > (n + 1 - k)(k + 1) + (k - 1).\]

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.

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 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\) ?
  • 2014 N1 ★★☆☆☆ : Quel est le plus grand entier qu'on ne peut pas écrire comme somme de nombres \(2^n - 2^k\) ?
  • 2024 C8 ★★★★★ : On noircit un carré \(2 \times 2\) qui contient une seule case noire : pour quels \(n\) peut-on tout noircir ?
  • 2019 C9 ★★★★★ : Si chaque réel n'a qu'au plus \(k\) échelles de distances dyadiques aux autres, combien d'éléments au plus ?