Aller au contenu

Shortlist 2021, C6

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

Concepts : Coloriages et pavages · Jeux et stratégies gagnantes

Solution officielle : Shortlist officielle 2021 (avec solutions), p. 34 (page 34 du PDF)

Pas encore relu

Les concepts et la rédaction de cette page n'ont pas encore été vérifiés.

Énoncé

A hunter and an invisible rabbit play a game on an infinite square grid. First the hunter fixes a colouring of the cells with finitely many colours. The rabbit then secretly chooses a cell to start in. Every minute, the rabbit reports the colour of its current cell to the hunter, and then secretly moves to an adjacent cell that it has not visited before (two cells are adjacent if they share a side). The hunter wins if after some finite time either

  • the rabbit cannot move; or
  • the hunter can determine the cell in which the rabbit started.

Decide whether there exists a winning strategy for the hunter.

Indices : les idées clés
  • Coloriage produit : on superpose plusieurs coloriages en un seul, dont les couleurs sont des \(k\)-uplets ; toute information lisible sur l'un est lisible sur le produit.
  • Coloriages et pavages : des coloriages modulo \(3\) : les restes de \(x\) et \(y\) modulo \(3\) révèlent la direction de chaque pas du lapin.
  • Colonnes noires à écarts deux à deux distincts : dès que la coordonnée correspondante est non bornée, l'écart observé identifie exactement la colonne (ou la diagonale).
  • Jeux et stratégies gagnantes : deux des trois quantités \(x\), \(y\), \(x+y\) sont non bornées, ce qui suffit au chasseur pour tout reconstituer.
Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2021 (une solution et une remarque).

Réponse : oui, il existe un coloriage qui donne au chasseur une stratégie gagnante.

Solution

Coloriage produit. Une idée centrale est que plusieurs coloriages \(C_1, C_2, \ldots, C_k\) peuvent être fusionnés en un seul coloriage produit \(C_1 \times C_2 \times \cdots \times C_k\) : les couleurs du produit sont les \(k\)-uplets \((c_1, \ldots, c_k)\), où \(c_i\) est une couleur de \(C_i\), et chaque case reçoit le \(k\)-uplet de ses couleurs dans les différents \(C_i\). Ainsi, toute information que l'on peut déduire d'un des coloriages \(C_i\) peut aussi être déduite du coloriage produit. (Le livret écrit \((c_1, \ldots, c_n)\) ; il faut lire \((c_1, \ldots, c_k)\).)

Le chasseur fusionne les coloriages suivants (on repère les cases par leurs coordonnées entières \((x, y)\)).

  • \(C_1\) et \(C_2\) : suivre les déplacements. \(C_1\) colorie chaque case selon le reste de \(x\) modulo \(3\) ; comme un pas change \(x\) de \(-1\), \(0\) ou \(+1\), cela permet de savoir si le lapin va à gauche, à droite ou se déplace verticalement. De même, \(C_2\) utilise le reste de \(y\) modulo \(3\) et indique si le lapin monte, descend ou se déplace horizontalement. Le chasseur connaît donc toute la suite des pas du lapin, mais pas sa position.
  • \(C_3\) : trouver \(x\) si \(x\) est non borné. Dans \(C_3\), les colonnes sont coloriées en blanc et noir de sorte que les écarts entre colonnes noires voisines soient deux à deux distincts. Si l'abscisse du lapin est non bornée, il finira par visiter deux cases noires de colonnes différentes. Grâce à \(C_1\), le chasseur repère ce moment et connaît la différence des abscisses de ces deux cases noires, d'où il déduit la colonne exacte. (Précision ajoutée : comme \(x\) varie d'au plus \(1\) à chaque pas, entre une visite d'une colonne noire et la première visite d'une autre colonne noire, il y a un moment où le lapin passe d'une colonne noire à une colonne noire voisine ; leur écart, connu du chasseur, identifie ces deux colonnes.) Symétriquement, si l'ordonnée du lapin est non bornée, un coloriage \(C_4\) (lignes noires et blanches) permet de déterminer la valeur exacte de \(y\).
  • \(C_5\) : trouver \(x + y\) si \(x + y\) est non borné. Les diagonales \(x + y = \text{constante}\) sont coloriées en noir et blanc de sorte que les écarts entre diagonales noires voisines soient deux à deux distincts ; le même raisonnement donne la valeur exacte de \(x + y\).

Conclusion. Si le lapin n'est jamais bloqué, il visite une infinité de cases distinctes, donc au moins deux des trois valeurs \(x\), \(y\) et \(x + y\) sont non bornées. (Précision ajoutée : si \(x\) et \(y\) étaient bornées, le lapin resterait dans un ensemble fini de cases ; et si par exemple seule \(x\) était non bornée, \(x = (x+y) - y\) serait bornée.) Le chasseur finit donc par connaître deux de ces trois valeurs à un certain instant, donc les trois. Il remonte alors le temps à l'aide de \(C_1\) et \(C_2\), qui lui donnent tous les pas effectués, et calcule la case de départ du lapin. C'est une stratégie gagnante. \(\blacksquare\)

Remarques

Remarque. Il existe des variantes de cette solution : par exemple, on peut remplacer les coloriages \(C_3\), \(C_4\) et \(C_5\) par d'autres. Ces variantes sont cependant plus techniques et le livret ne les présente pas.