COMMENT GAGNER ?
L'algorithme est fondé sur un codage des situations, à l'aide
de l'écriture en base deux
(pour le codage en base deux cliquer
ICI).
Prenons l'exemple correspondant à une première ligne de 1 allumette,
une deuxième de 2,
une troisième de 2 et enfin une quatrième ligne de 5
allumettes.
La suite des nombres 1, 2, 2, 5 est codée en base deux 1, 10, 10,101.
Plaçons les nombres verticalement les uns en dessous des autres,
alignés en partant de la droite :
1
10
10
101
--------
ipp
Notons la
parité du nombre de 1 dans chaque colonne.
Ici cela donne ipp
- i pour impair : il y a un seul 1 à gauche,
- p pour pair : la deuxième colonne a deux 1 et
- p pour la troisième colonne qui a deux
1.
On dit quelquefois que l'on ajoute sans retenue en
binaire, dans ce cas ipp donne 100.
Pour GAGNER, il faut laisser à l'adversaire
- soit une situation à un seule lettre qui sera i
: par exemple la dernière allumette
- soit une situation à plusieurs lettres qui sera avec uniquement
DES p.
On peut aussi mémoriser les situations gagnantes :
elles sont dans le jeu présenté ici systématiquement
jouées par l'ordinateur, dès lors qu'il ne joue pas
le premier.
Ceux qui ne sont pas à l'aise avec le binaire ont intérêt
à procéder ainsi.
EXPLICATIONS
J'appelle,
-situation GAGNANTE une situation devant laquelle
en jouant bien, on est sûr de GAGNER (en la transformant en
situation perdante) ;
-situation PERDANTE une situation devant laquelle
on est sûr de perdre,
si l'autre joueur connaît la bonne stratégie.
ATTENTION, cette appellation n'est pas commune à tous les auteurs,
on trouve quelquefois l'appellation contraire.
Pour analyser toutes les situations possibles, on peut décomposer
le nombre d'allumettes, 16,
de toutes les façons possibles, en somme de quatre naturels
correspondant aux nombres d'allumettes possibles
dans les quatre lignes (j'ai rangé ces nombres dans l'ordre
croissant).
De toutes ces décompositions, on ne gardera que celles ayant
- un premier nombre inférieur à 1,
-un deuxième nombre inférieur à 3,
-un troisième nombre inférieur à 5 et
-un quatrième inférieur à 7.
On étudie toutes les situations une à une par ordre
croissant du nombre d'allumettes.
Une situation est GAGNANTE si on peut la ramener en un seul coup
à une situation Perdante,
sinon elle est Perdante.
Dans ce qui suit l'écriture 1247 signifie que l'une
des lignes contient
1 allumette, une autre
2 allumettes, une autre
4 allumettes et enfin une autre
7 allumettes.
On obtient
ainsi :
.avec une allumette
0001
situation PERDANTE puisque celui qui prend la dernière
allumette a perdu.
.avec deux allumettes
0002
ou 0011
GAGNANTES car on peut en un coup les ramener à la situation
0001 qui est perdante.
.avec trois allumettes
0003
Gagnante (ramener à la situation Perdante 0001
en enlevant deux allumettes dans la quatrième ligne)
0012
Gagnante (ramener à 0010 c'est à
dire à la situation Perdante 0001
en enlevant deux allumettes dans la quatrième ligne)
0111 Perdante
.avec quatre allumettes
0004
Gagnante (ramener à 0001
en enlevant trois allumettes dans la quatrième ligne)
0013
Gagnante (ramener à 0010 c'est à
dire 0001 en enlevant
trois allumettes dans la quatrième ligne)
0022 Perdante (codage
pp)
0112
Gagnante (ramener à la situation Perdante
0111
en enlevant une allumette dans la quatrième ligne)
1111
Gagnante (ramener à la situation Perdante
0111
en enlevant deux allumettes dans la première ligne)
.
.
.
.avec quatorze allumettes
0257
Perdante (codage ppp)
1157
Gagnante (codage pip)
0347
Perdante (codage
ppp)
1247
Perdante (codage
ppp)
1337
Gagnante (codage iip)
0356
Perdante (codage ppp)
1256
Perdante (codage ppp)
1346
Perdante (codage ppp)
1355
Gagnante (codage ppi)
.avec quinze allumettes
0357
Gagnante (codage ppi, ramener à 0257)
1257
Gagnante (codage ppi, ramener à 1256)
1347
Gagnante (codage ppi, ramener à 1346)
1356
Gagnante (codage ppi, ramener à 1346)
.avec seize allumettes
1357 Perdante (codage
ppp) . |
Appelons situation
pn, une situation où toutes les colonnes
sont paires avec n>1.
Après
observation de tous les cas,
on note que
-la situation initiale est perdante : si nous sommes en présence
de deux bons joueurs, le premier est sûr de perdre ;
-toutes les situations perdantes sont codées pn
sauf 0001 et 0111.
On démontre que
1°) en retirant des allumettes dans une ligne, une situation pn,
ne peut jamais devenir pn ou i.
2°) on peut transformer en un seul coup une position qui n'est
pas pn, en pn ou
en une situation i.
En effet,
1°) quel que soit le coup joué devant une situation pn,
une seule ligne est affectée et donc de par l'écriture
binaire
(avec chiffre o ou 1 seulement) du nombre d'allumettes
de cette ligne, la parité d'une colonne au moins est modifiée.
2°) devant une position qui n'est pas pn,
-si c'est pi, on retire une allumette dans une ligne
impaire (contenant un nombre impair d'allumettes)
;
-si c'est ppi, on retire une allumette dans une ligne
impaire ;
-si c'est pip, on retire deux (qui s'écrit
10 en binaire) allumettes dans une ligne contenant 2,
3, 6 ou 7 allumettes ;
-si c'est ipp, on retire quatre (qui
s'écrit 100 en binaire) allumettes dans une ligne
contenant 4, 5, 6 ou 7 allumettes ;
-si c'est pii, on retire trois (qui
s'écrit 11 en binaire) allumettes dans une ligne
contenant 3 ou 7 (111 devient 100) allumettes,
ou bien une allumette dans une ligne de 2 (10 devient
01) ou bien encore une dans une ligne de 6 allumettes (100
devenant 011) ;
-si c'est ipi, on retire cinq (qui
s'écrit 101 en binaire) allumettes dans une ligne
contenant 5 ou 7 (111 devient 010) allumettes,
ou bien trois allumettes dans une ligne de 4 (100 devient
001) ou de 6 (110 devient 011) ;
-si c'est iip, on retire six (qui
s'écrit 110 en binaire) allumettes dans une ligne
contenant 6 ou 7 allumettes,
ou bien deux allumettes dans une ligne de 4 (100 devient
010) ou de 5 (101 devient 011) ;
-si c'est iii, on retire une allumette dans une
ligne contenant 4 (100 devient 001) ;
Pour GAGNER, il faut laisser à l'adversaire, soit une situation
i soit une situation pn
avec n>1
