diff options
| -rw-r--r-- | notes-mitro206.tex | 33 |
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. |