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é

Une ville compte \(n \geq 3\) îles. Au départ, la compagnie de ferries propose des liaisons entre certaines paires d'îles, de sorte qu'il soit impossible de répartir les îles en deux groupes sans qu'aucune liaison ne relie deux îles de groupes différents.

Chaque année, la compagnie ferme une liaison entre deux îles \(X\) et \(Y\). En même temps, pour maintenir son service, elle ouvre de nouvelles liaisons selon la règle suivante : pour toute île reliée par une liaison à exactement une des îles \(X\) et \(Y\), une nouvelle liaison est créée entre cette île et l'autre des îles \(X\) et \(Y\).

On suppose qu'à tout moment, si l'on partage les îles en deux groupes non vides de façon quelconque, on sait que la compagnie fermera, au bout d'un certain nombre d'années, une liaison reliant deux îles des deux groupes. Montrer qu'au bout d'un certain nombre d'années, il y aura une île reliée par une liaison à toutes les autres îles.

Énoncé original (anglais)

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\)

Problèmes voisins

Sur les mêmes idées, à une difficulté proche :

  • 2023 C4 ★★★☆☆ : Découper une bande \(1 \times n^2\) et translater les morceaux pour former un carré avec une condition sur les numéros : combien de morceaux ?
  • 2019 C5 ★★★☆☆ · OIM P3 : Un réseau social où une amitié en angle se transforme : on peut toujours aboutir à des amitiés au plus en couple.
  • 2025 C6 ★★★★☆ : À partir d'un chemin hamiltonien d'un échidné, numéroter les cases pour que, entre voisines, le plus grand nombre soit visité en premier en ligne et en second en colonne.
  • 2007 C6 ★★★★☆ · OIM P3 : Si la plus grande clique est de taille paire, on peut répartir les candidats en deux salles où les plus grandes cliques ont la même taille.