Shortlist 2019, C4

Domaine : Combinatoire · Difficulté : ★★☆☆☆ · Proposé par : Canada

Concepts : Géométrie combinatoire : enveloppe convexe, points du réseau · Graphes : degrés, chemins, arbres · Invariants et monovariants · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2019 (avec solutions), section C4 (livret PDF)

Figures reprises du livret officiel de la Shortlist.

Énoncé

On a flat plane in Camelot, King Arthur builds a labyrinth \(\mathfrak{L}\) consisting of \(n\) walls, each of which is an infinite straight line. No two walls are parallel, and no three walls have a common point. Merlin then paints one side of each wall entirely red and the other side entirely blue.

At the intersection of two walls there are four corners: two diagonally opposite corners where a red side and a blue side meet, one corner where two red sides meet, and one corner where two blue sides meet. At each such intersection, there is a two-way door connecting the two diagonally opposite corners at which sides of different colours meet.

After Merlin paints the walls, Morgana then places some knights in the labyrinth. The knights can walk through doors, but cannot walk through walls.

Let \(k(\mathfrak{L})\) be the largest number \(k\) such that, no matter how Merlin paints the labyrinth \(\mathfrak{L}\), Morgana can always place at least \(k\) knights such that no two of them can ever meet. For each \(n\), what are all possible values for \(k(\mathfrak{L})\), where \(\mathfrak{L}\) is a labyrinth with \(n\) walls?

Indices : les idées clés

• Géométrie combinatoire : \(n\) droites en position générale découpent le plan en \(\binom{n+1}{2} + 1\) régions, avec \(\binom n2\) points d'intersection.
• Graphes : régions = sommets, portes = arêtes ; chaque arête diminue le nombre de composantes connexes d'au plus \(1\), d'où au moins \(n + 1\) composantes.
• Coloriage « ouest rouge, est bleu » (solution 1) : en marchant vers le nord par les portes, on garde le nombre de murs à l'ouest desquels on se trouve.
• Invariant (solution 2) : on part d'un labyrinthe construit par récurrence puis on déplace les murs ; passer un mur par l'intersection de deux autres conserve le nombre de composantes.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2019 (deux solutions et deux remarques).

Réponse : la seule valeur possible est \(k(\mathfrak L) = n + 1\), quelle que soit la forme du labyrinthe.

Solution 1

Montrons d'abord par récurrence que les \(n\) murs découpent le plan en \(\binom{n+1}{2} + 1\) régions. C'est vrai pour \(n = 0\) (une seule région). Quand on place le \(n\)-ième mur, il coupe chacun des \(n - 1\) autres murs exactement une fois, donc il est découpé en \(n\) morceaux et partage en deux exactement \(n\) des régions formées par les autres murs. Par hypothèse de récurrence, on obtient \(\left(\binom n2 + 1\right) + n = \binom{n+1}{2} + 1\) régions.

Soit \(G\) le graphe dont les sommets sont les \(\binom{n+1}{2} + 1\) régions, deux régions étant reliées par une arête s'il y a une porte entre elles.

Morgana peut toujours placer au moins \(n + 1\) chevaliers. Quel que soit le coloriage, il y a exactement \(\binom n2\) points d'intersection, chacun correspondant à une seule arête de \(G\). Ajoutons les arêtes de \(G\) une par une : chaque arête diminue le nombre de composantes connexes d'au plus \(1\). Le nombre de composantes connexes de \(G\) est donc au moins

\[\binom{n+1}{2} + 1 - \binom n2 = n + 1.\]

Si Morgana place les chevaliers dans des régions de composantes connexes différentes, deux chevaliers ne peuvent jamais se rencontrer.

Merlin peut toujours empêcher plus de \(n + 1\) chevaliers. Montrons que, quelle que soit la forme du labyrinthe, Merlin peut le colorier de sorte qu'il y ait exactement \(n + 1\) composantes connexes.

On choisit un repère dans lequel aucun mur n'est orienté exactement nord-sud ou est-ouest. Merlin peint en rouge la face ouest de chaque mur et en bleu sa face est. On étiquette chaque région par le nombre de murs à l'est desquels elle se trouve : les étiquettes sont des entiers entre \(0\) et \(n\).

Affirmation : pour chaque \(i\), les régions d'étiquette \(i\) sont reliées entre elles par des portes. D'abord, pour chaque \(i\) avec \(0 \leq i \leq n\), il y a une unique région d'étiquette \(i\) non bornée vers le nord. Ensuite, plaçons un chevalier dans une région d'étiquette \(i\) et demandons-lui de marcher vers le nord (en se déplaçant vers l'est ou l'ouest le long des murs qui bordent la région au nord, si besoin). Il ne reste jamais bloqué : chaque région est convexe, donc si elle est bornée au nord, elle a un unique sommet le plus au nord, où une porte mène vers le nord à une autre région d'étiquette \(i\). Précision ajoutée : en ce sommet, les deux murs descendent l'un vers le sud-ouest, l'autre vers le sud-est ; le coin sud est donc à l'est de l'un et à l'ouest de l'autre (coin rouge-bleu), et la porte mène au coin nord, qui est lui aussi à l'est d'exactement un des deux murs : l'étiquette ne change pas. Le chevalier finit par atteindre une région non bornée vers le nord, qui est l'unique région de ce type d'étiquette \(i\). Toutes les régions d'étiquette \(i\) sont donc reliées à celle-ci, donc entre elles.

Il y a ainsi exactement \(n + 1\) composantes connexes, et Morgana peut placer au plus \(n + 1\) chevaliers. \(\blacksquare\)

Solution 2

Voici une autre stratégie de coloriage pour Merlin, qui empêche Morgana de placer plus de \(n + 1\) chevaliers (la minoration est la même que dans la solution 1).

Merlin commence par construire un labyrinthe de \(n\) murs de son choix. Il place les murs l'un après l'autre avec des pentes positives croissantes, chacun suffisamment à droite pour que tous les points d'intersection des droites déjà placées soient à sa gauche. Il peint chaque mur en bleu à gauche et en rouge à droite. (Voir la figure pour un exemple avec quatre droites \(\ell_1, \ldots, \ell_4\).)

Une région est dite « à droite » si son abscisse n'est pas majorée (avec un seul mur, les deux régions sont à droite). Montrons par récurrence qu'après avoir placé \(n\) droites, il y a \(n + 1\) composantes connexes, chacune contenant exactement une région à droite. C'est vrai après \(0\) droite (une seule région, à droite).

Quand on place la \(n\)-ième droite, elle coupe chacune des \(n - 1\) droites précédentes, et comme elle est à droite de tous les points d'intersection, les régions qu'elle coupe sont exactement les \(n\) régions à droite. L'ajout de cette droite laisse à chaque composante connexe précédente exactement une région à droite, et crée une nouvelle composante formée d'une seule région, elle aussi à droite. Par récurrence, ce labyrinthe a donc \(n + 1\) composantes connexes.

Ensuite, Merlin déplace les murs un par un (par des translations et rotations continues) jusqu'à la position du labyrinthe d'Arthur, en faisant en sorte que deux droites ne deviennent jamais parallèles (la couleur de chaque face suit le mur dans son mouvement). La configuration ne change que lorsqu'un mur passe par le point d'intersection de deux autres. Tous les mouvements font bien passer d'une configuration de ce type à l'autre : tous les triplets de droites ont initialement ce type de coloriage, et les règles sur les rotations le préservent (en particulier, on ne peut pas créer un triangle dont les trois côtés sont rouges vers l'intérieur, ou bleus vers l'intérieur).

Or, comme on le voit sur la figure, un tel mouvement conserve le nombre de composantes connexes. Avec le coloriage ainsi obtenu sur le labyrinthe réel d'Arthur, Morgana peut donc placer au plus \(n + 1\) chevaliers. \(\blacksquare\)

Remarques

Remarque 1 (sur la solution 1). Il existe des variantes de cet argument, qui donnent plus ou moins d'information sur les composantes connexes avec cette numérotation. Par exemple, on peut montrer que les régions non bornées sont numérotées \(0, 1, \ldots, n-1, n, n-1, \ldots, 1\) quand on en fait le tour, que les régions d'étiquettes \(0\) et \(n\) sont seules dans leur composante, et que chaque autre composante forme une chaîne reliant les deux régions non bornées de même étiquette. On peut aussi montrer que les composantes sont acycliques sans trop en révéler sur leur structure.

Remarque 2 (sur la solution 2). Bien que superficiellement différentes, les deux constructions donnent en fait le même coloriage pour un labyrinthe donné. Avec les méthodes de la solution 2, on peut montrer que ce sont les seuls coloriages donnant exactement \(n + 1\) composantes connexes.