Shortlist 2012, C2¶
Domaine : Combinatoire · Difficulté : ★☆☆☆☆ · Proposé par : non indiqué
Concepts : Double comptage · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2012 (avec solutions), p. 20 (page 20 du PDF)
Énoncé¶
Soit \(n \geq 1\) un entier. Quel est le nombre maximal de paires disjointes d'éléments de l'ensemble \(\{1, 2, \ldots, n\}\) telles que les sommes des différentes paires soient des entiers distincts au plus égaux à \(n\) ?
Énoncé original (anglais)
Let \(n \geq 1\) be an integer. What is the maximum number of disjoint pairs of elements of the set \(\{1, 2, \ldots, n\}\) such that the sums of the different pairs are different integers not exceeding \(n\)?
Indices : les idées clés
- Double comptage de la somme \(S\) des \(2x\) nombres : \(S \geq 1 + 2 + \cdots + 2x\) (paires disjointes) et \(S \leq n + (n - 1) + \cdots + (n - x + 1)\) (sommes distinctes et au plus \(n\)).
- Borne : on obtient \(x \leq \frac{2n - 1}{5}\), donc au plus \(\left\lfloor \frac{2n - 1}{5} \right\rfloor\) paires.
- Construction pour \(n = 5k + 3\) : \(2k + 1\) paires utilisant \(1, \ldots, 4k + 2\) et de sommes \(3k + 3, \ldots, 5k + 3\), puis on adapte aux autres restes modulo \(5\).
Solutions
Les solutions ci-dessous suivent la solution officielle de la Shortlist 2012 (une solution et une remarque).
Réponse : \(\left\lfloor \frac{2n - 1}{5} \right\rfloor\).
Solution¶
Considérons \(x\) telles paires dans \(\{1, 2, \ldots, n\}\). La somme \(S\) des \(2x\) nombres qu'elles contiennent est au moins \(1 + 2 + \cdots + 2x\), puisque les paires sont disjointes. D'autre part, \(S \leq n + (n - 1) + \cdots + (n - x + 1)\), puisque les sommes des paires sont distinctes et ne dépassent pas \(n\). Cela donne l'inégalité
qui mène à \(x \leq \frac{2n - 1}{5}\). Il y a donc au plus \(\left\lfloor \frac{2n - 1}{5} \right\rfloor\) paires ayant les propriétés voulues.
Donnons une construction avec exactement \(\left\lfloor \frac{2n - 1}{5} \right\rfloor\) paires. Considérons d'abord le cas \(n = 5k + 3\) avec \(k \geq 0\), où \(\left\lfloor \frac{2n - 1}{5} \right\rfloor = 2k + 1\). Les paires sont données dans le tableau suivant (chaque colonne est une paire).
Les \(2k + 1\) paires utilisent tous les nombres de \(1\) à \(4k + 2\) ; leurs sommes sont tous les nombres de \(3k + 3\) à \(5k + 3\). La même construction fonctionne pour \(n = 5k + 4\) et \(n = 5k + 5\) avec \(k \geq 0\) : dans ces cas, le nombre \(\left\lfloor \frac{2n - 1}{5} \right\rfloor\) de paires vaut encore \(2k + 1\), et les nombres du tableau ne dépassent pas \(5k + 3\). Pour \(n = 5k + 2\) avec \(k \geq 0\), il ne faut que \(2k\) paires ; on les obtient en ignorant la dernière colonne du tableau (ce qui retire \(5k + 3\)). Enfin, il faut aussi \(2k\) paires pour \(n = 5k + 1\) avec \(k \geq 0\) ; il suffit alors d'ignorer la dernière colonne du tableau, puis de soustraire \(1\) à chaque nombre de la première ligne. \(\blacksquare\)
Remarque¶
La construction n'est pas unique. Par exemple, le tableau suivant donne un autre ensemble de \(2k + 1\) paires pour les cas \(n = 5k + 3\), \(n = 5k + 4\) et \(n = 5k + 5\).
Pour \(n = 5k + 2\), le tableau serait le même, avec la paire \((k + 1, 4k + 2)\) retirée. Pour \(n = 5k + 1\), on retire la dernière colonne et l'on soustrait \(2\) à chaque nombre de la deuxième ligne.
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2014 C1 ★☆☆☆☆ : Découper un rectangle en évitant \(n\) points intérieurs demande au moins \(n + 1\) petits rectangles.
- 2024 C3 ★★☆☆☆ : Des chevaliers en cercle échangent leurs places pour serrer la main de leur partenaire : combien d'échanges ?
- 2009 C2 ★★☆☆☆ : Combien de triplets de somme \(n\) peut-on choisir sans que deux d'entre eux partagent une coordonnée ?
- 2013 A4 ★★★☆☆ : Une suite périodique presque croissante vérifiant \(a_{a_i} \leq n + i - 1\) a une somme au plus \(n^2\).