Shortlist 2015, C7¶
Domaine : Combinatoire · Difficulté : ★★★★★ · Proposé par : Russia
Concepts : Graphes : degrés, chemins, arbres · Coloriages et pavages · Principe extrémal · Récurrence et constructions récursives
Solution officielle : Shortlist officielle 2015 (avec solutions), p. 38 (page 39 du PDF)
Figures reprises du livret officiel de la Shortlist.
Pas encore relu
Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.
Énoncé¶
In a company of people some pairs are enemies. A group of people is called unsociable if the number of members in the group is odd and at least \(3\), and it is possible to arrange all its members around a round table so that every two neighbors are enemies. Given that there are at most \(2015\) unsociable groups, prove that it is possible to partition the company into \(11\) parts so that no two enemies are in the same part.
Indices : les idées clés
- Graphes : degrés, chemins, arbres et Coloriages et pavages : on traduit en graphe des inimitiés ; un groupe insociable est l'ensemble des sommets d'un cycle impair, et une partition en \(11\) parties est une coloration propre à \(11\) couleurs. On montre qu'un graphe de nombre chromatique \(k \geq 3\) contient au moins \(2^{k-1} - k\) cycles impairs d'ensembles de sommets distincts.
- Principe extrémal : on prend une coloration lexicographiquement minimale (solution 1), ou minimisant lexicographiquement le nombre de voisins de \(v\) dans chaque classe (solution 2) ; toute recoloration qui la « diminuerait » fournit un cycle impair.
- Recoloration par décalage ou par échange de chaînes : déplacer les sommets marqués vers la classe suivante (solution 1), ou échanger deux couleurs sur une composante connexe (solution 2, « chaînes de Kempe »).
- Récurrence et constructions récursives (solution 2) : récurrence sur \(k\) via un sous-graphe critique, en séparant les cycles qui passent par un sommet \(v\) de ceux qui l'évitent.
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2015 (deux solutions et deux remarques).
Solution 1¶
Soit \(G = (V, E)\) le graphe dont les sommets sont les personnes et les arêtes les paires d'ennemis. Partager la compagnie en \(11\) parties sans ennemis dans une même partie, c'est colorier proprement les sommets avec \(11\) couleurs. On démontre l'énoncé plus général suivant.
Affirmation. Si \(G\) a pour nombre chromatique \(k \geq 3\), alors \(G\) contient au moins \(2^{k-1} - k\) groupes insociables.
Rappelons que le nombre chromatique de \(G\) est le plus petit \(k\) tel qu'il existe une coloration propre
Comme \(2^{11} - 12 > 2015\) (et que \(2^{k-1} - k\) croît avec \(k\)), l'affirmation entraîne le résultat : le nombre chromatique est au plus \(11\).
Soit \(G\) de nombre chromatique \(k\). Une coloration propre (1) est dite leximinimale si le \(k\)-uplet \((|V_1|, |V_2|, \ldots, |V_k|)\) est lexicographiquement minimal : \(n_1 = |V_1|\) est minimal ; \(n_2 = |V_2|\) est minimal compte tenu de \(n_1\) ; … ; \(n_{k-1} = |V_{k-1}|\) est minimal compte tenu de \(n_1, \ldots, n_{k-2}\).
Lemme 1. Soit \(G\) un graphe de nombre chromatique \(k \geq 3\) impair, et (1) une coloration leximinimale. Alors \(G\) contient un cycle impair qui passe par toutes les classes \(V_1, \ldots, V_k\).
Preuve. Appelons multicolore un cycle qui passe par toutes les classes. Par définition du nombre chromatique, \(V_1\) est non vide ; soit \(v \in V_1\). On construit un cycle impair multicolore dont le seul sommet dans \(V_1\) est \(v\).
Plaçons \(v\) au centre et disposons \(V_2, V_3, \ldots, V_k\) en cercle autour de lui ; posons \(V_{k+1} = V_2\). On oriente certaines arêtes et on marque des sommets : on trace d'abord des flèches de \(v\) vers tous ses voisins dans \(V_2\), que l'on marque. Puis, tant que c'est possible, si un sommet \(u \in V_i\) (\(2 \leq i \leq k\)) est marqué, on trace des flèches de \(u\) vers tous ses voisins non encore marqués dans \(V_{i+1}\), et on les marque. À la fin, un sommet marqué de \(V_i\) n'a aucun voisin non marqué dans \(V_{i+1}\), et \(v\) est relié à chaque sommet marqué par un chemin orienté.
Déplaçons maintenant chaque sommet marqué dans la classe suivante (dans l'ordre circulaire \(V_2 \to V_3 \to \cdots \to V_k \to V_2\)). D'après ce qui précède, la coloration obtenue \(V_1 \sqcup W_2 \sqcup \cdots \sqcup W_k\) est propre. Le sommet \(v\) a un voisin \(w \in W_2\) : sinon
serait une coloration propre lexicographiquement plus petite que (1). Si \(w\) n'était pas marqué, il serait dans \(V_2\), donc aurait été marqué dès le début et déplacé dans \(W_3\) : contradiction. Donc \(w\) est marqué et \(w \in V_k\).
Comme \(w\) est marqué, il existe un chemin orienté de \(v\) à \(w\). Il parcourt les classes \(V_2, \ldots, V_k\) dans l'ordre circulaire et se termine dans \(V_k\), donc son nombre d'arêtes est un multiple de \(k - 1\), qui est pair. En le refermant par l'arête \(wv\), on obtient un cycle impair multicolore. \(\square\)
Preuve de l'affirmation. Choisissons une coloration leximinimale (1) de \(G\). Pour chaque ensemble \(C \subseteq \{1, 2, \ldots, k\}\) de cardinal impair \(> 1\), on va trouver un cycle impair passant exactement par les classes d'indices dans \(C\). Des \(C\) différents donnent ainsi des groupes insociables différents, et il y a \(2^{k-1} - k\) tels ensembles \(C\).
Soit \(V_C = \bigcup_{c \in C} V_c\) et \(G_C\) le sous-graphe induit sur \(V_C\), muni de la coloration induite à \(|C|\) couleurs, qui est propre. Elle est aussi leximinimale : une coloration \((W_c)_{c \in C}\) de \(G_C\) lexicographiquement plus petite, complétée par les classes \(V_i\) pour \(i \notin C\), donnerait une coloration propre de \(G\) plus petite que (1). Le lemme 1, appliqué à \(G_C\) et à la coloration \((V_c)_{c \in C}\), fournit un cycle impair passant exactement par les classes d'indices dans \(C\). \(\blacksquare\)
Solution 2¶
On donne une autre preuve de l'affirmation. Un graphe est critique si la suppression de n'importe quel sommet fait baisser son nombre chromatique. Tout graphe contient un sous-graphe induit critique de même nombre chromatique.
Lemme 2. Soit \(G = (V, E)\) un graphe critique de nombre chromatique \(k \geq 3\). Alors tout sommet \(v\) de \(G\) appartient à au moins \(2^{k-2} - 1\) groupes insociables.
Preuve. Pour \(X \subseteq V\), notons \(n(X)\) le nombre de voisins de \(v\) dans \(X\). Comme \(G\) est critique, \(G \setminus \{v\}\) admet une coloration propre à \(k - 1\) couleurs, d'où une coloration propre \(V = V_1 \sqcup V_2 \sqcup \cdots \sqcup V_k\) de \(G\) avec \(V_1 = \{v\}\). Parmi ces colorations, prenons-en une pour laquelle la suite \(n(V_2), n(V_3), \ldots, n(V_k)\) est lexicographiquement minimale (principe extrémal). On a \(n(V_i) > 0\) pour tout \(i \geq 2\) : sinon \(V_2 \sqcup \cdots \sqcup V_{i-1} \sqcup (V_i \cup V_1) \sqcup V_{i+1} \sqcup \cdots \sqcup V_k\) serait une coloration propre à \(k - 1\) couleurs.
Montrons que pour tout \(C \subseteq \{2, \ldots, k\}\) de cardinal pair \(\geq 2\), \(G\) contient un groupe insociable dont l'ensemble des couleurs est exactement \(C \cup \{1\}\) ; comme il y a \(2^{k-2} - 1\) tels \(C\), cela prouvera le lemme. Notons \(c_1 < \cdots < c_{2\ell}\) les éléments de \(C\), \(U_i = V_{c_i}\) et \(N_i\) l'ensemble des voisins de \(v\) dans \(U_i\).
Montrons que pour \(i = 1, \ldots, 2\ell - 1\) et \(x \in N_i\), le sous-graphe induit par \(U_i \cup U_{i+1}\) contient un chemin reliant \(x\) à un point de \(N_{i+1}\). Sinon, soit \(S\) la composante connexe de \(x\) dans ce sous-graphe, \(P = U_i \cap S\) et \(Q = U_{i+1} \cap S\). Comme \(x\) est séparé de \(N_{i+1}\), les ensembles \(Q\) et \(N_{i+1}\) sont disjoints. En remplaçant \(U_i\) et \(U_{i+1}\) par \((U_i \cup Q) \setminus P\) et \((U_{i+1} \cup P) \setminus Q\) (échange de couleurs sur la composante \(S\)), on obtient une coloration propre dans laquelle \(n(U_i) = n(V_{c_i})\) diminue (au moins \(x\) part) et seul \(n(U_{i+1}) = n(V_{c_{i+1}})\) augmente. Cela contredit la minimalité lexicographique de \((n(V_2), \ldots, n(V_k))\).
On construit alors un chemin à travers \(U_1, \ldots, U_{2\ell}\). On part d'un sommet quelconque \(v_1 \in N_1\). Pour \(i \leq 2\ell - 1\), si \(v_i \in N_i\) est défini, on le relie à un sommet de \(N_{i+1}\) dans le sous-graphe induit par \(U_i \cup U_{i+1}\), on ajoute ces arêtes au chemin, et on note \(v_{i+1} \in N_{i+1}\) la nouvelle extrémité. On obtient un chemin de \(v_1 \in N_1\) à \(v_{2\ell} \in N_{2\ell}\) dont chaque arête relie deux classes voisines : un sommet dans \(U_i\) est suivi d'un sommet dans \(U_{i+1}\) ou \(U_{i-1}\). Ce chemin n'est pas forcément simple ; on en extrait un sous-chemin minimal, qui est simple, relie les mêmes extrémités et conserve la propriété que chaque arête passe d'une classe à une classe voisine. Il passe donc par tous les \(U_1, \ldots, U_{2\ell}\), et sa longueur est impaire (on va de l'indice \(1\) à l'indice \(2\ell\) par pas de \(\pm 1\)). En le refermant par les arêtes \(vv_1\) et \(v_{2\ell}v\), on obtient le cycle impair voulu. \(\square\)
Preuve de l'affirmation par récurrence sur \(k \geq 3\). Pour \(k = 3\), il suffit d'appliquer le lemme 2 à un sous-graphe critique : on obtient \(2^{1} - 1 = 1 = 2^{2} - 3\) groupe. Pour l'hérédité, soit \(G_0\) un sous-graphe critique de \(G\) de nombre chromatique \(k\), et \(v\) un sommet de \(G_0\). Par le lemme 2, \(G_0\) a au moins \(2^{k-2} - 1\) groupes insociables contenant \(v\). D'autre part, \(G_0 \setminus \{v\}\) a pour nombre chromatique \(k - 1\), donc contient au moins \(2^{k-2} - (k-1)\) groupes insociables par hypothèse de récurrence (ils ne contiennent pas \(v\)). Au total, \(G_0\) (donc \(G\)) contient au moins \(2^{k-2} - 1 + 2^{k-2} - (k-1) = 2^{k-1} - k\) groupes insociables distincts. \(\blacksquare\)
Remarques¶
Remarque 1. L'affirmation est optimale : le graphe complet à \(k\) sommets a pour nombre chromatique \(k\) et contient exactement \(2^{k-1} - k\) groupes insociables.
Remarque 2. La preuve du lemme 2 fonctionne aussi pour \(|C|\) impair \(\geq 3\). La solution 2 montre donc que le nombre de groupes de taille paire disposables en cycle d'ennemis est au moins \(2^{k-1} - 1 - \binom{k}{2}\). Le livret écrit \(2^k - 1 - \binom{k}{2}\) ; il faut lire \(2^{k-1} - 1 - \binom{k}{2}\) (le nombre de parties de taille paire \(\geq 4\) de \(\{1, \ldots, k\}\), atteint par le graphe complet).