Shortlist 2011, C4¶
Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : non indiqué
Concepts : Double comptage · Principe des tiroirs · Graphes : degrés, chemins, arbres
Solution officielle : Shortlist officielle 2011 (avec solutions), p. 33 (page 34 du PDF)
Énoncé¶
Determine the greatest positive integer \(k\) that satisfies the following property: The set of positive integers can be partitioned into \(k\) subsets \(A_1, A_2, \ldots, A_k\) such that for all integers \(n \geq 15\) and all \(i \in \{1, 2, \ldots, k\}\) there exist two distinct elements of \(A_i\) whose sum is \(n\).
Indices : les idées clés
- Exemple pour \(k = 3\) : \(A_1 = \{1, 2, 3\} \cup \{3m \mid m \geq 4\}\), \(A_2 = \{4, 5, 6\} \cup \{3m - 1 \mid m \geq 4\}\), \(A_3 = \{7, 8, 9\} \cup \{3m - 2 \mid m \geq 4\}\).
- Tiroirs pour \(k = 4\) : chaque \(B_i = A_i \cap \{1, \ldots, 23\}\) doit avoir au moins \(5\) éléments pour représenter \(15, \ldots, 24\) ; l'un en a exactement \(5\).
- Double comptage : les \(10\) sommes de paires de ce \(B_j\) sont exactement \(15, \ldots, 24\), d'où \(4(x_1 + \cdots + x_5) = 195\), impossible ; ou un argument de graphe avec au plus un cycle (solution 2).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2011 (deux solutions et une remarque).
Réponse : le plus grand tel \(k\) est \(3\).
Solution 1¶
Divers exemples montrent que \(k = 3\) a bien la propriété voulue. Par exemple,
Pour vérifier que cette partition convient, on remarque d'abord que les sommes de deux éléments distincts de \(A_i\) représentent évidemment tous les nombres \(n \geq 1 + 12 = 13\) pour \(i = 1\), tous les \(n \geq 4 + 11 = 15\) pour \(i = 2\), et tous les \(n \geq 7 + 10 = 17\) pour \(i = 3\). Il reste à représenter \(15\) et \(16\) comme sommes de deux éléments distincts de \(A_3\) : \(15 = 7 + 8\) et \(16 = 7 + 9\).
Supposons maintenant que, pour un \(k \geq 4\), il existe des ensembles \(A_1, \ldots, A_k\) ayant la propriété. Les ensembles \(A_1\), \(A_2\), \(A_3\), \(A_4 \cup \cdots \cup A_k\) ont alors aussi la propriété ; on peut donc supposer \(k = 4\).
Posons \(B_i = A_i \cap \{1, 2, \ldots, 23\}\) pour \(i = 1, 2, 3, 4\). Pour tout indice \(i\), chacun des dix nombres \(15, 16, \ldots, 24\) s'écrit comme somme de deux éléments distincts de \(B_i\). Cet ensemble doit donc avoir au moins cinq éléments. Comme \(\lvert B_1 \rvert + \lvert B_2 \rvert + \lvert B_3 \rvert + \lvert B_4 \rvert = 23\), il existe un indice \(j\) tel que \(\lvert B_j \rvert = 5\). Écrivons \(B_j = \{x_1, x_2, x_3, x_4, x_5\}\). Les sommes de deux éléments distincts de \(A_j\) représentant \(15, 16, \ldots, 24\) sont alors exactement toutes les sommes de deux éléments de \(B_j\). En calculant de deux façons la somme de ces nombres, on obtient
Le nombre \(195\) devrait donc être divisible par \(4\), ce qui est faux. Cette contradiction achève la solution. \(\blacksquare\)
Remarque. Il existe plusieurs variantes de la preuve que \(k \leq 3\). Par exemple, on peut considérer les ensembles \(C_i = A_i \cap \{1, 2, \ldots, 19\}\) pour \(i = 1, 2, 3, 4\). Comme ci-dessus, on montre que pour un indice \(j\) on a \(\lvert C_j \rvert = 4\), et que les six sommes de paires d'éléments de \(C_j\) représentent tous les nombres \(15, 16, \ldots, 20\). En écrivant \(C_j = \{y_1, y_2, y_3, y_4\}\) avec \(y_1 < y_2 < y_3 < y_4\), on montre sans difficulté que \(C_j = \{7, 8, 9, 11\}\) ; en particulier \(1 \notin C_j\). Il est alors impossible d'écrire \(21\) comme somme de deux éléments distincts de \(A_j\), ce qui conclut.
Solution 2¶
Là encore, on prouve seulement que \(k \leq 3\). Supposons que \(A_1, A_2, \ldots, A_k\) soit une partition ayant la propriété. Construisons un graphe \(G\) sur l'ensemble de sommets \(V = \{1, 2, \ldots, 18\}\) ainsi. Pour chaque \(i \in \{1, 2, \ldots, k\}\) et chaque \(d \in \{15, 16, 17, 19\}\), on choisit une paire d'éléments distincts \(a, b \in A_i\) avec \(a + b = d\), et l'on trace une arête de couleur \(i\) entre \(a\) et \(b\). Par hypothèse, \(G\) a exactement \(4\) arêtes de chaque couleur.
Affirmation. Le graphe \(G\) contient au plus un cycle.
Preuve. Toutes les composantes connexes de \(G\) sont monochromes, et contiennent donc au plus quatre arêtes. Tous les cycles de \(G\) sont donc monochromes et de longueur au plus quatre. De plus, chaque composante contient au plus un cycle, sinon elle aurait au moins cinq arêtes.
Supposons qu'il y ait un cycle de longueur \(4\) dans \(G\), de sommets \(a\), \(b\), \(c\), \(d\) dans cet ordre. Alors \(\{a + b, b + c, c + d, d + a\} = \{15, 16, 17, 19\}\). En sommant, \(2(a + b + c + d) = 15 + 16 + 17 + 19\), ce qui est impossible par parité. Tous les cycles de \(G\) sont donc des triangles.
Si les sommets \(a\), \(b\), \(c\) forment un tel triangle, alors, par un raisonnement analogue, l'ensemble \(\{a + b, b + c, c + a\}\) est égal à \(\{15, 16, 17\}\), \(\{15, 16, 19\}\), \(\{16, 17, 19\}\) ou \(\{15, 17, 19\}\). Le dernier cas est exclu par parité, et dans les trois premiers, \(\{a, b, c\}\) vaut respectivement \(\{7, 8, 9\}\), \(\{6, 9, 10\}\) ou \(\{7, 9, 10\}\). Une composante contenant un cycle contient donc le sommet \(9\). Il y a donc au plus une telle composante, et donc au plus un cycle. \(\square\)
On sait maintenant que \(G\) est un graphe à \(4k\) arêtes, avec au moins \(k\) composantes et au plus un cycle. Par conséquent, \(G\) a au moins \(4k + k - 1\) sommets. Donc \(5k - 1 \leq 18\), et \(k \leq 3\). \(\blacksquare\)