Le jeu des allumettes

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 27 — Jeux, stratégies et recherche heuristique

Énoncé

Un tas de $n$ allumettes. Chacun leur tour, les deux joueurs en retirent $1$ , $2$ ou $3$ . Celui qui prend la dernière gagne. Modéliser en jeu d'accessibilité, puis déterminer les positions perdantes pour le joueur qui doit jouer.

Corrigé

Le modèle. Un état est un couple $(n, j)$ : le nombre d'allumettes et le joueur qui doit jouer. Le graphe est biparti par construction — chaque coup change de joueur —, ce qui est exactement la forme demandée par le programme. Les états de $J_{1}$ sont les $(n, J_{1})$ , ceux de $J_{2}$ les $(n, J_{2})$ , et l'arc $(n, j) \to (n - k,  ˉ)$ existe pour $k \in {1, 2, 3}$ , $k \leq n$ . La cible de $J_{1}$ est ${(0, J_{2})}$ : « il ne reste rien, et c'est à $J_{2}$ de jouer » signifie que $J_{1}$ vient de prendre la dernière.

Le calcul. L'attracteur, calculé sur les états $(n, J_{1})$ pour $n \leq 24$ , donne :

$n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
$J_{1}$ gagne ?	$\cdot$	G	G	G	$\cdot$	G	G	G	$\cdot$	G	G	G	$\cdot$

et le motif se répète jusqu'à $24$ . Les positions perdantes sont exactement les multiples de $4$ : $0, 4, 8, 12, 16, 20, 24$ .

Pourquoi. Si $n \equiv 0 (mod 4)$ , tout coup $k \in {1, 2, 3}$ laisse $n - k$ non multiple de $4$ ; l'adversaire peut alors reprendre $4 - k$ et rétablir un multiple de $4$ . La suite des multiples de $4$ décroît strictement — c'est encore un variant — et l'on finit à $0$ , où le joueur qui doit jouer ne peut plus rien prendre : il a perdu. Réciproquement, si $n \neq \equiv 0$ , on retire $n mod 4$ et l'on impose le multiple de $4$ à l'adversaire.

La stratégie est sans mémoire, et tient en une ligne : retirer $n mod 4$ allumettes. Elle ne regarde ni les coups passés ni le nombre de tours — la restriction du programme aux stratégies sans mémoire n'est pas une simplification pédagogique, c'est ce que le calcul des attracteurs produit naturellement.

Généralisation, mesurée (par le calcul direct du problème 27.1) : Avec l'ensemble de retraits $S$ , les positions perdantes sont :

$S = {1, 2}$	les multiples de $3$
$S = {1, 2, 3}$	les multiples de $4$
$S = {1, 2, 3, 4}$	les multiples de $5$
$S = {2, 3}$	$n \equiv 0$ ou $1 (mod 5)$
$S = {1, 3, 4}$	$n \equiv 0$ ou $2 (mod 7)$

Pour $S = {1, \dots, k}$ la réponse est « les multiples de $k + 1$ », et la démonstration est celle ci-dessus. Pour les autres $S$ , le motif reste périodique mais la période ne se lit plus sur $S$ : c'est le sujet du problème 27.1.

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.