summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-04-12 13:04:28 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-04-12 13:04:28 (GMT)
commitb700c1e1959b2a388cd3e7ebc850335679b70085 (patch)
treeaec81f6b63be527acf9fc47353a424f9f9e65617 /notes-mitro206.tex
parent2da2180cd3a34e17316707cfd91f9557c24e122c (diff)
downloadmitro206-b700c1e1959b2a388cd3e7ebc850335679b70085.zip
mitro206-b700c1e1959b2a388cd3e7ebc850335679b70085.tar.gz
mitro206-b700c1e1959b2a388cd3e7ebc850335679b70085.tar.bz2
Continue writing answer to last exercise.
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex48
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.