diff options
| -rw-r--r-- | notes-mitro206.tex | 45 |
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 |