Le jeu de Nim est basé sur la représentation binaire (l'écriture en base 2) et l'opération booléenne "ou exclusif" (notée ^ ) donnée par la table suivante.

^ 0 1
0 0 1
1 1 0

Lorsque la représentation binaire comporte plusieurs chiffres, on applique cette table bit par bit. Par exemple, si x = 9 et y = 11, on les écrit en base 2 et on trouve

x = (1001)2

y = (1011)2

x^y = (0010)2

donc x^y = 2.

Notons X, Y, Z, S et T le nombre d'allumettes restant dans les 5 paquets.

Pour être dans une situation gagnante, il faut s'arranger pour qu'après avoir joué : X^Y^Z^S^T = 0 .

Remarque

Chaque bit a une position dans la représentation binaire. Celui le plus à droite est le bit 0, celui d'après le bit 1, etc.
Puisque chaque bit est égal à "1" ou "0", dire que X^Y^Z^S^T = 0 est équivalent à dire que si on considère les 5 nombres X, Y, Z, S et T, chaque bit est égal à "1" un nombre pair de fois (i.e. 0, 2 ou 4).

Preuve

Pour prouver ce résultat, nous devons montrer que :

  1. S'il reste des allumettes et si X^Y^Z^S^T = 0, alors on ne peut pas gagner en un coup.
  2. Si X^Y^Z^S^T = 0, alors après le coup suivant, cela ne peut plus être vrai.
  3. Si X^Y^Z^S^T n'est pas égal à 0, alors on peut toujours enlever des allumettes dans un des paquets pour que cela devienne nul.

Preuve de 1.

D'après la remarque ci-dessus, comme X^Y^Z^S^T = 0, s'il y a un bit égal à "1", il y en a forcement un autre dans la même position (sur une autre ligne). A chaque coup, on ne peut prendre des allumettes que dans un tas, i.e. ne modifier qu'une des lignes. Il est donc impossible de mettre tous les bits à "0" en un seul coup.

Preuve de 2.

Supposons que X^Y^Z^S^T = 0 et que l'on enlève T' allumettes dans le 5e paquet en ayant encore X^Y^Z^S^(T-T') = 0. Alors X^Y^Z^S = T et X^Y^Z^S = T - T' et donc T' = 0.

Preuve de 3.

Supposons que X^Y^Z^S^T = A et que A est différent de 0.
Le bit le plus significatif de A (celui non nul le plus à gauche) vient ou bien des 5 nombres X, Y, Z, S et T, ou bien de 3 d'entre eux, ou bien d'un seul. Sans perte de généralité, on peut supposer que Z y contribue.
On va enlever (Z - (X^Y^S^T)) allumettes dans le 3e tas. Il en restera donc (X^Y^S^T) et on a bien X^Y^(X^Y^S^T)^S^T = 0.
Attention, il faut quand même montrer que c'est possible, i.e. que Z - (X^Y^S^T) > 0.
Nous vous laissons ceci en exercice.

Question

Pouvez-vous décrire la stratégie gagnante dans le cas où, comme dans le jeu de Marienbad, celui qui prend la dernière allumette perd ?