diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 48 |
1 files changed, 48 insertions, 0 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 061dc89..518663c 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -6758,6 +6758,8 @@ $\omega^{\alpha_i}$ : ceci fait donc décroître strictement l'ordinal en question, et en particulier, la partie doit terminer en temps fini. \end{corrige} +\smallbreak + (2) Dans le cas particulier où $k=1$, expliquer pourquoi le jeu est simplement une reformulation du jeu de nim. @@ -6772,6 +6774,8 @@ nombre d'allumettes de la ligne qui en a $\alpha_i$ pour qu'il en reste $\alpha'_i$. Les jeux sont donc complètement équivalents. \end{corrige} +\smallbreak + (3) Dans le cas général, montrer qu'une position du jeu peut se voir comme somme de nim de positions ayant un seul jeton. Que peut-on dire des positions ayant plusieurs jetons sur la même case ? Expliquer @@ -6809,6 +6813,8 @@ autre jeton, les deux s'annulent — si bien qu'au final il n'y a jamais plus qu'un jeton sur une case donnée. \end{corrige} +\smallbreak + (4) Montrer 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. @@ -6825,11 +6831,53 @@ D'après \ref{summary-of-grundy-theory}, on en déduit que $\gr(x) = \bigoplus_{i=1}^N f_k(\alpha_i)$. \end{corrige} +\smallbreak + (5) Donner une définition inductive directe de la fonction $f_k$ (sans faire référence à un jeu). Que vaut $f_k(0)$ ? +\begin{corrige} +Comme $f_k(\alpha)$ est la valeur de Grundy de la position $u_\alpha$ +ayant un unique jeton sur la case $\alpha$, la définition de la +fonction de Grundy fait que $f_k(\alpha)$ est le $\mex$ de toutes les +valeurs de Grundy des options (=voisins sortants) de $u_\alpha$, +c'est-à-dire des coups qu'on peut faire à partir de là. La règle du +jeu est que ce sont les positions ayant $k$ jetons sur cases +numérotées $<\alpha$, et on a vu que la valeur de Grundy d'une telle +position est la somme de nim des $f_k$ correspondants. On a donc la +définition inductive +\[ +f_k(\alpha) = \mex\Big\{\bigoplus_{i=1}^k f_k(\beta_i) +: \beta_1,\ldots,\beta_k < \alpha \Big\} +\] +c'est-à-dire que $f_k(\alpha)$ est le plus petit ordinal qui ne peut +pas s'écrire comme somme de nim de $k$ valeurs de $f_k$ sur des +ordinaux strictement plus petits. + +Pour $\alpha=0$, notamment, on a $f_k(0) = 0$ d'après la définition +ci-dessus (il s'agit du $\mex$ de l'ensemble vide) ou simplement en se +rappelant que la position $u_0$ ayant un jeton dans la défausse ne +permet pas de faire de coup. +\end{corrige} + +\smallbreak + (6) Pour $k=1$, que vaut $f_1(\alpha)$ ? +\begin{corrige} +La définition inductive trouvée à la question précédente donne +$f_1(\alpha) = \mex\{f_1(\beta) : \beta<\alpha\}$ : une induction +transfinie immédiate montre $f_1(\alpha) = \alpha$ (en effet, si on +suppose que $f_1(\beta) = \beta$ pour tout $\beta<\alpha$, alors la +définition montre que $f_1(\alpha)$ vaut $\mex\{\beta : \beta<\alpha\} += \alpha$). Si on préfère, comme on a vu que le jeu pour $k=1$ est +simplement le jeu de nim, on +invoque \ref{grundy-of-nimbers-triviality} pour affirmer $f_1(\alpha) += \alpha$. +\end{corrige} + +\smallbreak + (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. |