diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 88 |
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 |