Shortlist 2018, C2¶

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

Concepts : Coloriages et pavages · Graphes : degrés, chemins, arbres · Jeux et stratégies gagnantes

Solution officielle : Shortlist officielle 2018 (avec solutions), p. 25 (page 27 du PDF)

Problème 4 de l'OIM 2018

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2018, où il était le problème 4 (jour 2).

Énoncé¶

Queenie and Horst play a game on a \(20 \times 20\) chessboard. In the beginning the board is empty. In every turn, Horst places a black knight on an empty square in such a way that his new knight does not attack any previous knights. Then Queenie places a white queen on an empty square. The game gets finished when somebody cannot move.

Find the maximal positive \(K\) such that, regardless of the strategy of Queenie, Horst can put at least \(K\) knights on the board.

Indices : les idées clés

Coloriages : coloriage en damier ; deux cavaliers sur des cases de même couleur ne s'attaquent jamais, ce qui donne la stratégie de Horst.
Graphes : dans le graphe des attaques de cavalier, les cases se regroupent en \(100\) cycles de longueur \(4\).
Jeux et stratégies : stratégie de réponse pour Queenie, qui joue la case opposée dans le cycle où Horst vient de jouer.

Solutions

Les solutions ci-dessous suivent la solution officielle de la Shortlist 2018 (une solution et deux remarques).

Réponse : \(K = 20^2/4 = 100\). Pour un échiquier \(4N \times 4M\), la réponse est \(K = 4NM\).

Solution¶

On donne deux stratégies : l'une permet à Horst de placer au moins \(100\) cavaliers, l'autre permet à Queenie de l'empêcher d'en placer plus de \(100\).

Une stratégie pour Horst : placer les cavaliers uniquement sur des cases noires, tant qu'il en reste de libres. On colorie l'échiquier en noir et blanc de la façon habituelle (les couleurs alternent). Un cavalier change toujours de couleur de case en se déplaçant, donc deux cavaliers placés sur des cases de même couleur ne s'attaquent jamais. Il y a \(20^2/2 = 200\) cases noires. Les deux joueurs occupent les cases à tour de rôle (une case chacun par tour), donc lors de ses \(100\) premiers coups Horst trouve toujours une case noire libre.

Une stratégie pour Queenie : regrouper les cases en cycles de longueur \(4\) et, après chaque coup de Horst, occuper la case opposée dans le même cycle. On considère les cases comme les sommets d'un graphe : deux cases sont reliées si deux cavaliers placés sur ces cases s'attaqueraient. Dans un échiquier \(4 \times 4\), les cases peuvent être regroupées en \(4\) cycles de longueur \(4\) (voir la figure 1 du livret officiel ; par exemple, en numérotant lignes et colonnes de \(1\) à \(4\), le cycle \((1,1) - (2,3) - (4,4) - (3,2) - (1,1)\)). On découpe l'échiquier en \(25\) blocs \(4 \times 4\) et on fait le même regroupement dans chaque bloc : les \(400\) cases sont ainsi réparties en \(100\) cycles.

La stratégie de Queenie est la suivante : chaque fois que Horst place un nouveau cavalier sur une case \(A\), qui appartient à un cycle \(A - B - C - D - A\), Queenie place sa dame sur la case opposée \(C\) de ce cycle. À partir de là, Horst ne peut plus placer de cavalier ni sur \(A\) ni sur \(C\) (cases occupées), ni sur \(B\) ou \(D\) (cases attaquées par le cavalier en \(A\)). Ainsi Horst place au plus un cavalier par cycle, soit au plus \(100\) cavaliers au total.

Les deux stratégies ensemble donnent \(K = 100\). \(\blacksquare\)

Remarques¶

Remarque 1. La stratégie de Queenie se décrit par une règle simple : découper l'échiquier en blocs \(4 \times 4\) ; quand Horst place un cavalier dans un bloc \(P\), Queenie prend le symétrique de cette case par rapport au centre de \(P\) et y place sa dame.

Remarque 2. Le résultat reste le même si Queenie joue en premier. Au premier tour, elle place sa dame n'importe où. Plus tard, si la case où elle devrait jouer contient déjà une dame, elle joue n'importe où.