Après Cédric Villani il y a un mois, un prof de prépa, Jean-Hervé Cohen, se fait le grand prêtre des énigmes mathématiques du journal Le Monde et lance comme défi de trouver une stratégie gagnante à un jeu basé sur des allumettes[1]. Des allumettes formant le mot espagnol HOY (aujourd'hui) sont disposées sur une table ; le H est constitué de 5 allumettes, le O de 6, et le Y de 4[2] Deux joueurs s'affrontent, en retirant chacun leur tour un nombre non nul d'allumettes à une même lettre du mot, et le gagnant est celui qui prend la dernière allumette. Alors, a-t-on intérêt à commencer ou pas ? Et comment gagner ?

Cliquer pour dévoiler la solution (après avoir réfléchi). Cliquer pour dévoiler la solution (après avoir réfléchi).

Pour comprendre comment gagner, voyons d'abord s'il y a des situations dans le jeu dans lesquelles on est sûr de pouvoir gagner quand c'est à notre tour de jouer (des ''positions gagnantes). En quelque sorte, on part de la fin.

Il y a des positions gagnantes triviales, ce sont celles où il ne reste plus qu'une lettre en jeu. Si la lettre comporte \(n\) allumettes, on peut noter cette position \([n]\). Dans ce cas on ramasse toutes les \(n\) allumettes de ladite lettre et c'est gagné.

Maintenant, que se passe-t-il s'il reste deux lettres en jeu ? Là il y a deux cas :

  • Si les deux lettres comportent le même nombre d'allumettes ( \( [n,n] \) ), alors on est mal. En effet l'adversaire possède une stratégie imparable : jouer en miroir, c'est-à dire jouer à chaque fois comme nous sur l'autre lettre. Il est ainsi assuré de prendre la dernière allumette. Ce cas est donc une position perdante.
  • Si les deux lettres n'ont pas le même nombre d'allumettes, alors c'est le contraire, on a une position gagnante ; en effet on peut amener l'adversaire au cas précédent en retirant le bon nombre d'allumettes à la lettre qui en comporte le plus.

Plus compliqué, il y a maintenant trois lettres en jeu. Que faire ?

  1. Si deux des lettres ont le même nombre d'allumettes \([n,n,m]\), on sait maintenant qu'on peut gagner en enlevant toutes les allumettes de la troisième.
  2. Le cas le plus simple \([m,n,p]\) avec \([m \neq n \neq p]\) est \([1,2,3]\), manifestement perdant puisque chaque coup possiblement joué ramène l'adversaire à un cas précédent gagnant. Donc, \([1,2,p>3]\) et \([1,3,p>3]\) sont gagnants.
  3. Qu'en est-il de \([1,4,5]\) ? De même que dans le cas précédent, chaque coup possiblement joué ramène à un cas précédent gagnant. Donc c'est perdant. Et donc tous les \([1,4,p>5]\) et \([1,5,p>5]\) sont gagnants.
  4. Du coup, en partant du mot HOY...

Cliquer pour dévoiler le bonus qui généralise le jeu (après avoir réfléchi). Cliquer pour dévoiler le bonus qui généralise le jeu (après avoir réfléchi).

  1. Progressivement, il apparaît que toutes les positions sont soit gagnantes, soit perdantes. Cela provient en fait de la symétrie du rôle des joueurs.
  2. Il apparaît aussi que les positions perdantes \([1,n,p]\) sont de la forme \([1,n,n+1]\) avec \(n\) pair, ou autrement dit, \([1,n,n-1]\) avec \(n\) impair. Il y a donc pour chaque valeur de \(n\) une unique valeur possible pour \(p\) correspondant à une position perdante, qui sera \(n+1\) ou \(n-1\) en fonction de la parité de \(n\).
  3. Cela peut s'exprimer plus simplement sous la forme \(p=n \oplus 1\) où \( \oplus \) est la fonction d'addition binaire (appelée également ou exclusif ou XOR en informatique).
  4. Les premières positions perdantes \([m,n,p]\) sont \([2,4,6]\), \([2,5,7]\), \([2,7,9]\) et \([2,8,10]\) ; le cas général est \([2,n,n \oplus 2]\).
  5. Les positions perdantes à trois lettres \([m,n,p]\) sont \([m,n,m \oplus n]\).
  6. On peut alors conjecturer que plus généralement, les positions perdantes \([m_i]\) sont celles pour lesquelles \(\bigoplus_{m_i} = 0\) (cette conjecture se démontre facilement, cf la section 2.4 du lien en fin de texte).

Par définition d'une position gagnante, il est toujours possible de partir de n'importe laquelle de celles-ci pour mettre l'adversaire en position perdante en un unique coup. Et réciproquement jouer une position perdante mettra systématiquement l'adversaire en position gagnante. Les positions gagnantes sont toutes celles pour lesquelles \(\bigoplus_{m_i} \neq 0\).

En pratique, il n'est pas complètement trivial de jouer un bon coup à partir d'une position gagnante. Mais ce n'est pas trop difficile non plus. Illustrons cela sur l'exemple du défi, en écrivant la décomposition binaire de chaque nombre d'allumettes constituant les lettres (avec bit le plus fort à gauche) :

[ b : 4 2 1 ]
[ 5 : 1 0 1 ]
[ 6 : 1 1 0 ]
[ 4 : 1 0 0 ]

On peut agir sur n'importe quelle lettre qui a le bit le plus fort allumé, c'est-à-dire toutes dans notre cas, et la transformer de façon à avoir une somme binaire totale nulle. Il suffit pour cela de la transformer en la somme binaire de toutes les autres lettres, c'est-à-dire faire en sorte que le nombre de 1 dans chaque colonne soit pair. L'intérêt d'avoir le bit le plus fort allumé, c'est d'être sûr que le nombre d'allumettes résultant pour la lettre transformée sera plus petit.

Ainsi à partir de \([5,6,4]\) on a trois choix possibles : \([2,6,4]\), \([5,1,4]\), et \([5,6,3]\), qui mettent toutes l'adversaire en position perdante.

Ce jeu est connu sous le nom de jeu de Nim (en France il est également dénommé jeu de Marienbad en raison de sa présence dans le film L'année dernière à Marienbad), et il est décrit en détails entre autres dans le classique Berlekamp, Conway, & Guy : Winning Ways for your Mathematical Plays. Il y a des variations et des généralisations bien plus complexes.

Note : ce texte sur la théorie des jeux a une approche didactique assez similaire à celle présentée ici.

Questions ou commentaires bienvenus.

Notes

[1] D'ailleurs il y a eu deux autres défis entre temps.

[2] On remarque que le jeu peut être également fait avec "564" écrit en style LCD.