Shortlist 2020, C6¶
Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : Hungary
Concepts : Graphes : degrés, chemins, arbres · Principe extrémal
Solution officielle : Shortlist officielle 2020 (avec solutions), p. 38 (page 40 du PDF)
Problème 3 de l'OIM 2020
Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2020, où il était le problème 3 (jour 1).
Énoncé¶
\(4n\) coins of weights \(1, 2, 3, \ldots, 4n\) are given. Each coin is colored in one of \(n\) colors and there are four coins of each color. Show that all these coins can be partitioned into two sets with the same total weight, such that each set contains two coins of each color.
Indices : les idées clés
- Apparier les pièces de somme \(4n+1\) : il suffit alors de répartir \(2n\) paires en deux groupes de \(n\) paires, chaque groupe ayant automatiquement le même poids total.
- Graphes : degrés, chemins, arbres : un multigraphe auxiliaire (sommets = couleurs, arêtes = paires dans la solution 1 ; sommets = pièces dans la solution 2) traduit le problème en un coloriage d'arêtes ; la solution 1 utilise un circuit eulérien parcouru en alternant les couleurs.
- Principe extrémal (solution 2) : parmi les \(3^n\) graphes « cycliques », on choisit celui qui a le moins de cycles ; un échange d'arêtes montre que tous ses cycles ont une longueur multiple de \(4\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2020 (deux solutions et deux remarques).
Solution 1¶
On regroupe les pièces en paires de poids total \(4n+1\) ; on obtient l'ensemble \(S\) des \(2n\) paires
Il suffit de partager \(S\) en deux ensembles de \(n\) paires chacun, de sorte que chaque ensemble contienne deux pièces de chaque couleur : les deux moitiés auront alors le même poids total \(n(4n+1)\).
On introduit un multigraphe \(G\) (boucles et arêtes multiples autorisées) à \(n\) sommets, chaque sommet correspondant à une couleur. Pour chaque paire de \(S\), on ajoute une arête entre les sommets correspondant aux couleurs des deux pièces de la paire (une boucle si elles ont la même couleur). Chaque sommet est de degré \(4\). Une partition voulue des pièces correspond exactement à un coloriage des arêtes de \(G\) en deux couleurs, rouge et bleu, tel que chaque sommet soit de degré \(2\) pour chaque couleur (degrés rouge et bleu égaux en chaque sommet).
Il suffit de construire un tel coloriage dans chaque composante connexe \(G_1\) de \(G\). Tous les degrés étant pairs, \(G_1\) possède un circuit eulérien \(C\) (un circuit qui passe exactement une fois par chaque arête de \(G_1\)). Le nombre d'arêtes de \(C\) est pair : il vaut le double du nombre de sommets de \(G_1\) (somme des degrés \(= 4 \times\) nombre de sommets). On peut donc colorier les arêtes en parcourant \(C\) et en alternant rouge et bleu, de sorte que deux arêtes consécutives de \(C\) soient toujours de couleurs différentes (y compris la dernière et la première, grâce à la parité). Chaque passage de \(C\) par un sommet utilise une arête rouge et une arête bleue ; ainsi, dans \(G_1\), chaque sommet a autant d'arêtes rouges que de bleues, comme voulu. \(\blacksquare\)
Solution 2¶
Comme dans la solution 1, il suffit de partager les \(2n\) paires \(\{1, 4n\}, \{2, 4n-1\}, \ldots, \{2n, 2n+1\}\) en deux ensembles de \(n\) paires, chacun contenant deux pièces de chaque couleur.
On introduit un multigraphe \(\Gamma\) (arêtes multiples autorisées) dont les sommets sont les pièces : \(4n\) sommets de \(n\) couleurs, quatre de chaque couleur. On relie les paires \(\{1, 4n\}, \{2, 4n-1\}, \ldots, \{2n, 2n+1\}\) par \(2n\) arêtes noires. Ensuite, pour chaque quadruplet monochrome de sommets \(i, j, k, \ell\), on ajoute deux arêtes grises formant un couplage, par exemple \((i, j)\) et \((k, \ell)\). Pour chacune des \(n\) couleurs, on a trois couplages possibles, d'où \(3^n\) façons de choisir les arêtes grises ; chacun des \(3^n\) graphes \(\Gamma\) obtenus est appelé un graphe cyclique. Dans un graphe cyclique, chaque sommet a exactement une arête noire et une arête grise. Donc \(\Gamma\) est une réunion disjointe de cycles, le long desquels arêtes noires et grises alternent (en particulier, tous les cycles sont de longueur paire).
Il suffit de trouver un graphe cyclique dont toutes les longueurs de cycles sont multiples de \(4\). En effet, on part alors d'un sommet de chaque cycle, on le parcourt et on recolorie ses arêtes noires alternativement en rouge et en bleu (c'est cohérent car le cycle contient un nombre pair d'arêtes noires). Les arêtes rouges et bleues définissent la partition voulue : chaque arête grise relie une extrémité d'une arête rouge à une extrémité d'une arête bleue, donc pour chaque quadruplet monochrome, les arêtes grises fournissent une bijection entre les extrémités des arêtes rouges et celles des arêtes bleues ; chaque couleur a ainsi deux pièces de chaque côté.
Parmi tous les graphes cycliques, choisissons (principe extrémal) un graphe \(\Gamma_0\) ayant le nombre minimal de composantes (c'est-à-dire de cycles). L'affirmation suivante achève la preuve.
Affirmation. Dans \(\Gamma_0\), toutes les longueurs de cycles sont multiples de \(4\).
Preuve. Une longueur de cycle vaut le double de son nombre d'arêtes grises ; supposons par l'absurde qu'un cycle \(C_1\) contienne un nombre impair d'arêtes grises. Alors, pour une certaine couleur \(c\), le cycle \(C_1\) contient exactement une arête grise reliant deux sommets \(i, j\) de couleur \(c\), tandis que l'autre arête grise de couleur \(c\), reliant \(k\) et \(\ell\), se trouve dans un autre cycle \(C_2\). (Précision ajoutée : chaque couleur fournit \(0\), \(1\) ou \(2\) arêtes grises à \(C_1\) ; leur total étant impair, une couleur en fournit exactement une.) Supprimons les arêtes \((i, j)\) et \((k, \ell)\) et ajoutons les arêtes \((i, k)\) et \((j, \ell)\). Après cet échange, on obtient de nouveau un graphe cyclique \(\Gamma_0'\), et les deux cycles \(C_1\) et \(C_2\) (devenus deux chemins) sont fusionnés en un seul : le nombre de cycles a diminué de \(1\). Cela contredit le choix de \(\Gamma_0\). \(\square\) \(\blacksquare\)
Remarques¶
Remarque 1. Pour conclure la solution 1, n'importe quelle partition des arêtes de \(G\) en circuits de longueurs paires conviendrait. On l'a obtenue grâce au lemme classique du circuit eulérien : si \(G\) est un graphe connexe dont tous les sommets sont de degré pair, il existe un circuit passant exactement une fois par chaque arête de \(G\).
Remarque 2. L'introduction d'un graphe auxiliaire, et la reformulation du problème en termes de ce graphe, est l'étape cruciale des deux solutions. En fait, le graphe \(G\) de la solution 1 s'obtient à partir de n'importe quel graphe \(\Gamma\) de la solution 2 en fusionnant les sommets de même couleur.