diff options
Diffstat (limited to 'controle-20190408.tex')
| -rw-r--r-- | controle-20190408.tex | 104 |
1 files changed, 104 insertions, 0 deletions
diff --git a/controle-20190408.tex b/controle-20190408.tex index 429447b..1f6164c 100644 --- a/controle-20190408.tex +++ b/controle-20190408.tex @@ -167,6 +167,18 @@ de remplacement particulières. cela associer judicieusement un ordinal à l'état du jeu et montrer qu'il décroît strictement à chaque tour. +\begin{corrige} +On associe à la position $J(n_1,\ldots,n_r)$ (définie en (2) +ci-dessous), quitte à supposer $n_1>\cdots>n_r$ l'ordinal +$\omega^{n_1} + \cdots + \omega^{n_r}$ ; ou, ce qui revient au même, +s'il y a $r_n$ jetons de type $n$, on considère l'ordinal $\omega^N +r_n + \cdots + \omega^1 r_1 + r_0$ où $N$ est le plus grand type d'un +jeton sur la table. Par la comparaison des ordinaux écrits en forme +normale de Cantor, cet ordinal décroît à chaque coup (puisqu'on +remplace un $\omega^n$ par des $\omega^{n'}$ avec $n' < n$). Le jeu +termine donc en temps fini. +\end{corrige} + \medskip (2)(a) En notant $J(n_1,\ldots,n_r)$ l'état du jeu dans lequel $r$ @@ -183,6 +195,24 @@ en termes simples. (\emph{Convention :} $J()$ est le jeu nul dans lequel il ne reste plus aucun jeton. Notamment, on a $\gr J() = 0$.) +\begin{corrige} +(a) Il s'agit simplement d'observer que les différents jetons + n'interagissent pas du tout. Jouer à la somme de nim de + $J(n_1),\ldots,J(n_r)$ revient donc à jouer à $J(n_1,\ldots,n_r)$. + +(b) On en déduit que $\gr J(n_1,\ldots,n_r) = \gr(J(n_1) \oplus \cdots + \oplus J(n_r)) = \gr J(n_1) \oplus \cdots \oplus \gr J(n_r)$ (la + première égalité par (a), la seconde d'après le fait que la valeur + de Grundy d'une somme de nim est la somme de nim des valeur de + Grundy). + +(c) Le second joueur a une stratégie gagnante à $J(n,n)$ (ceci se voit + par le fait que sa valeur de Grundy vaut $0$). Cette stratégie + consiste à reproduire systématiquement les coups de son adversaire + (ce qui maintiendra un nombre pair de jetons de chaque type à la fin + de son coup). +\end{corrige} + \medskip (3)(a) Pour une règle de remplacement $\mathscr{R}$ donnée, en notant @@ -196,6 +226,19 @@ $\mathscr{R}_0 = \{()\}$ si on veut) : en déduire la valeur de $\gr J(0)$ et celle de $\gr J(0,\ldots,0)$ (avec, disons, $r$ jetons de type $0$). +\begin{corrige} +(a) Puisque $\gr x$, pour une position $x$ d'un jeu combinatoire + impartial bien-fondé, vaut $\mex\{\gr y : y\in\outnb(x)\}$, on a ici + $\gr J(n) = \mex\{\gr J(y) : y\in\mathscr{R}_n\}$, c'est-à-dire $\gr + J(n) = \mex\{\gr J(n'_1) \oplus \cdots \oplus \gr J(n'_r) : + (n'_1,\ldots,n'_r)\in\mathscr{R}_n\}$ d'après (2)(b). + +(b) Dans le cas de $n=0$, on trouve $\gr J(0) = \mex\{0\} = 1$, et par + conséquent $\gr J(0,\ldots,0) = 1\oplus \cdots\oplus 1$ vaut + $0$ ou $1$ selon que $r$ est pair ou impair (si l'on veut, + $\frac{1}{2}(1+(-1)^r)$). +\end{corrige} + \medskip (4) On suppose dans cette question que la règle de remplacement est la @@ -211,6 +254,30 @@ conjecturer une formule générale, et la démontrer par récurrence sur $n$.)\quad(b) Exprimer de façon simple la stratégie gagnante du jeu considéré dans cette question. +\begin{corrige} +(a) On a vu en (3)(b) que $\gr J(0,\ldots,0)$ vaut $0$ ou $1$ selon + que le nombre de jetons est pair ou impair ; on en déduit que $\gr + J(1) = \mex\{0,1\} = 2$, et alors (en se rappelant que $2\oplus + 2=0$) on trouve que $\gr J(1,\ldots,1)$ vaut $0$ ou $2$ selon que le + nombre de jetons est pair ou impair ; on en déduit que $\gr J(2) = + \mex\{0,2\} = 1$, et donc $\gr J(2,\ldots,2)$ vaut $0$ ou $1$ selon + que le nombre de jetons est pair ou impair ; par conséquent, $\gr + J(3) = \mex\{0,1\} = 2$. En général on imagine facilement que $\gr + J(n)$ vaut $1$ ou $2$ selon que $n$ est pair ou impair, et ceci se + démontre par une récurrence immédiate avec exactement le même + argument qu'on vient de faire. + +(b) La valeur de Grundy de $\gr J(n_1,\ldots,n_r)$ est le XOR (= la + somme de nim) de $r$ valeurs $1$ si $r$ est le nombre de jetons de + type pair, et $r'$ valeurs $2$ si $r'$ est le nombre de jetons de + type impair : ce nombre vaut $0$, $1$, $2$ ou $3$ selon que $r$ et + $r'$ sont tous les deux pairs, que $r$ est impair et $r'$ pair, le + contraire, ou qu'ils sont tous les deux impairs. La stratégie + gagnante consiste donc à jouer de façon que le nombre $r$ de jetons + de type pair et le nombre $r'$ de jetons de type impair soient tous + les deux pairs (de façon à annuler Grundy). +\end{corrige} + \medskip (5) On suppose dans cette question que la règle de remplacement est la @@ -226,6 +293,21 @@ conditions, que vaut $\gr J(n)$ ? (On pourra par exemple commencer par calculer $\gr J(n)$ pour $n=0,1,2,3$, conjecturer une formule générale, et la démontrer par récurrence sur $n$.) +\begin{corrige} +On a vu en (3)(b) que $\gr J(0,\ldots,0)$ vaut $0$ ou $1$ selon que le +nombre de jetons est pair ou impair ; on en déduit que $\gr J(1) = +\mex\{0,1\} = 2$, et alors (en se rappelant que $2\oplus 2=0$) on +trouve que $\gr J(1,\ldots,1)$ vaut $0$ ou $2$ selon que le nombre de +jetons est pair ou impair ; on en déduit que $\gr J(2) = \mex\{0,1,2\} += 3$ (la différence avec (4)(a) est que maintenant on peut aussi aller +en $\gr J(0,\ldots,0)$ donc $1$ apparaît dans le $\mex$), et donc $\gr +J(2,\ldots,2)$ vaut $0$ ou $3$ selon que le nombre de jetons est pair +ou impair ; par conséquent, $\gr J(3) = \mex\{0,1,2,3\} = 4$. En +général on imagine facilement que $\gr J(n)$ vaut $n+1$, et ceci se +démontre par une récurrence immédiate avec exactement le même argument +qu'on vient de faire. +\end{corrige} + \medskip (6) On suppose dans cette question que la règle de remplacement est la @@ -242,6 +324,28 @@ générale, et la démontrer par récurrence sur $n$.)\quad(b) Exprimer de façon simple la stratégie gagnante du jeu considéré dans cette question. +\begin{corrige} +(a) On a vu en (3)(b) que $\gr J(0,\ldots,0)$ vaut $0$ ou $1$ selon + que le nombre de jetons est pair ou impair ; on en déduit que $\gr + J(1) = \mex\{0,1\} = 2$, et alors (en se rappelant que $2\oplus + 2=0$) on trouve que $\gr J(0,\ldots,0,\penalty0\relax 1,\ldots,1)$ + vaut $0$, $1$, $2$ ou $3$ selon que le nombre de jetons de chaque + type est pair ou impair (comme expliqué en (4)(b)) ; on en déduit + que $\gr J(2) = \mex\{0,1,2,3\} = 4$, et donc $\gr + J(0,\ldots,0,\penalty0\relax 1,\ldots,1,\penalty0\relax 2,\ldots,2)$ + prend exactement les valeurs entre $0$ et $7$ selon la parité des + jetons de chaque type ; par conséquent, $\gr J(3) = + \mex\{0,\ldots,7\} = 8$. En général on imagine facilement que $\gr + J(n)$ vaut $2^n$, et ceci se démontre par une récurrence immédiate + en remarquant que le $\gr J(n'_1,\ldots,n'_r)$, si les $n'_i$ + sont $<n$, peut prendre toutes les valeurs de $0$ à $2^n - 1$ selon + la parité des jetons de chaque type (donnant l'écriture binaire du + résultat). + +(b) La stratégie gagnante consiste donc à jouer de façon que le nombre + de jetons de chaque type soit pair. +\end{corrige} + % % |