Shortlist 2021, C4¶
Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : non indiqué
Concepts : Graphes : degrés, chemins, arbres
Solution officielle : Shortlist officielle 2021 (avec solutions), p. 30 (page 30 du PDF)
Énoncé¶
The kingdom of Anisotropy consists of \(n\) cities. For every two cities there exists exactly one direct one-way road between them. We say that a path from \(X\) to \(Y\) is a sequence of roads such that one can move from \(X\) to \(Y\) along this sequence without returning to an already visited city. A collection of paths is called diverse if no road belongs to two or more paths in the collection.
Let \(A\) and \(B\) be two distinct cities in Anisotropy. Let \(N_{AB}\) denote the maximal number of paths in a diverse collection of paths from \(A\) to \(B\). Similarly, let \(N_{BA}\) denote the maximal number of paths in a diverse collection of paths from \(B\) to \(A\). Prove that the equality \(N_{AB} = N_{BA}\) holds if and only if the number of roads going out from \(A\) is the same as the number of roads going out from \(B\).
Indices : les idées clés
- Graphes : on modélise le royaume par un tournoi ; \(N_{AB}\) est le nombre maximal de chemins de \(A\) à \(B\) deux à deux sans arc commun, et on prouve en fait \(N_{BA} - N_{AB} = b - a\) (degrés sortants \(a\), \(b\)).
- Chemins courts et recombinaison (solution 1) : on peut supposer qu'une collection optimale contient tous les chemins de longueur \(1\) ou \(2\) ; les autres chemins se retournent en chemins de \(B\) vers \(A\).
- Partition des villes en quatre groupes (solution 1) selon le sens des routes vers \(A\) et \(B\), ce qui exprime \(a - b\).
- Théorème de Menger (solution 2) : nombre maximal de chemins disjoints en arcs \(=\) taille minimale d'une coupe ; on transforme une coupe pour \((A, B)\) en coupe pour \((B, A)\) en échangeant \(A\) et \(B\).
Solutions
Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2021 (deux solutions).
Dans les deux solutions, on note \(a\) et \(b\) les nombres de routes sortant de \(A\) et de \(B\) ; on montre que \(N_{BA} - N_{AB} = b - a\), ce qui donne l'équivalence demandée.
Solution 1¶
On écrit \(X \to Y\) (ou \(Y \leftarrow X\)) si la route entre \(X\) et \(Y\) va de \(X\) vers \(Y\). Remarquons que s'il existe un itinéraire de \(X\) à \(Y\) (passant éventuellement plusieurs fois par une même ville), il existe un chemin de \(X\) à \(Y\) formé de certaines routes de cet itinéraire : on peut supprimer sans dommage tout cycle de l'itinéraire, et après quelques suppressions on obtient un chemin.
Un chemin est court s'il comporte une ou deux routes. On répartit les villes autres que \(A\) et \(B\) en quatre groupes \(\mathcal{I}\), \(\mathcal{O}\), \(\mathcal{A}\), \(\mathcal{B}\) : pour toute ville \(C\),
Lemme. Soit \(\mathcal{P}\) une collection variée de \(p\) chemins de \(A\) à \(B\). Il existe une collection variée d'au moins \(p\) chemins de \(A\) à \(B\) contenant tous les chemins courts de \(A\) à \(B\).
Preuve. On modifie \(\mathcal{P}\) comme suit. S'il existe une route directe \(A \to B\) et que le chemin formé de cette seule route n'est pas dans \(\mathcal{P}\), on l'ajoute simplement.
Considérons ensuite une ville \(C \in \mathcal{A}\) telle que le chemin \(A \to C \to B\) ne soit pas dans \(\mathcal{P}\). Si \(\mathcal{P}\) contient au plus un chemin utilisant la route \(A \to C\) ou la route \(C \to B\), on retire ce chemin (s'il existe) et on ajoute \(A \to C \to B\). Sinon, \(\mathcal{P}\) contient deux chemins de la forme \(A \to C \dashrightarrow B\) et \(A \dashrightarrow C \to B\), où \(C \dashrightarrow B\) et \(A \dashrightarrow C\) sont des chemins. On recombine alors les routes en deux nouveaux chemins \(A \to C \to B\) et \(A \dashrightarrow C \dashrightarrow B\) (en supprimant les cycles de ce dernier si nécessaire), qui remplacent les deux anciens.
Après chacune de ces opérations, le nombre de chemins ne diminue pas et la collection reste variée. En traitant ainsi chaque \(C \in \mathcal{A}\), on obtient la collection voulue. \(\square\)
Retour au problème. Quitte à échanger \(A\) et \(B\), supposons qu'il existe une route \(A \to B\). Choisissons une collection variée \(\mathcal{P}\) de \(N_{AB}\) chemins de \(A\) à \(B\). Nous allons la transformer en une collection variée \(\mathcal{Q}\) d'au moins \(N_{AB} + (b - a)\) chemins de \(B\) à \(A\). Cela donnera
d'où \(N_{BA} - N_{AB} = b - a\), ce qui donne l'équivalence voulue.
D'après le lemme, il existe une collection variée \(\mathcal{P}'\) d'au moins \(N_{AB}\) chemins contenant les \(|\mathcal{A}| + 1\) chemins courts de \(A\) à \(B\). Les chemins de \(\mathcal{P}'\) ne contiennent aucune route d'un chemin court de \(B\) à \(A\) (un chemin partant de \(A\) n'emprunte aucune route arrivant en \(A\), et un chemin arrivant en \(B\) n'emprunte aucune route partant de \(B\)). Chaque chemin non court de \(\mathcal{P}'\) est de la forme \(A \to C \dashrightarrow D \to B\), où \(C \dashrightarrow D\) est un chemin d'une ville \(C \in \mathcal{I}\) vers une ville \(D \in \mathcal{O}\). (Précision ajoutée : la route \(A \to C\) n'est pas celle d'un chemin court, donc \(C \notin \mathcal{A}\), et \(A \to C\) impose \(C \in \mathcal{I}\) ; de même \(D \in \mathcal{O}\).) Pour chacun de ces chemins, on met dans \(\mathcal{Q}\) le chemin \(B \to C \dashrightarrow D \to A\) ; on y met aussi tous les chemins courts de \(B\) à \(A\). Clairement, la collection \(\mathcal{Q}\) est variée.
Maintenant, toutes les routes sortant de \(A\) aboutissent dans \(\mathcal{I} \cup \mathcal{A} \cup \{B\}\), et toutes celles sortant de \(B\) aboutissent dans \(\mathcal{I} \cup \mathcal{B}\). Donc
D'autre part, il y a \(|\mathcal{A}| + 1\) chemins courts de \(A\) à \(B\) (y compris \(A \to B\)) et \(|\mathcal{B}|\) chemins courts de \(B\) à \(A\), d'où
comme voulu. \(\blacksquare\)
Solution 2¶
Rappelons quelques notions de théorie des graphes. Soit \(G\) un graphe orienté fini d'ensemble de sommets \(V\), et soient \(s \neq t\) deux sommets. Une \((s, t)\)-coupe est une partition \(V = S \sqcup T\) avec \(s \in S\) et \(t \in T\). Les arcs de coupe de \((S, T)\) sont les arcs allant de \(S\) vers \(T\), et la taille \(e(S, T)\) de la coupe est leur nombre. On utilise le théorème suivant (cas particulier du théorème « flot maximal – coupe minimale » de Ford–Fulkerson).
Théorème de Menger. Dans un graphe orienté \(G\), le nombre maximal de chemins de \(s\) à \(t\) deux à deux sans arc commun est égal à la taille minimale d'une \((s, t)\)-coupe.
Considérons le graphe orienté \(G\) dont les sommets sont les villes et les arcs les routes. Alors \(N_{AB}\) est le nombre maximal de chemins de \(A\) à \(B\) sans arc commun, et de même pour \(N_{BA}\).
Nous montrons que pour toute \((A, B)\)-coupe \((S_A, T_A)\), il existe une \((B, A)\)-coupe \((S_B, T_B)\) telle que
Par le théorème de Menger, cela donne \(N_{BA} \leq N_{AB} + (b - a)\) ; de même \(N_{AB} \leq N_{BA} + (a - b)\), d'où à nouveau \(N_{BA} - N_{AB} = b - a\).
La construction est simple : \(S_B = (S_A \cup \{B\}) \setminus \{A\}\), et donc \(T_B = (T_A \cup \{A\}) \setminus \{B\}\).
Notons \(\mathcal{E}_A\) et \(\mathcal{E}_B\) les ensembles d'arcs de coupe de \((S_A, T_A)\) et \((S_B, T_B)\). Soient \(a_s\) et \(a_t = a - a_s\) les nombres d'arcs allant de \(A\) vers \(S_A\) et vers \(T_A\) ; de même, \(b_s\) et \(b_t = b - b_s\) les nombres d'arcs allant de \(B\) vers \(S_B\) et vers \(T_B\).
Tout arc ne touchant ni \(A\) ni \(B\) appartient soit aux deux ensembles \(\mathcal{E}_A\), \(\mathcal{E}_B\), soit à aucun ; notons \(c\) le nombre de tels arcs dans \(\mathcal{E}_A\). Les autres arcs de \(\mathcal{E}_A\) sont de deux sortes : ceux qui partent de \(A\) vers \(T_A\) (y compris \(A \to B\) s'il existe), au nombre de \(a_t\), et ceux qui vont de \(S_A \setminus \{A\}\) vers \(B\), c'est-à-dire de \(S_B \setminus \{B\}\) vers \(B\), au nombre de \(|S_B| - 1 - b_s\) (entre deux villes il y a toujours exactement une route). Donc
Comme \(|S_A| = |S_B|\), on obtient
ce qui achève la solution. \(\blacksquare\)