Another exercise.

1 files changed, 66 insertions, 0 deletions

diff --git a/controle-20250626.tex b/controle-20250626.tex
index c2177ca..6e01fbe 100644
--- a/controle-20250626.tex
+++ b/controle-20250626.tex
@@ -186,6 +186,72 @@ de ceux-ci.
 
 \exercise
 
+On considère dans cet exercice le jeu suivant :
+
+Alice et Bob ont devant eux des piles de jetons, qui représentent
+l'état du jeu.  Les piles sont numérotées $0$, $1$, $2$, etc.  Chaque
+pile contient un certain nombre fini (entier naturel) de jetons.  Il
+n'y a qu'un nombre fini de piles non vides (c'est-à-dire, ayant un
+nombre non-nul de jetons).  Pour représenter la position
+mathématiquement, on utilisera la liste $(n_0, n_1, n_2, \ldots,
+n_{k-1})$ où $n_i$ est le nombre de jetons de la pile numérotée $i$,
+et où ceci signifie implicitement que toutes les piles $\geq k$ sont
+vides.
+
+Un coup d'un joueur consiste à retirer \emph{exactement un} jeton
+d'une certaine pile $i$, de son choix, et d'ajouter \emph{autant qu'il
+le souhaite} (y compris $0$) jetons à chacune des piles $j<i$.  Par
+exemple, à partir de la position $(0,3,2)$ on peut notamment jouer
+vers $(42,1000,1)$ ou bien vers $(0,2,2)$.
+
+Comme d'habitude, le joueur qui ne peut pas jouer a perdu,
+c'est-à-dire que celui qui prend le dernier jeton a gagné.
+
+\textbf{(1)} Montrer que le jeu qu'on vient de définir termine
+forcément en temps fini, quelle que soit la position initiale.  (On
+justifiera soigneusement.)
+
+Appelons « position totalement paire » une position dans laquelle le
+nombre $n_i$ de jetons de chaque pile est pair.
+
+\textbf{(2)} Montrer que tout coup joué depuis une position totalement
+paire conduit nécessairement à une position qui n'est pas totalement
+paire.
+
+\textbf{(3)} Montrer que depuis toute position qui n'est pas
+totalement paire il existe au moins un coup conduisant à une position
+totalement paire.
+
+\textbf{(4)} En déduire quelles sont les positions du jeu dans
+lesquelles le premier joueur a une stratégie gagnante, et quelles sont
+celles dans lesquelles le second joueur en a une.  (On justifiera très
+soigneusement.)
+
+\textbf{(5)} Calculer, en fonction de $n$, la valeur de Grundy de la
+position $(n)$ (c'est-à-dire s'il n'y a que la pile numérotée $0$, et
+qu'elle comporte $n$ jetons).
+
+\textbf{(6)} En déduire la valeur de Grundy des posititions $(0,1)$ et
+$(1,1)$, puis plus généralement de $(n,1)$ en fonction de $n$.
+
+\textbf{(7)} En déduire la valeur de Grundy des positions $(0,2)$ et
+$(1,2)$, plus plus généralement de $(n_0,n_1)$ en fonction
+de $n_0,n_1$.
+
+\textbf{(8)} En déduire la valeur de Grundy de la position $(0,0,1)$.
+
+\textbf{(9)} Conjecturer une formule générale pour la valeur de Grundy
+d'une position $(n_0,n_1,\ldots,n_{k-1})$ quelconque.
+
+\textbf{(10)} Démontrer cette formule.
+
+
+%
+%
+%
+
+\exercise
+
 On se propose dans cet exercice de montrer qu'il existe une partie $A
 \subseteq \{0,1\}^{\mathbb{N}}$ tel que le jeu de Gale-Stewart $G(A)
 := G_{\{0,1\}}(A)$ ne soit pas déterminé (i.e., tel qu'aucun des deux