informatique (MP2I/MPI) · Chapitre 27 · Application directe du cours

Problème — Le jeu de soustraction, et sa périodicité

Jeux, stratégies et recherche heuristique · niveau 3 (difficile)

Énoncé

On généralise l'exercice 27.2 : l'ensemble des retraits autorisés est un ensemble fini $S \subseteq {1, 2, \dots}$ , et celui qui prend la dernière allumette gagne.

Écrire le calcul des positions perdantes, sans passer par le graphe biparti.
Démontrer que pour $S = {1, \dots, k}$ les positions perdantes sont les multiples de $k + 1$ .
Montrer que pour tout $S$ fini, la suite des positions perdantes est périodique à partir d'un certain rang.
Vérifier sur $S = {1, 3, 4}$ et $S = {2, 3}$ .

Corrigé de la question 1

1. Le calcul direct. Le graphe biparti $(n, j)$ est utile pour modéliser, mais la position ne dépend pas du joueur : le jeu est impartial. On calcule donc un seul tableau.


(* gagnante.(n) vaut true si le joueur qui doit jouer avec n allumettes gagne.
   Précondition : s est une liste d'entiers >= 1, nmax >= 0.
   INVARIANT : après le tour n de la boucle, gagnante.(0..n) est correct.
   Complexité : Theta(nmax · |s|). *)
let positions s nmax =
  let gagnante = Array.make (nmax + 1) false in
  for n = 1 to nmax do
    gagnante.(n) <-
      List.exists (fun k -> k <= n && not gagnante.(n - k)) s
  done;
  gagnante

La ligne qui porte tout le jeu est not gagnante.(n - k) : une position est gagnante s'il existe un coup menant à une position perdante pour l'adversaire. C'est le $\exists$ du chapitre, et le $\forall$ y est caché dans la négation — une position est perdante quand tous ses coups mènent à des positions gagnantes. Terminaison : boucle bornée. Correction : par récurrence forte sur $n$ , chaque valeur ne dépend que de valeurs d'indice strictement inférieur, déjà calculées.

Question 2 : comment l'IA t'aide

2. Démontrer que pour $S = {1, \dots, k}$ les positions perdantes sont les multiples de $k + 1$ .

Élève

Je fais une récurrence forte. Si $n$ est multiple de $k + 1$ , tout retrait mène à un non-multiple. Mais pour conclure que $n$ est perdante, il me faut savoir que les non-multiples sont gagnantes, ce que je n'ai pas encore montré.

C'est pour cela qu'on démontre l'équivalence entière par récurrence forte : l'hypothèse porte sur tous les rangs inférieurs à $n$ , dans les deux sens. Que te donne-t-elle exactement pour la position $n - j$ ?

Élève

Pour $n - j < n$ , elle dit que $n - j$ est perdante si et seulement si $(k + 1) ∣ (n - j)$ . Comme ce n'est pas le cas, chaque $n - j$ est gagnante.

Bien. Reste l'autre sens : si $n$ n'est pas multiple de $k + 1$ , quel coup précis mène à une position perdante, et pourquoi ce coup est-il toujours autorisé par $S$ ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →