Aller au contenu

Shortlist 2016, C6

Domaine : Combinatoire · Difficulté : ★★★★☆ · Proposé par : non indiqué

Concepts : Graphes : degrés, chemins, arbres · Invariants et monovariants

Solution officielle : Shortlist officielle 2016 (avec solutions), p. 39 (page 42 du PDF)

Énoncé

There are \(n \geq 3\) islands in a city. Initially, the ferry company offers some routes between some pairs of islands so that it is impossible to divide the islands into two groups such that no two islands in different groups are connected by a ferry route.

After each year, the ferry company will close a ferry route between some two islands \(X\) and \(Y\). At the same time, in order to maintain its service, the company will open new routes according to the following rule: for any island which is connected by a ferry route to exactly one of \(X\) and \(Y\), a new route between this island and the other of \(X\) and \(Y\) is added.

Suppose at any moment, if we partition all islands into two nonempty groups in any way, then it is known that the ferry company will close a certain route connecting two islands from the two groups after some years. Prove that after some years there will be an island which is connected to all other islands by ferry routes.

Indices : les idées clés
  • Graphes : degrés, chemins, arbres : îles = sommets, liaisons = arêtes ; l'hypothèse initiale dit que le graphe est connexe, et l'on cherche un sommet relié à tous les autres.
  • Invariants et monovariants : on maintient une partition de l'ensemble \(\mathcal{A} \cup \mathcal{B}\) en deux parties formant un « réseau » (biparti complet) ; quand une liaison du réseau est fermée, on reforme un réseau sur les mêmes îles.
  • Faire grandir l'ensemble une île à la fois : la taille de \(\mathcal{A} \cup \mathcal{B}\) ne diminue jamais et augmente dès qu'une liaison vers l'extérieur est fermée.
Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2016 (une solution).

Solution

On modélise la situation par un graphe : les îles sont les sommets et les liaisons les arêtes. On dit que deux ensembles d'îles forment un réseau si chaque île de l'un est reliée à chaque île de l'autre.

Départ. Choisissons deux îles \(A\) et \(B\) reliées par une liaison, et mettons \(A\) dans l'ensemble \(\mathcal{A}\) et \(B\) dans l'ensemble \(\mathcal{B}\). D'après la condition initiale (le réseau de liaisons est connexe et \(n \geq 3\)), une autre île est reliée à \(A\) ou à \(B\) ; sans perte de généralité, une île \(C\) est reliée à \(A\). On met \(C\) dans \(\mathcal{B}\). Alors \(\mathcal{A} = \{A\}\) et \(\mathcal{B} = \{B, C\}\) forment un réseau.

On va inclure toutes les îles dans \(\mathcal{A} \cup \mathcal{B}\), une par une.

Le réseau se maintient (invariant). Supposons que \(\mathcal{A}\) et \(\mathcal{B}\) forment un réseau, avec \(3 \leq |\mathcal{A} \cup \mathcal{B}| < n\). Cette propriété ne peut cesser d'être vraie que si une liaison entre une île \(A \in \mathcal{A}\) et une île \(B \in \mathcal{B}\) est fermée. Dans ce cas, posons \(\mathcal{A}' = \{A, B\}\) et \(\mathcal{B}' = (\mathcal{A} \cup \mathcal{B}) \setminus \{A, B\}\) ; notons que \(\mathcal{B}'\) est non vide. Soit \(C \in \mathcal{A} \setminus \{A\}\). Comme \(\mathcal{A}\) et \(\mathcal{B}\) forment un réseau, \(C\) est relié à \(B\). Si \(C\) n'était pas relié à \(A\) avant la fermeture de la liaison \(AB\), une liaison entre \(C\) et \(A\) est ajoutée ensuite. Donc \(C\) est maintenant relié à la fois à \(A\) et à \(B\). Il en va de même pour toute île de \(\mathcal{B} \setminus \{B\}\). Ainsi \(\mathcal{A}'\) et \(\mathcal{B}'\) forment un réseau, et \(\mathcal{A}' \cup \mathcal{B}' = \mathcal{A} \cup \mathcal{B}\). Les îles de \(\mathcal{A} \cup \mathcal{B}\) peuvent donc toujours être partagées en deux ensembles formant un réseau.

L'ensemble grandit. Comme \(|\mathcal{A} \cup \mathcal{B}| < n\), certaines îles ne sont pas dans \(\mathcal{A} \cup \mathcal{B}\). D'après l'hypothèse (appliquée à la partition entre \(\mathcal{A} \cup \mathcal{B}\) et son complémentaire), au bout de quelques années une liaison entre une île \(A \in \mathcal{A} \cup \mathcal{B}\) et une île \(D\) extérieure sera fermée. Sans perte de généralité, \(A \in \mathcal{A}\). Chaque île de \(\mathcal{B}\) est reliée à \(A\) ; qu'elle ait été reliée à \(D\) ou non auparavant, elle est donc ensuite reliée à \(D\). On peut alors mettre \(D\) dans \(\mathcal{A}\) : les nouveaux ensembles \(\mathcal{A}\) et \(\mathcal{B}\) forment encore un réseau, et \(|\mathcal{A} \cup \mathcal{B}|\) a augmenté de \(1\). En répétant ce procédé, toutes les îles finissent par être incluses ; on peut donc supposer \(|\mathcal{A} \cup \mathcal{B}| = n\).

Conclusion. Supposons qu'au bout de quelques années une liaison entre \(A \in \mathcal{A}\) et \(B \in \mathcal{B}\) soit fermée (cela arrivera, d'après l'hypothèse appliquée à la partition \(\{\mathcal{A}, \mathcal{B}\}\)). On met \(A\) et \(B\) dans \(\mathcal{A}'\) et toutes les autres îles dans \(\mathcal{B}'\) ; comme ci-dessus, \(\mathcal{A}'\) et \(\mathcal{B}'\) forment un réseau. Cette propriété ne cesse d'être vraie que lorsqu'une liaison entre, sans perte de généralité, \(A\) et une île \(C \in \mathcal{B}'\) est fermée, et cela finit par arriver d'après l'hypothèse. À ce moment, l'île \(B\) est reliée à toutes les autres îles : elle est reliée à toutes les îles de \(\mathcal{B}'\), et si elle n'était pas reliée à \(A\), elle est reliée à \(C\) mais pas à \(A\), donc une liaison \(BA\) est ajoutée. D'où le résultat. \(\blacksquare\)