Ce jeu ancien d’origine incertaine (peut-être en Chine ?) existe sous plusieurs variantes. Il se joue à deux personnes, A et B, avec des bâtonnets (ou des allumettes, des crayons, etc.).
À tour de rôle, A et B retirent des bâtonnets selon une règle préétablie. Dans les variantes appelées jeu gourmand la personne retirant le dernier bâtonnet gagne. Dans les variantes appelées jeu misère, la personne retirant le dernier bâtonnet perd.
Le jeu à une rangée
Un nombre quelconque, n, de bâtonnets est aligné sur une rangée.
À tour de rôle, A et B peuvent prendre 1, 2 ou 3 bâtonnets. Dans le jeu gourmand, la personne qui prend le dernier bâtonnet gagne.
Quelles sont les positions gagnantes ? Commencez par chercher une stratégie pour gagner avant de lire la solution.
Soit m le nombre de bâtonnets au moment où arrive le tour de A. Remarquons que le reste r de la division de m par 4 est 0, 1, 2, ou 3. Si r est non nul, alors A enlève r bâtonnets. C’est maintenant B qui joue. Quel que soit le nombre de bâtonnets qu’il enlève, il ramène le nombre de bâtonnets à un nombre non divisible par 4. On est revenu au cas précédent : le nombre de bâtonnets que prend A est le reste de la division du nombre de bâtonnets par 4, ramenant ainsi le nombre de bâtonnets à un multiple de 4. Et ainsi de suite, chaque fois B n’a d’autre choix que de ramener le nombre de bâtonnets à un nombre non divisible par 4, et chaque fois A ramène ce nombre à un multiple de 4. À un moment donné, il reste quatre bâtonnets. Quel que soit le nombre de bâtonnets pris par B, A prend le reste et gagne.
Donc, une position gagnante est de jouer quand le nombre de bâtonnets n’est pas divisible par 4 et la stratégie est de ramener le nombre de bâtonnets à un multiple de 4.
Dans la section problèmes, vous pouvez trouver la stratégie pour le jeu misère où la personne qui prend le dernier bâtonnet perd.
Le jeu à deux rangées
Des bâtonnets sont alignés sur deux rangées, en nombres respectifs m et n.
À tour de rôle, A et B peuvent prendre un nombre quelconque de bâtonnets, mais sur une seule rangée à la fois. Dans le jeu gourmand, la personne qui prend le dernier bâtonnet gagne.
Quelles sont les positions gagnantes ? Ici encore, cherchez une stratégie avant de lire la solution.
Soient r et s les nombres de bâtonnets sur chaque rangée au moment où arrive le tour de A. Si \(r \neq s\), alors A prend des bâtonnets sur la rangée qui en contient le plus de manière à ramener les deux rangées à un nombre égal de bâtonnets. B est obligé de détruire l’égalité entre les deux rangées et, chaque fois, A peut la ramener. Si B choisissait de prendre tous les bâtonnets d’une rangée, alors A prendrait tous ceux de l’autre rangée et gagnerait. Sinon, le nombre de bâtonnets diminue jusqu’à arriver à un bâtonnet sur chaque rangée. Ici encore, A gagne.
Donc, une position gagnante est de jouer quand les deux rangées n’ont pas le même nombre de bâtonnets et la stratégie est de ramener les deux rangées à un nombre égal de bâtonnets.
Dans la section problèmes, vous pouvez trouver la stratégie pour le jeu misère où la personne qui prend le dernier bâtonnet perd.
Le jeu à un nombre quelconque de rangées
Les règles sont les mêmes que pour le jeu à deux rangées, mais la stratégie est plus complexe. Nous la décrivons ici sur un exemple et dans la section problèmes vous pouvez vous essayer à la prouver après l’avoir pratiquée sur d’autres exemples.
Pour chaque rangée, nous allons écrire le nombre de bâtonnets en base 2 :
\[\begin{array}{l c l}8 &=& 2^3,\\5 &= &2^2 + 2^0,\\7 &=& 2^2 + 2^1+ 2^0.\end{array}\]
Remarquons que 23 et 21 apparaissent un nombre impair de fois et 22 et 20 apparaissent un nombre pair de fois. A doit prendre dans une rangée un nombre de bâtonnets de manière à ce que toutes les occurrences de chaque puissance de 2 apparaissent un nombre pair de fois. Ici A n’a pas le choix et doit prendre dans la première rangée 6 bâtonnets. Les nouveaux nombres sont
\[\begin{array}{l c l}2 &=& 2^1,\\5 &=& 2^2 + 2^0,\\7 &=& 2^2 + 2^1+ 2^0.\end{array}\]
En prenant des bâtonnets dans une seule rangée, B n’a pas d’autre choix que de détruire cette parité et A pourra la ramener au coup suivant.
Donc, une position gagnante est de jouer quand au moins une puissance de 2 apparait un nombre impair de fois et la stratégie est de prendre un nombre de bâtonnets sur une rangée de sorte que chaque puissance de 2 apparaisse un nombre pair de fois (ceci est toujours possible). Remarquez que la stratégie du jeu à deux rangées est un cas particulier de celle-ci.
