Exercice 2 — Jouer sur un damier — Olympiades 2012 Paris

Sujet

Deux joueurs établissent les règles d'un jeu : sur un damier rectangulaire de dimensions quelconques \(n \times p\) ( \(n\) lignes et \(p\) colonnes), \(n>1\) et \(p>1\), chaque joueur à tour de rôle coche une case. La case cochée ainsi que toutes celles qui se trouvent au-dessus et à droite, lorsqu'elles existent, sont neutralisées.

Exemple : Dans le cas ci-dessous la croix désigne la case cochée, et le grisé les cases neutralisées

Le perdant est celui qui coche la dernière case. Montrer que celui qui joue le premier a une stratégie gagnante :

dans le cas \(n \times n\) (c'est-à-dire \(p=n\) );
dans le cas \(2 \times p\) (c'est-à-dire \(n=2\) );
dans le cas général.

On considère que les lignes sont numérotées, de haut en bas, de 1 à \(n\); que les colonnes sont numérotées, de gauche à droite, de 1 à \(p\).

Premier cas

Dans le cas \(n \times n\), le premier joueur ( \(J 1\) ) doit cocher la case ( \((n-1)\); 2) de façon à obtenir une configuration ne comportant plus que la première colonne et la dernière ligne. Il reste alors \(2 n-1\) cases. Quelle que soit la réponse du second joueur ( \(J 2\) ), \(J 1\) doit jouer de manière à préserver la symétrie de la configuration et par là-même un nombre de cases impair. J2 ne pourra faire autrement que de cocher la dernière case.

Deuxième cas

Dans le cas \(2 \times p, J 1\) doit cocher la case ( \(1 ; p\) ) (il reste alors \(2 p-1\) cases). Ensuite quelque soit la réponse de \(J 2\) il doit toujours maintenir cet écart d'une case (il restera toujours un nombre impair de cases).
Par exemple :
Si \(J 2\) coche la case \((1 ; r)\) (avec \(1 si \(J 2\) coche la case ( \(1 ; 1\) ), alors \(J 1\) coche ( \(2 ; 2\) ), il ne reste plus alors que la case ( \(2 ; 1\) );
si \(J 2\) coche la case \((2 ; r)\) (avec \(1Cas général Il faut remarquer que ce jeu comporte un nombre fini de coups. Chaque damier permet donc de mettre en œuvre une stratégie gagnante. Il existe un premier coup pour \(J 1\), cocher la case ( \(1 ; n\) ), tel que quelque soit la réponse de \(J 2\), la configuration obtenue à l'issue de ces deux coups aurait pu être obtenue par \(J 1\) dès le premier coup. Cela permet de conclure que le premier joueur a toujours une stratégie gagnante.