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é¶
Déterminer le plus grand entier \(k\) strictement positif ayant la propriété suivante : l'ensemble des entiers strictement positifs peut être partagé en \(k\) parties \(A_1, A_2, \ldots, A_k\) de sorte que, pour tout entier \(n \geq 15\) et tout \(i \in \{1, 2, \ldots, k\}\), il existe deux éléments distincts de \(A_i\) dont la somme vaut \(n\).
Énoncé original (anglais)
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\)
Problèmes voisins¶
Sur les mêmes idées, à une difficulté proche :
- 2015 C2 ★☆☆☆☆ · OIM P1 : Des ensembles de points où toute paire a un point équidistant, mais où aucun point n'est centre de trois autres.
- 2015 C5 ★★★☆☆ · OIM P6 : Une suite bornée où les \(i + a_i\) sont distincts a des sommes partielles proches de celles d'une suite constante.
- 2013 A4 ★★★☆☆ : Une suite périodique presque croissante vérifiant \(a_{a_i} \leq n + i - 1\) a une somme au plus \(n^2\).
- 2010 C5 ★★★☆☆ : Dans un tournoi sans un certain type de quadruplet, la somme des \((w_i - \ell_i)^3\) est positive.