Aller au contenu

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é

Sur une plaine de Camelot, le roi Arthur construit un labyrinthe \(\mathfrak{L}\) formé de \(n\) murs, chacun étant une droite infinie. Deux murs ne sont jamais parallèles, et trois murs n'ont jamais de point commun. Merlin peint ensuite entièrement un côté de chaque mur en rouge et l'autre côté en bleu.

À l'intersection de deux murs, il y a quatre coins : deux coins diagonalement opposés où se rencontrent un côté rouge et un côté bleu, un coin où se rencontrent deux côtés rouges, et un coin où se rencontrent deux côtés bleus. À chacune de ces intersections, une porte, franchissable dans les deux sens, relie les deux coins diagonalement opposés où se rencontrent des côtés de couleurs différentes.

Une fois les murs peints par Merlin, Morgane place des chevaliers dans le labyrinthe. Les chevaliers peuvent franchir les portes, mais pas traverser les murs.

Soit \(k(\mathfrak{L})\) le plus grand nombre \(k\) tel que, quelle que soit la façon dont Merlin peint le labyrinthe \(\mathfrak{L}\), Morgane puisse toujours placer au moins \(k\) chevaliers dont deux ne pourront jamais se rencontrer. Pour chaque \(n\), quelles sont toutes les valeurs possibles de \(k(\mathfrak{L})\), où \(\mathfrak{L}\) est un labyrinthe à \(n\) murs ?

Énoncé original (anglais)

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

Figure (solution 2)

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.

Figure (solution 2)

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

Figure (solution 2)

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.

Problèmes voisins

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

  • 2015 C2 ★☆☆☆☆ · OIM P1 : Des ensembles de points où toute paire a un point équidistant, mais où aucun point n'est centre de trois autres.
  • 2006 C2 ★★☆☆☆ · OIM P2 : Une triangulation d'un \(2006\)-gone régulier : combien de triangles isocèles à deux côtés impairs au maximum ?
  • 2019 C6 ★★★☆☆ : Ordonner \(2n\) points pour que les angles du polygone obtenu se répartissent en deux groupes de même somme.
  • 2016 C5 ★★★☆☆ : Combien de diagonales d'un \(n\)-gone régulier peut-on choisir pour que deux qui se coupent soient perpendiculaires ?