Stratégie gagnante — jeu de Nim

1. Avec 4 allumettes, si A prend 1 → reste 3 → B prend 2 → reste 1 → A doit prendre et perd. Si A prend 2 → reste 2 → B prend 1 → reste 1 → A perd. Si A prend 3 → reste 1 → A avait laissé 1 → B ne peut que prendre 1 → non, c'est A qui prend 3 et laisse 1 → B prend la dernière et perd... Attention : celui qui prend la dernière PERD. Donc avec 1 allumette, le joueur à jouer perd. Avec 4 : tous les coups de A laissent 1, 2 ou 3 à B, et B peut toujours laisser 1 à A. ✓

2. Positions perdantes (celui qui joue perd) : n=1 (doit prendre, perd), n=5 (laisse 1,2,3,4 → B laisse 1 à A), n=9, … → positions perdantes : 1, 5, 9, 13, 17, 21 (congrus à 1 mod 4).

3. 21 ≡ 1 (mod 4) → position perdante pour A. Donc B gagne. Stratégie de B : toujours laisser un multiple de 4 +1 après son coup (→ répondre à k allumettes de A par 4−k allumettes).