From a8f94b41361c3c09e7de5791ad7b9bbaa483976f Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Wed, 23 Mar 2016 17:25:49 +0100 Subject: Another remark on the Grundy function. --- notes-mitro206.tex | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) diff --git a/notes-mitro206.tex b/notes-mitro206.tex index cafa9d2..876c0cc 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -4937,6 +4937,10 @@ impartiaux bien-fondés se calcule donc comme le \emph{ou exclusif} des fonctions de Grundy des composantes. Notamment, la fonction de Grundy d'un jeu de nim est le \emph{ou exclusif} des nombres d'allumettes des différentes lignes. + +Enfin, la fonction de Grundy d'un jeu combinatoire impartial +bien-fondé $G$ peut se voir comme l'unique ordinal $\alpha$ tel que le +second joueur ait une stratégie gagnante dans $G \oplus *\alpha$. \end{thm} \begin{proof} L'affirmation du premier paragraphe résulte @@ -4948,8 +4952,22 @@ de $2$ identiques. L'affirmation du second paragraphe est une reformulation de \ref{nim-sum-for-games-versus-ordinals} (et pour le jeu de nim, cf. aussi \ref{grundy-of-nimbers-triviality}). + +Enfin, l'affirmation du troisième paragraphe en résulte d'après +\ref{nim-sum-cancellative} (pour l'unicité de $\alpha$) +et \ref{nim-sum-has-characteristic-two}. \end{proof} +\thingy On savait déjà que dire que la valeur de Grundy d'un jeu +combinatoire impartial bien-fondé $G$ vaut $0$ signifie que le second +joueur a une stratégie gagnante. On voit maintenant que dire que +cette valeur vaut $1$ signifie que le second joueur a une stratégie +gagnante dans le jeu modifié où les joueurs peuvent passer un tour +exactement une fois dans le jeu (le premier joueur qui utilise cette +faculté la consomme pour tout le monde, et le jeu n'est fini qu'une +fois ce tour consommé) : en effet, c'est simplement une reformulation +du jeu $G \oplus *1$. + % -- cgit v1.2.3