Continue writing answer to last exercise.

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.