Ce jeu est très ancien ; sa 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), par exemple, est aussi une configuration perdante.
Ces résultats sont intéressants, et on pourrait élargir pas à pas un catalogue de configurations gagnantes ou perdantes. Mais l'écriture des entiers en base 2 apporte beaucoup plus : une 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 dix 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.
Soit une configuration de k paquets de tailles respectives (x1, x2, …, xk). Sa représentation binaire est le tableau de k lignes dont la ligne de rang i est la suite des chiffres de l'écriture binaire de xi, complétée à gauche par des 0 pour que toutes les lignes aient la même longueur. La représentation binaire de la configuration (12, 10, 6, 5) est donc le tableau formé des 4 lignes bleues ci-dessous :
| 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 colonne de ce tableau est paire si la somme de ses chiffres est paire. On dit qu'une configuration est paire si toutes ses colonnes sont paires. Sinon, c'est à dire si l'une au moins de ses colonnes est impaire, on dit qu'elle est impaire.
Les sommes des quatre colonnes de la configuration (12, 8, 6, 5) sont 2, 3, 2, 1. C'est une configuration impaire car la deuxième et la quatrième colonne sont impaires.
| 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 jouant depuis une configuration paire, on ne peut que la rendre impaire : En effet, puisqu'on ne modifie qu'un paquet, seule la ligne des chiffres de ce paquet est modifiée. L'un des chiffre au moins est modifié, ce qui rend impaire la somme de la colonne contenant ce chiffre.
En jouant bien dans une configuration impaire, on peut toujours la rendre paire : On choisit l'un quelconque des paquets de taille x dont le chiffre dans colonne impaire la plus à gauche est un 1.
Soit y le nombre obtenu en inversant (c'est à dire en remplaçant 0 par 1 ou 1 par 0) les chiffres de x figurant dans une colonne impaire. Alors y est plus petit que x. On rétablit la parité en remplaçant x par y, c'est à dire en retranchant x-y allumettes de ce paquet.
Dans le cas de la configuration (12, 10, 6, 5) représentée ci-dessus, la colonne impaire la plus à gauche est la deuxième, de somme 3. On choisit donc l'un quelconque des paquets de deuxième chiffre 1 c'est à dire l'un des paquets 12, 6, 5, et on inverse son deuxième et son quatrième chiffre.
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. Dès qu'il ne reste plus qu'un seul paquet contenant plusieurs allumettes, le coup gagnant consiste à jouer avec ce paquet, en le supprimant entièrement ou en y laissant une allumette, de façon à laisser un nombre impair de paquets réduits à une allumette.