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

---
 notes-mitro206.tex | 88 ++++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 72 insertions(+), 16 deletions(-)

(limited to 'notes-mitro206.tex')

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 518663c..eea7e7e 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -6737,11 +6737,12 @@ 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.
+quelque manière que ce soit (en tout cas si $k\geq 1$) : 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
@@ -6834,7 +6835,7 @@ D'après \ref{summary-of-grundy-theory}, on en déduit que $\gr(x) =
 \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)$ ?
+faire référence à un jeu).  Que vaut $f_k(0)$ (pour $k\geq 1$) ?
 
 \begin{corrige}
 Comme $f_k(\alpha)$ est la valeur de Grundy de la position $u_\alpha$
@@ -6862,26 +6863,81 @@ permet pas de faire de coup.
 
 \smallbreak
 
-(6) Pour $k=1$, que vaut $f_1(\alpha)$ ?
+(6) Pour $k=1$, que vaut $f_1(\alpha)$ ?  Et pour $k=0$, que vaut
+$f_0(\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
+Pour $k=1$, 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$.
+
+Pour $k=0$, la définition inductive donne $f_0(\alpha) = \mex\{0\}$
+(la somme de nim vide vaut $0$), donc $f_0(\alpha) = 1$ pour
+tout $\alpha$.  Si on préfère, comme le jeu pour $k=0$ consiste
+simplement à ce que chaque joueur tour à tour retire un jeton, il est
+évident que seule compte la parité du nombre total $N$ de jetons, et
+que la valeur de Grundy de ce jeu est égale à $0$ ou $1$ selon que ce
+nombre $N$ total de jetons est pair ou impair.
+\end{corrige}
+
+\smallbreak
+
+(7) Pour tout $k\geq 1$, montrer que $f_k$ est une fonction
+strictement croissante.
+
+\begin{corrige}
+Si $\alpha < \alpha'$ alors $f_k(\alpha')$ est le $\mex$ d'un ensemble
+$\{\bigoplus_{i=1}^k f_k(\beta_i) : \beta_1,\ldots,\beta_k <
+\alpha'\}$ qui contient celui $\{\bigoplus_{i=1}^k f_k(\beta_i) :
+\beta_1,\ldots,\beta_k < \alpha\}$ dont $f_k(\alpha)$ est le $\mex$.
+Mais par ailleurs, $f_k(\alpha') \neq f_k(\alpha)$ puisqu'on peut
+prendre $\beta_1 = \alpha$ et $\beta_2,\ldots,\beta_k = 0$ (et qu'on a
+vu $f_k(0) = 0$).  On a donc $f_k(\alpha') > f_k(\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
+(8) Calculer les premières valeurs de $f_2(n)$ (pour $n$ entier
+naturel).  En considérant le nombre $n-1$ et notamment la parité du
+nombre de $1$ dans l'écriture binaire de $n-1$, et/ou la parité du
+nombre de $1$ dans l'écriture binaire de $f_2(n)$, formuler une
 conjecture quant à la valeur de $f_2(n)$.  Montrer cette conjecture.
 
+\begin{corrige}
+On a vu que $f_2(n)$ est défini inductivement (i.e., récursivement)
+comme le plus petit entier naturel qui n'est pas de la forme $f_2(n_1)
+\oplus f_2(n_2)$ avec $n_1,n_2<n$.  Pour faciliter les calculs, on
+peut aussi remarquer que (pour $n>0$) c'est le plus petit entier
+naturel \emph{non nul} qui n'est pas sous la forme $f_2(n_1) \oplus
+f_2(n_2)$ avec $n_1 < n_2 < n$ (en effet, le cas $n_1 = n_2$ donne de
+toute façon zéro, et dans les autres cas, par symétrie on peut prendre
+$n_1 < n_2$) ; ou encore, si on préfère séparer le cas $n_1=0$ du
+reste : le plus petit entier naturel non nul qui n'est pas ni sous la
+forme $f_2(n')$ pour $0<n'<n$ ni sous la forme $f_2(n_1) \oplus
+f_2(n_2)$ pour $0<n_1<n_2<n$.  On calcule ainsi de proche en proche :
+
+\begin{center}
+\begin{tabular}{r|ccccccccccc}
+$n$&$0$&$1$&$2$&$3$&$4$&$5$&$6$&$7$&$8$&$9$&$10$\\\hline
+$n-1$&&$0$&$1$&$2$&$3$&$4$&$5$&$6$&$7$&$8$&$9$\\\hline
+$f_2(n)$&$0$&$1$&$2$&$4$&$7$&$8$&$11$&$13$&$14$&$16$&$19$\\
+\end{tabular}
+\end{center}
+
+En considérant la partié du nombre de $1$ dans l'écriture binaire de
+$n-1$ et/ou de $f_2(n)$, on constate expérimentalement que (A) les
+valeurs $f_2(n)$ pour $n>0$ ont un nombre impair de $1$ dans leur
+écriture binaire, et sont même exactement tous ces nombres rangés par
+ordre croissant, et (B) $f_2(n)$ vaut $2(n-1)$ ou $2(n-1)+1$ selon que
+$n-1$ a un nombre impair ou pair de $1$ dans son écriture binaire.
+\end{corrige}
+
 
 
 \setbox0=\vbox\bgroup
-- 
cgit v1.2.3

