Les allumettes, théorie et pratique

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 20 — L'étude des jeux : attracteurs et minmax

Énoncé

Pour le jeu des allumettes à prise de $1$ à $3$ , déterminer qui possède une stratégie gagnante et le premier coup à jouer pour les configurations initiales suivantes : $n = 21$ , $n = 24$ , $n = 30$ . Généraliser la règle pour une prise autorisée de $1$ à $k$ allumettes.

Corrigé

La position $n$ est perdante au trait si et seulement si $n \equiv 0 (mod 4)$ .

Pour $n = 21$ : $21 \equiv 1 (mod 4)$ . La position est gagnante pour le premier joueur. Le coup gagnant consiste à retirer $21 mod 4 = 1$ allumette pour laisser $20$ allumettes (multiple de $4$ ) à l'adversaire.
Pour $n = 24$ : $24 \equiv 0 (mod 4)$ . La position est perdante pour le premier joueur. Face à un adversaire jouant parfaitement, $J_{1}$ perdra la partie.
Pour $n = 30$ : $30 \equiv 2 (mod 4)$ . La position est gagnante pour $J_{1}$ . Le coup gagnant consiste à retirer $30 mod 4 = 2$ allumettes pour laisser $28$ allumettes à l'adversaire.
Généralisation (prise de $1$ à $k$ ) : Les positions perdantes au trait sont les multiples de $k + 1$ . La stratégie gagnante consiste à retirer $n mod (k + 1)$ allumettes pour laisser un multiple de $k + 1$ à l'adversaire, puis à compléter chaque prise adverse de $p$ allumettes en retirant $(k + 1) - p$ allumettes.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.