Shortlist 2013, C3¶
Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Japan
Concepts : Graphes : degrés, chemins, arbres · Coloriages et pavages · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2013 (avec solutions), p. 25 (page 25 du PDF)
Énoncé¶
A crazy physicist discovered a new kind of particle which he called an imon, after some of them mysteriously appeared in his lab. Some pairs of imons in the lab can be entangled, and each imon can participate in many entanglement relations. The physicist has found a way to perform the following two kinds of operations with these particles, one operation at a time.
(i) If some imon is entangled with an odd number of other imons in the lab, then the physicist can destroy it.
(ii) At any moment, he may double the whole family of imons in his lab by creating a copy \(I'\) of each imon \(I\). During this procedure, the two copies \(I'\) and \(J'\) become entangled if and only if the original imons \(I\) and \(J\) are entangled, and each copy \(I'\) becomes entangled with its original imon \(I\); no other entanglements occur or disappear at this moment.
Prove that the physicist may apply a sequence of such operations resulting in a family of imons, no two of which are entangled.
Indices : les idées clés
- Graphes : les imons sont les sommets, les intrications les arêtes ; on veut un graphe sans arête.
- Coloriage propre (solution 1) : on supprime des sommets de degré impair jusqu'à ce que tous les degrés soient pairs, on double (tous les degrés deviennent impairs), et la copie reçoit la couleur suivante modulo \(n\).
- Récurrence sur le nombre de couleurs : on supprime alors une classe de couleur entière, dont les sommets ne sont pas reliés entre eux.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2013 (deux solutions et une remarque).
Solution 1¶
Considérons le graphe dont les sommets sont les imons, deux imons étant reliés si et seulement s'ils sont intriqués. On rappelle qu'un coloriage propre d'un graphe \(G\) est un coloriage de ses sommets en plusieurs couleurs tel que deux sommets reliés aient toujours des couleurs différentes.
Lemme. Supposons qu'un graphe \(G\) admette un coloriage propre en \(n\) couleurs (\(n > 1\)). On peut alors effectuer une suite d'opérations aboutissant à un graphe qui admet un coloriage propre en \(n - 1\) couleurs.
Preuve. Appliquons l'opération (i) à des sommets convenables tant que c'est possible. Le nombre de sommets diminuant, on aboutit à un graphe dont tous les degrés sont pairs. Ce graphe admet évidemment encore un coloriage propre en \(n\) couleurs \(1, \ldots, n\) ; fixons-le.
Appliquons maintenant l'opération (ii) à ce graphe. Le graphe obtenu admet encore un coloriage propre en \(n\) couleurs : on garde les couleurs des sommets d'origine et l'on colorie le sommet \(I'\) en la couleur \(k + 1 \pmod n\) si le sommet \(I\) a la couleur \(k\). Deux sommets d'origine reliés ont toujours des couleurs différentes, de même que leurs deux copies reliées. D'autre part, les sommets \(I\) et \(I'\) ont des couleurs différentes puisque \(n > 1\).
Tous les degrés du graphe obtenu sont impairs ; on peut donc appliquer l'opération (i) pour supprimer un par un tous les sommets de couleur \(n\). Deux d'entre eux ne sont jamais reliés par une arête, donc leurs degrés ne changent pas pendant le processus. On obtient ainsi un graphe admettant un coloriage propre en \(n - 1\) couleurs, comme voulu. \(\square\)
Supposons maintenant que le graphe \(G\) ait \(n\) sommets ; il admet alors un coloriage propre en \(n\) couleurs. En appliquant le lemme de façon répétée, on obtient finalement un graphe admettant un coloriage propre en une seule couleur, c'est-à-dire un graphe sans arête, comme voulu. \(\blacksquare\)
Solution 2¶
On utilise encore le langage des graphes.
I. Commençons par l'observation suivante.
Lemme. Supposons qu'un graphe \(G\) contienne un sommet isolé \(A\), et que le graphe \(G^\circ\) soit obtenu en supprimant ce sommet. S'il existe une suite d'opérations qui transforme \(G^\circ\) en un graphe sans arête, alors il en existe une aussi pour \(G\).
Preuve. Considérons une opération applicable à \(G^\circ\), qui donne un graphe \(G^\circ_1\) ; il existe alors une suite d'opérations applicables à \(G\) qui donne un graphe \(G_1\) ne différant de \(G^\circ_1\) que par l'ajout d'un sommet isolé \(A\). En effet, si l'opération est de type (i), on la répète simplement dans \(G\). Sinon, elle est de type (ii) ; on l'applique à \(G\), puis on supprime le sommet \(A'\) (il est de degré \(1\)). On transforme ainsi, étape par étape, le procédé pour \(G^\circ\) en un procédé pour \(G\). \(\square\)
D'après ce lemme, si à un moment un graphe contient un sommet isolé, on peut simplement le supprimer ; appelons cela l'opération (iii).
II. Soit \(V = \{A_1^0, \ldots, A_n^0\}\) l'ensemble des sommets du graphe initial. Décrivons les graphes qui peuvent apparaître au cours des opérations. Supposons que l'opération (ii) ait été appliquée \(m\) fois. Si ce sont les seules opérations appliquées, les sommets du graphe obtenu \(G_n^m\) peuvent être numérotés
où \(A_i^0\) est l'« ancêtre » commun de tous les sommets \(A_i^j\), et où l'écriture binaire de \(j\) (complétée par des zéros à gauche pour avoir \(m\) chiffres) « garde l'historique » du sommet : le \(d\)-ème chiffre en partant de la droite vaut \(0\) si, au \(d\)-ème doublement, l'ancêtre de \(A_i^j\) était dans la partie d'origine, et \(1\) s'il était dans la copie.
Deux sommets \(A_i^j\) et \(A_k^\ell\) de \(G_n^m\) sont alors reliés si et seulement si (1) \(j = \ell\) et \(A_i^0\), \(A_k^0\) étaient reliés (ces sommets sont donc apparus lors d'une même application de l'opération (ii)) ; ou (2) \(i = k\) et les écritures binaires de \(j\) et \(\ell\) diffèrent d'exactement un chiffre (leurs ancêtres ont été reliés comme copie et original lors d'une application de (ii)).
Si des opérations (i) ont été appliquées au cours du processus, certains sommets de \(G_n^m\) ont simplement disparu. Dans tous les cas, le graphe obtenu est un sous-graphe induit de \(G_n^m\).
III. Montrons enfin qu'à partir de tout sous-graphe (pas forcément induit) de \(G_n^m\), on peut obtenir un graphe sans sommet à l'aide des opérations (i), (ii) et (iii). On procède par récurrence sur \(n\) ; le cas \(n = 0\) est évident.
Pour l'hérédité, montrons comment appliquer des opérations pour obtenir un graphe sans sommet de la forme \(A_n^j\). On procède en trois étapes.
Étape 1. On applique l'opération (i) à des sommets convenables tant que c'est possible. Dans le graphe obtenu, tous les degrés sont pairs.
Étape 2. On applique l'opération (ii), et l'on obtient un sous-graphe de \(G_n^{m+1}\) dont tous les degrés sont impairs. Dans ce graphe, on supprime un par un tous les sommets \(A_n^j\) pour lesquels la somme des chiffres binaires de \(j\) est paire ; c'est possible car il n'y a pas d'arête entre ces sommets, donc leurs degrés restent impairs. Ensuite, on supprime tous les sommets isolés.
Étape 3. Considérons enfin un sommet restant \(A_n^j\) (la somme des chiffres de \(j\) est alors impaire). Si son degré est impair, on le supprime simplement. Sinon, comme \(A_n^j\) n'est pas isolé, considérons un sommet qui lui est adjacent. Il est de la forme \(A_k^j\) avec \(k < n\) (sinon il serait de la forme \(A_n^\ell\), où \(\ell\) a une somme de chiffres paire ; mais un tel sommet a déjà été supprimé à l'étape 2). Aucun voisin de \(A_k^j\) n'a été supprimé aux étapes 2 et 3, donc il est de degré impair. On supprime alors successivement \(A_k^j\) et \(A_n^j\).
Cette suppression n'affecte pas l'applicabilité de cette étape aux autres sommets, puisque deux sommets \(A_i^j\) et \(A_k^\ell\) avec \(j \neq \ell\) de sommes de chiffres impaires ne sont jamais reliés. On supprime ainsi tous les sommets restants de la forme \(A_n^j\), et l'on obtient un sous-graphe de \(G_{n-1}^{m+1}\). L'hypothèse de récurrence achève la preuve. \(\blacksquare\)
Remarque¶
En fait, le graphe \(G_n^m\) est le produit cartésien de \(G\) et du graphe de l'hypercube de dimension \(m\).