diff options
| -rw-r--r-- | controle-20250626.tex | 66 |
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 |