Hastily write an exercise on combinatorial games.

1 files changed, 45 insertions, 0 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index d26a650..fda011b 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -6727,6 +6727,51 @@ deux exercices précédents) ?\spaceout (À chaque fois, plusieurs
 
 \subsection{Jeux combinatoires impartiaux à information parfaite}
 
+\exercice
+
+Soit $k$ un entier naturel fixé.  On considère le jeu suivant : une
+position du jeu consiste en un certain nombre (fini) de jetons placés
+sur des cases étiquetées par les ordinaux.  Par exemple, il pourrait y
+avoir trois jetons sur la case $42$ et un sur la case $\omega$ ; ou
+bien douze jetons sur la case $0$.  Un coup du jeu consiste à retirer
+un jeton sur une case, disons $\alpha$, et le remplacer par exactement
+$k$ jetons situées sur des cases $<\alpha$ quelconques (y compris
+plusieurs fois la même).  Par exemple, s'il y a un jeton sur la
+case $3$ et si $k=7$, on peut le remplacer par quatre jetons sur la
+case $2$ et trois sur la case $0$.  (Le nombre de jetons présents dans
+le jeu augmente donc de $k-1$ à chaque coup joué.)  On remarquera que
+les jetons sur la case $0$ ne peuvent plus être retirés ou servir de
+quelque manière que ce soit : on pourra dire que la case $0$ est la
+« défausse » des jetons.  Le jeu se termine lorsque tous les jetons
+sont sur la case $0$ (=dans la défausse), car il n'est alors plus
+possible de jouer.  Les joueurs (Alice et Bob) jouent à tour de rôle
+et celui qui ne peut plus jouer a perdu.
+
+(1) Montrer que le jeu termine toujours en temps fini.  (On pourra par
+exemple coder la position sous la forme d'un ordinal écrit en forme
+normale de Cantor et montrer qu'il décroît strictement.)
+
+(2) Dans le cas particulier où $k=1$, expliquer pourquoi le jeu est
+simplement une reformulation du jeu de nim.
+
+(3) Dans le cas général, montrer qu'une position du jeu peut s'écrire
+comme somme de nim de positions ayant un seul jeton.
+
+(4) En déduire que la valeur de Grundy d'un état du jeu est la somme
+de nim sur tous les jetons du jeu d'un valeur $f_k(\alpha)$ où
+$\alpha$ est la case où se trouve le jeton.
+
+(5) Donner une définition inductive directe de la fonction $f_k$ (sans
+faire référence à un jeu).  Que vaut $f_k(0)$ ?
+
+(6) Pour $k=1$, que vaut $f_1(\alpha)$ ?
+
+(7) Calculer les premières valeurs de $f_2(n)$.  En considérant le
+nombre de $1$ dans l'écriture binaire de $n-1$, formuler une
+conjecture quant à la valeur de $f_2(n)$.  Montrer cette conjecture.
+
+
+
 \setbox0=\vbox\bgroup
 \subsection{Notions sur les combinatoires partisans à information parfaite}
 \egroup