From b700c1e1959b2a388cd3e7ebc850335679b70085 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 12 Apr 2016 15:04:28 +0200
Subject: Continue writing answer to last exercise.

---
 notes-mitro206.tex | 48 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 48 insertions(+)

(limited to 'notes-mitro206.tex')

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.
-- 
cgit v1.2.3