Write answers to exercise 1.

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}
+
 
 %
 %