Ce jeu est assez ancien, la stratégie gagnante a été publiée en 1901 par le mathématicien américain Charles Bouton. Il oppose deux joueurs. On dispose sur une table quelques paquets d'allumettes, c'est la configuration initiale. À tour de rôle chaque joueur choisit un paquet et retire de celui-ci un nombre quelconque d'allumettes, éventuellement toutes. Le gagnant est celui qui prend la dernière allumette. Vous pouvez jouer en ligne ici.
Une configuration est gagnante si à partir de celle-ci on est certain de gagner en choisissant chaque fois le meilleur coup. Une configuration est perdante si en jouant depuis celle-ci on est assuré de perdre contre un joueur qui joue au mieux.
Il suffit de quelques parties pour constater que toute configuration formée de deux paquets de même taille est perdante. Si A est le premier joueur son adversaire B est sûr de gagner en retirant, après chaque coup de A, le même nombre d'allumettes, mais de l'autre paquet.
On découvre aussi rapidement que (3, 2, 1) est perdante. Le joueur A amène cette configuration à (2, 2, 1) ou (1, 2, 1) ou (2, 1) s'il choisit le premier paquet, (3, 1, 1) ou (3, 1) s'il choisit le deuxième paquet et (3, 2) s'il choisit le dernier. Après le coup de A, B joue donc avec l'une des 6 configurations (2, 2, 1), (1, 2, 1), (2, 1), (3, 1, 1), (3, 1), (3, 2) qui sont toutes gagnantes car, chacune d'elles peut être transformée en (1, 1) ou (2, 2) par le retrait d'une allumette bien choisie.
Ces résultats sont intéressants, et on pourrait élargir pas à pas un catalogue de positions gagnantes ou perdantes. Mais l'écriture des entiers en base 2 apporte beaucoup plus, un caractérisation très simple des configurations perdantes.
L'écriture en base 10 des entiers, celle que nous utilisons tous les jours, consiste à écrire chaque entier à l'aide des puissances de 10, les nombres 1, 10, 100, 1000... et des dix chiffres 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. L'écriture décimale 457 est une abréviation de l'expression 4 × 100 + 5 × 10+ 7 × 1.
L'écriture en base 2 fonctionne de la même manière, en remplaçant les puissances de 10 par les puissances de 2, les nombres 1, 2, 4, 8, 16, 32 … et les 10 chiffres 0, 1,..., 9 par les deux chiffres binaires 0 et 1.
L'écriture en base 2 1101 est une abréviation de 1 × 8 + 1 × 4 + 0 × 2 + 1 × 1, c'est à dire 13.
Dans l'autre sens, pour passer de l'écriture décimale d'un entier, 21 par exemple, à son écriture binaire, on part de la plus grande puissance de 2 qui ne dépasse pas 21 c'est à dire 16. Puis on écrit 21 = 16 + 5. La plus grande puissance de 2 qui ne dépasse pas 5 est 4, et 5 = 4 + 1 ce qui nous donne 21 = 16 + 4 + 1 et donc 21 = 1 × 16 + 0 × 8 + 1 × 4 + 0 × 2 + 1 × 1, qu'on abrège en 10101. Dans la suite toute écriture d'un nombre en bleu est une écriture en base 2. Avec cette convention on peut donc écrire 14 = 1110.
| 8 | 4 | 2 | 1 | |
| 12 | 1 | 1 | 0 | 0 |
| 10 | 1 | 0 | 1 | 0 |
| 6 | 0 | 1 | 1 | 0 |
| 5 | 0 | 1 | 0 | 1 |
On dit qu'une configuration est équilibrée ou paire, si pour chaque colonne de sa représentation binaire, le nombre de chiffres 1 figurant dans cette colonne est un nombre pair. Une configuration qui n'est pas équilibrée est dite déséquilibrée ou impaire. Dans le cas de la configuration (12, 10, 6, 5), les nombres de 1 figurant dans les 4 colonnes sont, respectivement, 2, 3, 2, 1. Ces 4 entiers ne sont pas tous pairs. La configuration (12, 10, 6, 5) est donc une configuration impaire.
| 8 | 4 | 2 | 1 | |
| 12 | 1 | 1 | 0 | 0 |
| 10 | 1 | 0 | 1 | 0 |
| 6 | 0 | 1 | 1 | 0 |
| 5 | 0 | 1 | 0 | 1 |
| 2 | 3 | 2 | 1 |
En effet:
Démontrons donc les points 1 et 2
Soit p une configuration paire. En jouant depuis cette configuration on ne modifie qu'un paquet, donc qu'une ligne de sa présentation binaire. Dans cette ligne l'un des chiffres au moins est inversé, de 0 à 1, ou de 1 à 0. Dans les deux cas, la somme des chiffres de la colonne concernée, qui était paire, devient impaire.
Soit par exemple la configuration déséquibrée (12, 10, 6, 5).
Puisque la deuxième et la quatrieme colonne sont de sommes impaires, pour équilibrer cette position en jouant avec un paquet de taille x, il faut inverser le deuxième et le quatrième chiffre de x.
Pour jouer avec le 12 = 1100 par exemple, il faut le remplacer par 1001 = 5, c'est à dire retrancher 7 allumettes.
Mais on ne peut pas jouer avec le 10 =1010 car il faudrait le remplacer par 1111 = 15, c'est à dire ajouter 5 allumettes.
Avec le 6, en retirant 3 allumettes on remplace 6 = 0110 par 0011 = 3.
Avec le 5, en retirant les 5 allumettes on remplace 5 = 0101 par 0000 = 0, en ne laissant ainsi que les trois paquets (12, 10, 6).
Il y a une solution avec chaque paquet dont le premier chiffre à inverser est un 1.
En pratique, avec un peu d'habitude, on joue souvent plus rapidement, avec en tête un répertoire de combinaisons perdantes simples, comme par exemple (×, ×), (1, 2×, 2×+1). On passe alors après un simple coup d'oeil, de (x, x, y) à (x, x), ou de (2x, 2x+1, y) à (2x, 2x+1, 1).
Une recette assez pratique pour obtenir la valeur y à substituer à x, est de remarquer que le kème chiffre de y est la somme modulo 2 des kème chiffres des autres paquets. Pour le paquet de taille 6, par exemple, les écritures binaires des autres paquets sont 1100, 1010 et 101. Additionnons ces 3 nombres comme s'il s'agissait de nombres décimaux, on obtient la somme 2211, et en réduisant ces chiffres modulo 2, c'est à dire en remplaçant les chiffres impairs par 1, et les chiffres pairs par 0, on obtient 0011 = 11, l'écriture binaire de 3. Evidemment ceci ne fonctionne que s'il n'y a pas plus de 10 paquets.
On peut aussi jouer en convenant que le perdant est celui qui prend la dernière allumette. Dans ce cas, une configuration dont tous les paquets contiennent une seule allumette est perdante si et seulement si le nombre des paquets est impair. La stratégie gagnante est inchangée tant qu'il reste au moins deux paquets contenant plus d'une allumette. La première fois qu'il ne reste plus qu'un paquet contenant plusieurs allumettes, le coup gagnant est de jouer avec ce paquet en le supprimant entièrement ou en laissant une allumette pour ramener la configuration à un nombre impair de paquets réduits à une allumette.
_______________________________________