Probleme – Le jeu de soustraction, et sa périodicité

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.

2. Le cas $S=\{1,\dots ,k\}$. Montrons par récurrence forte que $n$ est perdante si et seulement si $(k+1)\mid n$.

• $n=0$ : le joueur ne peut pas jouer, il a perdu. Et $(k+1)\mid 0$.
• Si $(k+1)\mid n$ et $n>0$ : tout coup $j\in \{1,\dots ,k\}$ mène à $n-j$, qui vérifie $n-j\equiv -j\not\equiv 0(\mathrm{mod}k+1)$ puisque $1\le j\le k$. Par hypothèse de récurrence, toutes ces positions sont gagnantes : $n$ est perdante.
• Si $(k+1)\nmid n$ : posons $j=n\mathrm{mod}(k+1)$, qui vérifie $1\le j\le k$. Le coup $j$ est légal et mène à $n-j$, multiple de $k+1$, donc perdante : $n$ est gagnante.

La stratégie s'en déduit : retirer $n\mathrm{mod}(k+1)$, une fonction de la seule position courante — sans mémoire.

3. La périodicité, pour tout $S$ fini. Soit $M=\max S$. La ligne de code ci-dessus montre que $\text{gagnante}(n)$ ne dépend que de $\text{gagnante}(n-M),\dots ,\text{gagnante}(n-1)$, c'est-à-dire de la fenêtre des $M$ valeurs précédentes. Une telle fenêtre est un mot de $\{0,1{\}}^M$ : il n'y en a que $2^M$, donc un nombre fini.

En parcourant $n=M,M+1,\dots$, on lit une suite de fenêtres ; par le principe des tiroirs, deux d'entre elles coïncident au plus tard au rang $M+2^M$. Or la fenêtre détermine entièrement toute la suite qui la suit. Deux fenêtres égales aux rangs $n_1<n_2$ engendrent donc deux suites identiques : la suite est périodique de période $n_2-n_1$ à partir de $n_1$. La borne $2^M$ est grossière — les périodes observées sont très petites — mais elle suffit à établir l'existence.

4. Les vérifications, mesurées.

Pour $\{1,3,4\}$, la période est $7$ et non $\max S+1=5$ : la formule « multiples de $\max S+1$ » ne se généralise pas.

Et $S=\{2,3\}$ réserve un piège, celui de l'exercice 27.9. La position $1$ y est perdante sans être nulle : le joueur ne peut rien retirer, puisque le plus petit retrait vaut $2$, et un joueur qui ne peut pas jouer a perdu. Or si l'on calcule ces positions par un attracteur sur le graphe biparti $(n,j)$, avec le code du cours, on obtient une réponse fausse — $n\equiv 0,1$ ou $4(\mathrm{mod}5)$ au lieu de $n\equiv 0$ ou $1$ — parce que l'état $(1,J_2)$ est un cul-de-sac de $J_2$ que ce code n'ajoute jamais à l'attracteur. Le défaut de l'exercice 27.9 n'est pas une curiosité : il change la réponse du premier jeu venu. La version directe ci-dessus n'y est pas sujette, car sa disjonction List.exists sur une liste de coups vide vaut false, ce qui est exactement « le joueur bloqué perd ».

C'est le genre de cas limite qu'un jeu de tests doit contenir, et le chapitre chap:discipline explique pourquoi : il est aux frontières du domaine.