Cliquez pour afficher

Les situations de départ gagnantes sont celles où le reste de la division de b par 4 est 1. Quand ce reste est 3, si le deuxième joueur joue parfaitement, le premier joueur est perdant.

Preuve :
D'abord un tableau avec en lignes les cas a pair ou impair et en colonnes les 4 dernières possibilités pour b (avec 0 la situation finale, le tas est vide) :

b -->	0	1	2	3
a pair	perdant	gagnant	gagnant	perdant
a impair	gagnant	perdant	gagnant	gagnant

Explications :
- Quand le tas est vide, si a est impair, le joueur a gagné ; si a est pair, le joueur a perdu.
- Quand il ne reste plus qu'une allumette dans le tas, le joueur est obligé de la prendre, donc la situation est inversée : si a est impair, il a perdu ; si a est pair, il a gagné.
- Quand il reste deux allumettes dans le tas, on peut amener l'autre joueur sur un des deux cas perdants des colonnes précédentes. b étant pair, si a est impair, c'est que l'autre joueur a un nombre pair d'allumettes et inversement.
- Quand il reste trois allumettes dans le tas, si a est pair, l'autre joueur a aussi un nombre pair d'allumettes. Or les cas a pair des deux colonnes précédentes sont gagnants, donc la situation sera gagnante pour l'autre joueur, donc perdante pour ce joueur. Si a est impair, l'autre joueur a aussi un nombre impair d'allumettes, donc en retirant deux allumettes, on peut l'amener sur un cas perdant (a impair, b=1).

On montre par des raisonnements similaires que ce tableau reste valable si on remplace "b" par "reste de la division par 4 de b".

reste de la division par 4 de b -->	0	1	2	3
a pair	A	B	C	D
a impair	E	F	G	H

- A est perdant parce que l'adversaire sera en G ou H, tous les deux gagnants.
- B est gagnant parce qu'on peut amener l'adversaire en A, perdant.
- C est gagnant parce qu'on peut amener l'adversaire en F, perdant.
- D est perdant parce que l'adversaire sera en B ou C, tous les deux gagnants.
- E est gagnant parce qu'on peut amener l'adversaire en D, perdant.
- F est perdant parce que l'adversaire sera en E ou H, tous les deux gagnants.
- G est gagnant parce qu'on peut amener l'adversaire en A, perdant.
- H est gagnant parce qu'on peut amener l'adversaire en F, perdant.

Au départ a est pair (a=0) et b est impair. On est donc forcément soit dans le cas B (gagnant), soit dans le cas D (perdant), en fonction du reste de la division de b par 4.
Si b=4n+1 (n N) au départ, la stratégie gagnante du premier joueur est de prendre une allumette.

 Cliquez pour afficher

...il peut aussi en prendre 2 puisque les cas A et D sont tous les deux perdants.

Je suppose que ma démonstration est trop longue et que matheuxmatou (ou quelqu'un d'autre) a quelque chose de plus concis, que je me réjouis de lire !

 Cliquez pour afficher

par un raisonnement légèrement différent, mais un tableau sensiblement analogue à ton deuxième tableau, j'arrive au même résultat.

Je n'ai pas de raisonnement sensiblement plus court que le tien... qui est complet.

Sinon que j'aimerais une formulation simple du coup à jouer dans le cas où je suis dans une situation gagnante... j'en prends 1 ou j'en prends 2 en fonction de a et b ? (ou plus simplement de leurs restes modulo respectivement 1 et 4)... histoire de pouvoir faire le calcul de tête sans avoir le tableau sous les yeux

 Cliquez pour afficher

Une stratégie qui fonctionnerait : prendre à chaque fois autant d'allumettes que



ou

(a % 2 == 1) && (b % 4 > 1) ? 2 : 1

J'ai écrit une stratégie, parce que ça m'arrangeait mieux de jouer 1 dans le cas B, mais on aurait aussi pu jouer 2.

 Cliquez pour afficher

effectivement, il y a un cas où on peut jouer ce qu'on veut en restant gagnant.

en appelant a' et b' les restes modulo 2 et 4 de a et b

regarde la quantité 2a'+b'... elle te donne, suivant les cas, le coup à jouer

 Cliquez pour afficher

En effet, et c'est plus concis que mes deux lignes

 Cliquez pour afficher

mais cela revient au même

en fait la situation à jouer est perdante ssi 2a'+b' est multiple de 3

dans les autres cas on prend un nombre d'allumettes égal à la partie entière de ce nombre divisé par 3, plus 1 : 1 allumette si il vaut 1 ou 2 et 2 allumettes s'il vaut 4 ou 5

 Cliquez pour afficher

je m'intéresse au couple formé par le nombre d'allumettes (a) qu'un joueur a déjà au moment où il doit jouer et au nombre restant (b) dans le tas à cet instant là.

Pour (a), c'est sa parité qui semble importante.

si à ce moment celui qui vient de jouer possède (c) allumettes (après avoir joué), il est clair que a+b+c est impair (nombre initial d'allumettes).

Si au moment de jouer la situation est (a ; b impair), et donc (c) de même parité que (a), le coup que je vais jouer laissera mon adversaire devant une situation (même parité que a ; b-1 ou b-2)

et Si au moment de jouer la situation est (a ; b pair), et donc (c) de parité différente de (a), le coup que je vais jouer laissera mon adversaire devant une situation (parité opposée de a ; b-1 ou b-2)

D'où le graphe du jeu (figure 1)



le sommet (pair ; 0) est évidemment perdant (rouge) et le sommet (impair; 0) est gagnant (vert)

Puis je complète suivant le principe suivant :
un sommet qui peut mener à une situation perdante est une situation gagnante
un sommet qui ne peut que mener à une situation gagnante est perdante

Dans un premier temps on obtient ça (figure 2)



Puis en propageant la chose de gauche à droite (figure 3)



on voit bien apparaître le cycle d'ordre 4

la stratégie s'en déduit :

a' (resp b') étant le reste modulo 2 (resp 4) de a (resp b)

si 2a'+b' est multiple de 3, c'est perdu
si 2a'+b' = 1 ou 2 : prendre une allumette
si 2a'+b' = 4 ou 5 : prendre 2 allumettes

 Cliquez pour afficher

 Cliquez pour afficher

Je pense que tu voulais dire "un sommet qui ne peut mener à une situation perdante est perdant"

 Cliquez pour afficher

un sommet qui, quel que soit le coup joué, débouche sur une situation gagnante, est perdant