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é

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).

Solution

Réponse : \(\left\lfloor \frac{2n - 1}{5} \right\rfloor\).

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é

\[\frac{2x(2x + 1)}{2} \leq nx - \frac{x(x - 1)}{2},\]

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).

\[\begin{array}{c|cccc|cccc|c} \text{Paires} & 3k + 1 & 3k & \cdots & 2k + 2 & 4k + 2 & 4k + 1 & \cdots & 3k + 3 & 3k + 2 \\ & 2 & 4 & \cdots & 2k & 1 & 3 & \cdots & 2k - 1 & 2k + 1 \\ \hline \text{Sommes} & 3k + 3 & 3k + 4 & \cdots & 4k + 2 & 4k + 3 & 4k + 4 & \cdots & 5k + 2 & 5k + 3 \end{array}\]

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

\[\begin{array}{c|cccc|cccc} \text{Paires} & 1 & 2 & \cdots & k & k + 1 & k + 2 & \cdots & 2k + 1 \\ & 4k + 1 & 4k - 1 & \cdots & 2k + 3 & 4k + 2 & 4k & \cdots & 2k + 2 \\ \hline \text{Sommes} & 4k + 2 & 4k + 1 & \cdots & 3k + 3 & 5k + 3 & 5k + 2 & \cdots & 4k + 3 \end{array}\]

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.