Jeux d'allumettes/Exercices/Jeux de Nim

Le jeu de Grundy est une variante du jeu de Nim à deux joueurs

Règle du jeu

La position de départ consiste en un unique tas d'objets (des allumettes par exemple), et le seul coup disponible pour les joueurs consiste à séparer un tas d'objets en deux tas de tailles distinctes. Les joueurs jouent à tour de rôle, jusqu'à ce que l'un d'entre eux ne puisse plus jouer. Le jeu se joue habituellement en version normale, c'est-à-dire que le joueur qui ne peut plus jouer est le perdant.

Un tas de n objets du jeu de Grundy est équivalent à un tas du jeu de Nim d'un certain nombre d'objets (appelé le nimber ou nombre de Grundy - théorème de Sprague-Grundy).

Calculer pour chaque tas (de 0 à 12 tas), quel est son nimber équivalent.

Solution

${\begin{array}{|c|c|c|c|c|c|c|c|c|c|c||c|c|c}taille~du~tas:&0&1&2&3&4&5&6&7&8&9&10&11&12\\nimber:&0&0&0&1&0&2&1&0&2&1&0&2&1\\\end{array}}$.