summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2019-04-04 17:39:58 +0200
committerDavid A. Madore <david+git@madore.org>2019-04-04 17:39:58 +0200
commit8e08c8d40d7e80db19436e14877eb776cc342c3e (patch)
tree76030d6267ca8febd8da1d30e3a7ca63ade15593
parentd6407cdedca4903910adccceba8864e2598efb03 (diff)
downloadmitro206-8e08c8d40d7e80db19436e14877eb776cc342c3e.zip
mitro206-8e08c8d40d7e80db19436e14877eb776cc342c3e.tar.gz
mitro206-8e08c8d40d7e80db19436e14877eb776cc342c3e.tar.bz2
Write answers to exercise 1.
-rw-r--r--controle-20190408.tex104
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}
+
%
%