summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-04-12 12:50:35 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-04-12 12:50:35 (GMT)
commit9b4f30b8ea3ad3a15aac0ee580cbf3aa96813535 (patch)
treec9a18c263e671a5348f2ed8cde69870d5c6d2f9c /notes-mitro206.tex
parent638f444c848689a42ae138388085461d4ad8289f (diff)
downloadmitro206-9b4f30b8ea3ad3a15aac0ee580cbf3aa96813535.zip
mitro206-9b4f30b8ea3ad3a15aac0ee580cbf3aa96813535.tar.gz
mitro206-9b4f30b8ea3ad3a15aac0ee580cbf3aa96813535.tar.bz2
Continue writing answer to last exercise.
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex33
1 files changed, 32 insertions, 1 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 393c5f1..2f020f1 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -6772,12 +6772,43 @@ nombre d'allumettes de la ligne qui en a $\alpha_i$ pour qu'il en
reste $\alpha'_i$. Les jeux sont donc complètement équivalents.
\end{corrige}
-(3) Dans le cas général, montrer qu'une position du jeu peut s'écrire
+(3) Dans le cas général, montrer qu'une position du jeu peut se voir
comme somme de nim de positions ayant un seul jeton. Que peut-on dire
des positions ayant plusieurs jetons sur la même case ? Expliquer
comment on pourrait modifier les règles, sans changer vraiment le jeu,
pour qu'il n'y ait jamais plusieurs jetons sur la même case.
+\begin{corrige}
+Il n'y a aucune interaction entre les jetons dans le jeu. En
+particulier, jouer à une somme de nim de deux positions du jeu
+considéré dans cet exercice revient au même que de jouer à la position
+ayant la réunion de ces deux ensembles de jetons. Par exemple, la
+somme de nim de deux positions, l'une ayant un unique jeton sur la
+case $\alpha$ et l'autre ayant un unique jeton sur la case $\alpha'$
+revient au même que la position ayant deux jetons, un sur la case
+$\alpha$ et l'autre sur la case $\alpha'$ (quitte à se rappeler si un
+jeton est un descendant de celui de la case $\alpha$ ou de celui de la
+case $\alpha'$, on peut transformer toute poisition ou partie d'un jeu
+en une position ou partie de l'autre), et la même chose vaut avec plus
+de deux jetons. (Si on veut être extrêmement rigoureux, « revenir au
+ même » dans ce paragraphe signifie que les jeux en question ont le
+même écrasement transitif, cf. \ref{definition-transitive-collapse},
+ce qui implique notamment qu'ils ont même valeur de Grundy.)
+
+En particulier, deux jetons sur la même case peuvent être considérés
+comme s'annulant (puisque la somme de nim de deux jeux égaux donne un
+jeu nul, c'est-à-dire dont la valeur de Grundy est nulle,
+cf. \ref{nim-sum-has-characteristic-two}) : concrètement, ajouter deux
+jetons sur la même case ne changera jamais rien, dès qu'un joueur joue
+sur l'un, son adversaire pourra reproduire le même coup sur l'autre.
+
+On peut donc modifier la règle du jeu sans le changer
+substantiellement (concrètement, sans en changer la valeur de Grundy)
+en décrétant que si on jeton tombe sur une case déjà occupée par un
+autre jeton, les deux s'annulent — si bien qu'au final il n'y a jamais
+plus qu'un jeton sur une case donnée.
+\end{corrige}
+
(4) Montrer que la valeur de Grundy d'un état du jeu est la somme de
nim sur tous les jetons du jeu d'un valeur $f_k(\alpha)$ où $\alpha$
est la case où se trouve le jeton.