Shortlist 2009, C6

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

Concepts : Coloriages et pavages · Récurrence et constructions récursives

Solution officielle : Shortlist officielle 2009 (avec solutions), p. 36 (page 38 du PDF)

Figures reprises du livret officiel de la Shortlist.

Énoncé

On a \(999 \times 999\) board a limp rook can move in the following way: From any square it can move to any of its adjacent squares, i.e. a square having a common side with it, and every move must be a turn, i.e. the directions of any two consecutive moves must be perpendicular. A non-intersecting route of the limp rook consists of a sequence of pairwise different squares that the limp rook can visit in that order by an admissible sequence of moves. Such a non-intersecting route is called cyclic, if the limp rook can, after reaching the last square of the route, move directly to the first square of the route and start over.

How many squares does the longest possible cyclic, non-intersecting route of a limp rook visit?

Indices : les idées clés

• Coloriage à quatre couleurs selon les parités de \((i, j)\) : la tour visite les couleurs dans l'ordre \(A, B, D, C\) ou \(A, C, D, B\), donc chaque couleur autant de fois ; il n'y a que \(499^2\) cases \(A\).
• Toutes les cases \(A\) impossibles : en coloriant les cases \(A\) en damier, un nombre impair empêche l'alternance, d'où deux cases \(A\) consécutives en diagonale et un croisement forcé.
• Construction récursive pour \(n \equiv 3 \pmod 4\) qui manque exactement une case \(A\).

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2009 (une solution).

Réponse : \(998^2 - 4 = 4 \cdot (499^2 - 1)\) cases.

Solution

Montrons d'abord que ce nombre majore le nombre de cases qu'une tour boiteuse peut visiter. Pour cela, colorions les cases avec quatre couleurs \(A\), \(B\), \(C\) et \(D\) ainsi : pour \((i, j) \equiv (0, 0) \pmod 2\), on utilise \(A\) ; pour \((i, j) \equiv (0, 1) \pmod 2\), \(B\) ; pour \((i, j) \equiv (1, 0) \pmod 2\), \(C\) ; et pour \((i, j) \equiv (1, 1) \pmod 2\), \(D\). Depuis une case \(A\), la tour doit aller sur une case \(B\) ou une case \(C\). Dans le premier cas, l'ordre des couleurs des cases visitées est \(A, B, D, C, A, B, D, C, A, \ldots\) ; dans le second, il est \(A, C, D, B, A, C, D, B, A, \ldots\). Comme la route est fermée, elle doit contenir le même nombre de cases de chaque couleur. Il n'y a que \(499^2\) cases \(A\). Nous allons montrer que la tour ne peut pas visiter toutes les cases \(A\) de sa route, de sorte que le nombre maximal possible de cases d'une route est \(4 \cdot (499^2 - 1)\).

Supposons que la route passe par chaque case \(A\). Colorions les cases \(A\) en noir et blanc comme un échiquier, c'est-à-dire que deux cases \(A\) à distance \(2\) sont de couleurs différentes. Comme le nombre de cases \(A\) est impair, la tour ne peut pas toujours alterner entre cases \(A\) noires et blanches le long de sa route. Il y a donc deux cases \(A\) de même couleur, à quatre pas de tour l'une de l'autre, visitées l'une juste après l'autre. Soient \((a, b)\) et \((a + 2, b + 2)\) les numéros de ligne et de colonne de ces deux cases \(A\).

À une symétrie près, il n'y a qu'un chemin possible pour la tour de \((a, b)\) à \((a + 2, b + 2)\). Soit ce chemin \((a, b) \to (a, b + 1) \to (a + 1, b + 1) \to (a + 1, b + 2) \to (a + 2, b + 2)\). Supposons aussi, sans perte de généralité, que la case \((a, b + 1)\) soit de couleur \(B\) (sinon, on échange les rôles des colonnes et des lignes).

Considérons maintenant la case \(A\) \((a, b + 2)\). La seule façon pour la tour d'y passer est \((a - 1, b + 2) \to (a, b + 2) \to (a, b + 3)\) dans cet ordre, puisque, d'après notre hypothèse, après chaque case \(A\) la tour passe par une case \(B\). Pour relier ces deux parties du chemin, il doit donc y avoir un chemin reliant les cases \((a, b + 3)\) et \((a, b)\), et aussi un chemin reliant \((a + 2, b + 2)\) et \((a - 1, b + 2)\).

Mais ces quatre cases sont les sommets opposés d'un quadrilatère convexe, et les chemins sont à l'extérieur de ce quadrilatère ; ils doivent donc se couper. Cela vient du fait suivant : le chemin de \((a, b)\) à \((a, b + 3)\), avec le segment joignant ces deux cases, forme une boucle fermée qui a l'une des cases \((a - 1, b + 2)\) et \((a + 2, b + 2)\) à l'intérieur et l'autre à l'extérieur. Le chemin entre ces deux points doit donc croiser le chemin précédent.

Mais une intersection n'est possible que si une case est visitée deux fois. C'est une contradiction.

Le nombre de cases visitées est donc au plus \(4 \cdot (499^2 - 1)\).

La figure suivante indique une construction récursive, pour tous les échiquiers \(n \times n\) avec \(n \equiv 3 \pmod 4\), qui donne clairement un chemin qui manque exactement une case \(A\) (marquée d'un point : la case centrale de l'échiquier \(15 \times 15\)), et donc, dans le cas \(n = 999\), qui traverse exactement \(4 \cdot (499^2 - 1)\) cases. \(\blacksquare\)