Jeu de soustraction : de quoi s’agit-il ?
Le jeu de soustraction est le Nim avec une limite à chaque coup. Vous prenez toujours des objets dans la pile de votre choix, mais au moins un et au plus k, où k vaut 2, 3, 4 ou 5, au choix dans la configuration de la table (3 par défaut). Vous ne pouvez prendre une pile entière que si elle contient k objets ou moins.
Tout le reste est comme au jeu classique : les piles de départ viennent de la même option (1, 3, 5 et 7 par défaut), et l’option misère décide si prendre le dernier objet fait perdre (le réglage par défaut ici) ou gagner. Le plafond change l’arithmétique du jeu. Une grande pile ne peut plus être vidée en un coup, elle ne sert donc plus à rétablir la position d’un seul geste, et ce qui compte pour chaque pile, c’est sa taille divisée par k + 1 : le reste.
Changements de règles
| Règle | Nim standard | Jeu de soustraction |
|---|---|---|
| Coups | Nim standardPrenez un objet ou plus dans une pile, autant que vous voulez, jusqu’à la pile entière. | Jeu de soustractionPrenez au moins 1 et au plus k objets dans une pile ; k vaut 2, 3, 4 ou 5, au choix dans la configuration de la table (3 par défaut). |
| Piles | Nim standardPlusieurs piles : 1, 3, 5 et 7 objets par défaut, ou un autre ensemble choisi dans la configuration de la table. | Jeu de soustractionLes mêmes piles, choisies avec la même option. |
| Objectif | Nim standardJeu misère par défaut : celui qui prend le dernier objet perd. La configuration permet de passer au jeu normal, où prendre le dernier objet fait gagner. | Jeu de soustractionPareil, avec la même option misère. |
| Jeu gagnant | Nim standardJeu normal : laissez les piles avec une somme de Nim (le XOR bit à bit de leurs tailles) nulle. Jeu misère : pareil, jusqu’au moment où il ne resterait plus que des piles d’un objet ; laissez-en alors un nombre impair. | Jeu de soustractionJeu normal : chaque pile compte pour le reste de sa taille divisée par k + 1, et vous laissez ces restes avec une somme de Nim nulle ; une pile seule est perdante pour le joueur au trait exactement quand sa taille est un multiple de k + 1. Jeu misère : une pile seule est perdante pour le joueur au trait exactement quand sa taille vaut un de plus qu’un multiple de k + 1. |
Histoire
Les jeux de comptage avec un plafond à chaque coup sont anciens. Les Problèmes plaisants et délectables de Claude-Gaspard Bachet de Méziriac, un recueil de récréations mathématiques publié pour la première fois à Paris en 1612, décrivent un jeu où deux joueurs ajoutent à tour de rôle un nombre de 1 à 10 à un total cumulé, le premier à atteindre 100 gagnant. Le plan gagnant consiste à atteindre les totaux 12, 23, 34 et ainsi de suite jusqu’à 89, par pas de 11 : la même arithmétique qu’une pile unique de 100 dont chaque coup retire de 1 à 10.
Le Nim lui-même a reçu son nom et sa théorie complète de Charles L. Bouton en 1901. Les travaux de Roland Sprague (1935) et de Patrick Grundy (1939) ont montré que tout jeu de ce genre, jeu de soustraction compris, se comporte comme une pile de Nim d’une certaine taille, et c’est ainsi que se résout la version à plusieurs piles. Les jeux de soustraction sont un exemple classique de la théorie des jeux combinatoires, par exemple dans Winning Ways for your Mathematical Plays d’Elwyn Berlekamp, John Conway et Richard Guy.