Le jeu des bâtonnets de Fort Boyard est maintenant bien connu : celui qui gagne, c'est celui qui laisse 1 bâtonnet modulo 4. Le gros problème de ce jeu, c'est que tout le monde sait comment gagner (ou du moins, tout le monde sait qu'il existe une stratégie gagnante), et donc, plus moyen de proposer des paris gagnés d'avance.
C'est sans doute pour cela que le fan-tan a été inventé il y a bien longtemps par les Chinois : un jeu gagné d'avance pour celui qui le propose, mais qui n'y paraît pas !

Pour jouer à ce jeu, vous devez disposer de pièces, de jetons, d'allumettes, de cailloux, de grenouilles ou de n'importe quel petits objets manipulables. On présente les jetons en ligne, chaque ligne possédant un nombre différent de jetons (ou pas). Il s'agit d'un jeu à deux participants, au tour par tour. Lorsque c'est à votre tour de jouer, vous choisissez l'une des ligne, et prenez autant de jetons que vous le souhaitez dans cette ligne (même tous les jetons de la ligne si vous le souhaitez). Celui qui prend le(s) dernier(s) jeton(s) de la dernière ligne gagne la partie.

Vous pouvez y jouer en ligne contre l'ordinateur ici.

Exemple de partie, avec 3 lignes de jetons (1, 3 et 5 jetons). Ici, J1 n'est qu'un manipulateur qui n'a laissé aucune chance à sa victime.
Partie_de_Nim

Alors que les Africains l'appellent "Tiouk-tiouk", on connait aujourd'hui ce jeu sous le nom de "jeu de Nim", donné par le mathématicien américain Charles Bouton, en 1901. Le mot "Nim" provient de l'allemand "Nimm" qui signifie "prends"... à moins que cela vienne de l'ancien anglais "Nim" signifiant la même chose... Ou alors, il s'agit de "WIN" écrit la tête à l'envers... L'origine du nom reste obscure, en fait ! On lui prête aussi le nom de "jeu de Marienbad", en référence au film L'Année dernière à Marienbad d'Alain Resnais, où le héros est un grand fan de ce jeu.

Son étude, par contre, n'a rien d'obscure, puisqu'il a complètement résolu le jeu. Pour gagner à ce jeu, il faut connaître les deux secrets : le théorème de Bouton et la maîtrise du XOR mental ! (alias nim-addition)

Par la suite, j'appellerai "configuration" d'un jeu de Nim la liste des nombres de jetons. L'exemple d'au-dessus commençait dans la configuration (1,3,5).
Le théorème de Bouton est le suivant : un joueur qui se trouve dans une configuration dont la nim-addition est non-nulle peut appliquer une stratégie lui assurant la victoire.

Prenons le cas de l'exemple, qui commence par la configuration (1,3,5), sa nim-addition est 7 : puisque J1 commence dans une configuration gagnante (sa nim-adddition n'est pas nulle) et qu'il connaît parfaitement le truc, il n'a eu aucun mal pour gagner !

Reste la question : pourquoi 1⊕3⊕5=7 ?
Pour faire la nim-addition de 1, 3 et 5, il faut simplement poser l'addition, au détail près qu'il faut la faire sans les retenues, et en binaire !
Concrètement, il faut commencer par écrire les nombres sous forme binaire, c'est à dire, trouver sa décomposition en somme de puissances de 2 (1, 2, 4, 8, 16, 32...). Par exemple, le nombre 6 s'écrit 6=4+2, et s'écrit en binaire 110.
On trouve alors que 1 s'écrit 1, 3 s'écrit 11 et 5 s'écrit 101.

Il suffit donc ensuite de poser l'addition, toujours en base 2 et sans les retenues (poser l'addition en admettant que 1+1=0). On peut travailler par colonne : s'il y a un nombre pair de 1, le résultat est 0, sinon, le résultat est 1.

      1 (1)
+   1 1
(3)
+ 1 0 1 (5)
________   
  1 1 1
(7)

On repasse ensuite le résultat en décimal : on trouve bien que 1⊕3⊕5=7.
On peut calculer également la nim-addition de la configuration (1,3,2) : 1⊕3⊕2=0.
(Pour les flemmards, la calculatrice de Windows fait très bien le travail avec la touche XOR)

Il y a alors deux types de configurations : les non-nulles (comme (1,3,5)) et les nulles (comme (1,3,2)). Les non-nulles sont les gagnantes, les nulles sont les perdantes. En enlevant le bon nombre de jetons de la bonne ligne, on peut toujours passer d'une configuration non-nulle à une configuration nulle ; et quelque soit le nombre de jetons que l'on enlève à une situation nulle, elle devient non nulle.
La stratégie gagnante consiste donc à toujours faire en sorte que l'adversaire ait une configuration nulle, ce qui est toujours possible.

Tout ça, c'est de la théorie. Dans la pratique, lon ne cherche qu'à savoir si la nim-addition sera nulle ou non. Les choses sont plus faciles à manipuler : la règle d'or est de "réparer les colonnes".

Pour cela, il faut se matérialiser la décomposition binaire des lignes de jetons en disposant mentalement les jetons par paquets dans des colonnes. Il y aura alors une colonne de paquets de 1, une colonne de paquets de 2, une colonne de paquets de 4 etc.
Par exemple, il faut voir la configuration (1,3,5) de la façon suivante :

Decomp_1_3_5
Décomposition binaire de la configuration (1,3,5)

On se matérialise ainsi la Nim-addition. Puisqu'il y a au moins une des colonnes qui possède un nombre impair de tas (Dans le cas précis, elles sont toutes dans ce cas), la nim-addition n'est pas nulle.

Il faut donc annuler la nim-addition. Pour cela, il faut "réparer les colonnes", c'est à dire,  trouver un moyen pour que chaque colonne ait un nombre pair de paquets (ce qui n'est pas forcément évidement.) Dans notre cas, enlever 3 jetons de la dernière ligne fait l'affaire. On obtient alors la configuration (1,3,2), qui est une configuration perdante pour l'adversaire.

Decomp_1_3_2
Il faut enlever 3 jetons de la dernière ligne pour se ramener à une situation perdante

Il est maintenant temps de s'entrainer ! Nous sommes dans la configuration (12,8,7,4,1). Est-il préférable que vous jouiez en premier et, si oui, que jouer ?

12_8_7_4_1

Solution :
Il faut commencer ! Plusieurs solutions s'offrent alors :
(A) - retirer 2 jetons à la ligne 1
(B) - retirer 6 jetons à la ligne 3
(C) - retirer 2 jetons à la ligne 4

Pour trouver ce résultat, il faut considérer la la décomposition binaire en paquet :

Decomp_12_8_7_4_1
Avant

La colonne (8) et la colonne (1) contiennent un nombre pair de paquets, on ne touchera donc ni à la 2eme, ni à la dernière ligne. Il faut donc chercher à parifier les deux autres colonnes. Pour cela, deux solutions s'offrent : on peut tenter d'avoir 2 paquets par colonnes en décalant les paquets de 4 de la ligne 1 ou 4 (solution (A) ou (C)) ou bien d'avoir 2 paquets dans la 2ème colonne, et aucun dans la troisième, en enlevant le trop plein de la ligne 3 (solution (B)).

Decomp_12_8_1_4_1
Après - solution (B)

Un peu d'entraînement, et, à vous les paris gagnés d'avance !


Sources :
Stratégies magiques au pays de Nim - Pour la science - n°377 - Mars 2009