summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-04-12 15:32:17 +0200
committerDavid A. Madore <david+git@madore.org>2016-04-12 15:32:17 +0200
commite1a506c2b7868936f22782b64b3ab08d295e885a (patch)
tree5069c4124942a597b87b081e3eb8e7dc85adb8f1 /notes-mitro206.tex
parentb700c1e1959b2a388cd3e7ebc850335679b70085 (diff)
downloadmitro206-e1a506c2b7868936f22782b64b3ab08d295e885a.tar.gz
mitro206-e1a506c2b7868936f22782b64b3ab08d295e885a.tar.bz2
mitro206-e1a506c2b7868936f22782b64b3ab08d295e885a.zip
Continue writing answer to last exercise.
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex88
1 files changed, 72 insertions, 16 deletions
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