David Gale (1921—2008).
Cette variante des jeux de Nim sur un quadrillage est due au mathématicien David Gale.
On part d’un damier à N lignes et P colonnes, dont les cases sont blanches à l’origine. Chaque joueur à tour de rôle choisit une case blanche et la colorie.
Immédiatement et automatiquement, toutes les cases situées à droite et au-dessus de cette case se colorient elles aussi. Le perdant est celui qui est contraint de colorier tout le rectangle, c’est-à-dire celui qui ne trouve libre que la case ultime en bas à gauche.
Sauriez-vous montrer, sans pour autant la donner, que le premier joueur a toujours une stratégie gagnante ?
Quelle est cette stratégie dans les cas où P = 2 ? Dans le cas P = N ?
SOURCES
Les cinq piliers du divertissement mathématique (tome 1, algorithmes, jeux et stratégie), Élisabeth Busser et Gilles Cohen, POLE, 2013