Nim sum of ordinals and games.

1 files changed, 238 insertions, 5 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index a9ccf7f..2646625 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -2804,7 +2804,7 @@ Soit $G$ un graphe orienté bien-fondé dans lequel chaque sommet n'a
 qu'un nombre fini de voisins sortants.  En utilisant le
 théorème \ref{well-founded-definition}, on définit alors une fonction
 $\gr\colon G \to \mathbb{N}$ par $\gr(x) = \mex\{\gr(y) :
-y\in\outnb(x)\}$ où, si $S\subseteq\mathbb{N}$, on note $\mex S
+y\in\outnb(x)\}$ où, si $S\subseteq\mathbb{N}$, on note \index{mex}$\mex S
 := \mathbb{N}\setminus S$ pour le plus petit entier naturel
 \emph{n'appartenant pas} à $S$ ; formellement, c'est-à-dire qu'on pose
 $\Phi(x, g) = \mex\{g(y) : y\in\outnb(x)\}$ et qu'on appelle
@@ -2908,7 +2908,7 @@ $y\in\outnb(x)$.
 
 De même, la fonction de Grundy peut se généraliser à n'importe quel
 graphe bien-fondé en définissant $\gr(x) = \mex\{\gr(y) :
-y\in\outnb(x)\}$ où $\mex S$ désigne le plus petit ordinal
+y\in\outnb(x)\}$ où \index{mex}$\mex S$ désigne le plus petit ordinal
 \emph{n'appartenant pas} à $S$
 (voir \ref{definition-grundy-function-again} pour une écriture
 formelle de cette définition).  Il reste vrai (avec la même
@@ -4234,7 +4234,8 @@ Cette notion de somme peut servir à définir le produit, $\alpha\beta =
 \sum_{\iota<\beta} \alpha$, mais on va le redéfinir de façon plus
 simple :
 
-\thingy Il existe deux façons équivalentes de définir le produit
+\thingy\label{definition-product-of-ordinals}
+Il existe deux façons équivalentes de définir le produit
 $\alpha\cdot\beta$ (ou $\alpha\beta$) de deux ordinaux.
 
 La première façon consiste à prendre un ensemble bien-ordonné $W$ tel
@@ -4575,7 +4576,7 @@ Soit $\alpha$ un ordinal.  On appelle alors \defin{nimbre} associé
   l'ensemble $\alpha+1$),
 \item la relation d'arête (définissant le graphe) est $>$,
   c'est-à-dire que les voisins sortants de $\beta\leq\alpha$ sont les
-  ordinaux $\beta'<\alpha$,
+  ordinaux $\beta'<\alpha$, et
 \item la position initiale est $\alpha$.
 \end{itemize}
 Autrement dit, il s'agit du jeu où, partant de l'ordinal $\beta =
@@ -4593,7 +4594,7 @@ identifier les positions du nimbre $*\alpha$ avec les jeux $*\beta$
 pour $\beta\leq\alpha$.
 \end{defn}
 
-\begin{prop}
+\begin{prop}\label{grundy-of-nimbers-triviality}
 La valeur de Grundy du nimbre $*\alpha$ est $\alpha$.
 \end{prop}
 \begin{proof}
@@ -4605,6 +4606,238 @@ pour $\beta<\alpha$, c'est donc exactement $\alpha$.
 \end{proof}
 
 
+\subsection{Somme de nim}
+
+\begin{defn}
+Soient $G_1,G_2$ deux jeux combinatoires impartiaux dont on note
+$x_1,x_2$ les positions initiales et $E_1,E_2$ les relations d'arêtes.
+On appelle \defin{somme de nim} (ou simplement « somme ») de $G_1$ et
+$G_2$, et on note $G_1 \oplus G_2$ le jeu combinatoire impartial dont
+\begin{itemize}
+\item l'ensemble des positions est $G_1 \times G_2$,
+\item la relation d'arête (définissant le graphe) est $(E_1 \times
+  \id_{G_2}) \cup (\id_{G_1} \times E_2)$, c'est-à-dire que les
+  voisins sortants de $(y_1,y_2) \in G_1 \times G_2$ sont les
+  $(z_1,y_2)$ avec $z_1$ voisin sortant de $y_1$ ainsi que les
+  $(y_1,z_2)$ avec $z_2$ voisin sortant de $y_1$, et
+\item la position initiale est $(x_1,x_2)$.
+\end{itemize}
+\end{defn}
+
+\thingy Autrement dit, jouer à $G_1 \oplus G_2$ signifie que chaque
+joueur a, lorsque son tour vient (depuis la position $(y_1,y_2)$), le
+choix entre jouer dans $G_1$ (c'est-à-dire aller en $(z_1,y_2)$ avec
+$z_1$ voisin sortant de $y_1$ dans $G_1$) \emph{ou exclusif} jouer
+dans $G_2$ (c'est-à-dire aller en $(y_1,z_2)$ avec $z_2$ voisin
+sortant de $y_2$ dans $G_2$).
+
+Il est clair que la somme de nim est commutative et associative, au
+sens où les jeux $G_1 \oplus G_2$ et $G_2 \oplus G_1$ sont isomorphes
+(=les graphes sont isomorphes par un isomorphisme qui envoie la
+position initiale de l'un sur celle de l'autre, en l'occurrence
+$(y_1,y_2) \mapsto (y_2,y_1)$) et de même pour $(G_1 \oplus G_2)
+\oplus G_3$ et $G_1 \oplus (G_2 \oplus G_3)$.  On peut donc parler
+sans souci du jeu $G_1 \oplus \cdots \oplus G_n$ ou $\bigoplus_{i=1}^n
+G_i$ pour la somme de nim d'un nombre fini de jeux.  Il s'agit
+simplement du jeu où chaque joueur, lorsque son tour vient, a la
+faculté de joueur un coup dans un et un seul des $G_i$.
+
+Notamment, si $\alpha_1,\ldots,\alpha_n$ sont des ordinaux, le
+\defin[nim (jeu de)]{jeu de nim} ayant $n$ rangées avec ces nombres
+(« nimbres » !) d'allumettes est défini comme le jeu
+$\bigoplus_{i=1}^n(*\alpha_i)$, c'est-à-dire le jeu où chaque joueur,
+lorsque son tour vient, a la faculté de décroître un et un seul
+des $\alpha_i$.
+
+\begin{prop}\label{nim-sum-is-well-founded}
+Si $G_1,G_2$ sont bien-fondés, alors $G_1\oplus G_2$ est bien-fondé.
+\end{prop}
+\begin{proof}
+S'il existe une suite infinie $x_{(i)} = (x_{(i),1}, x_{(i),2})$ de
+sommets de $G_1 \oplus G_2$ avec $x_{(i+1)}$ voisin sortant
+de $x_{(i)}$, alors soit l'ensemble des $i$ tels que $x_{(i+1),1}$
+soit voisin sortant de $x_{(i),1}$ soit celui des $i$ tels que
+$x_{(i+1),2}$ soit voisin sortant de $x_{(i),2}$ doit être infini :
+dans les deux cas on a une contradiction.  (Autre démonstration : la
+relation d'accessibilité sur $G_1\oplus G_2$ définit l'ordre partiel
+produit, qui est inclus, i.e., plus faible, que l'ordre
+lexicographique, et ce dernier est bien-ordonné
+d'après \ref{definition-product-of-ordinals}.)
+\end{proof}
+
+\begin{defn}
+Soient $\alpha_1,\alpha_2$ deux ordinaux.  On appelle \defin{somme de
+  nim} de $\alpha_1$ et $\alpha_2$ et on note $\alpha_1 \oplus
+\alpha_2$ l'ordinal défini inductivement
+(cf. \ref{scholion-transfinite-definition}) par
+\begin{align*}
+\alpha_1 \oplus \alpha_2 = \mex\big(
+& \{\beta_1\oplus\alpha_2 : \beta_1 < \alpha_1\}\\
+\cup\, & \{\alpha_1\oplus\beta_2 : \beta_2 < \alpha_2\}\big)
+\end{align*}
+Autrement dit, il s'agit du plus petit ordinal qui n'est ni de la
+forme $\beta_1\oplus\alpha_2$ pour $\beta_1 < \alpha_1$ ni de la forme
+$\alpha_1\oplus\beta_2$ pour $\beta_2 < \alpha_2$ ; cette définition a
+bien un sens d'après \ref{nim-sum-is-well-founded}.  Encore autrement
+(en utilisant \ref{grundy-of-nimbers-triviality}), il s'agit de la
+valeur de Grundy du jeu $(*\alpha_1) \oplus (*\alpha_2)$.
+\end{defn}
+
+\thingy Pour comprendre cette définition, le mieux est de calculer
+quelques valeurs.  Voici le tableau des $n_1 \oplus n_2$ pour $n_1 <
+16$ et $n_2 < 16$ :
+{\small\[
+\begin{array}{c|cccccccccccccccc}
+\oplus&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline
+0&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\
+1&1&0&3&2&5&4&7&6&9&8&11&10&13&12&15&14\\
+2&2&3&0&1&6&7&4&5&10&11&8&9&14&15&12&13\\
+3&3&2&1&0&7&6&5&4&11&10&9&8&15&14&13&12\\
+4&4&5&6&7&0&1&2&3&12&13&14&15&8&9&10&11\\
+5&5&4&7&6&1&0&3&2&13&12&15&14&9&8&11&10\\
+6&6&7&4&5&2&3&0&1&14&15&12&13&10&11&8&9\\
+7&7&6&5&4&3&2&1&0&15&14&13&12&11&10&9&8\\
+8&8&9&10&11&12&13&14&15&0&1&2&3&4&5&6&7\\
+9&9&8&11&10&13&12&15&14&1&0&3&2&5&4&7&6\\
+10&10&11&8&9&14&15&12&13&2&3&0&1&6&7&4&5\\
+11&11&10&9&8&15&14&13&12&3&2&1&0&7&6&5&4\\
+12&12&13&14&15&8&9&10&11&4&5&6&7&0&1&2&3\\
+13&13&12&15&14&9&8&11&10&5&4&7&6&1&0&3&2\\
+14&14&15&12&13&10&11&8&9&6&7&4&5&2&3&0&1\\
+15&15&14&13&12&11&10&9&8&7&6&5&4&3&2&1&0
+\end{array}
+\]}
+Chaque case est calculée en prenant la \emph{plus petite valeur qui ne
+  figure pas déjà plus à gauche dans la ligne ou plus haut dans la
+  colonne}.
+
+\begin{prop}\label{nim-sum-is-commutative}
+L'opération $\oplus$ est commutative sur les ordinaux.
+\end{prop}
+\begin{proof}[Première démonstration]
+Par induction transfinie sur $\alpha_1$ et $\alpha_2$, on prouve
+$\alpha_2\oplus\alpha_1 = \alpha_1\oplus\alpha_2$ : en effet,
+$\alpha_2\oplus\alpha_1 = \mex (\{\alpha_2\oplus\beta_1:
+\beta_1<\alpha_1\} \cup \{\beta_2\oplus\alpha_1: \beta_2<\alpha_2\})$,
+et par hypothèse d'induction ceci vaut $\mex (\{\beta_1\oplus\alpha_2:
+\beta_1<\alpha_1\} \cup \{\alpha_1\oplus\beta_2: \beta_2<\alpha_2\}) =
+\alpha_1\oplus\alpha_2$.
+\end{proof}
+\begin{proof}[Seconde démonstration]
+Cela résulte de la commutativité de $\oplus$ sur les jeux et de
+l'observation que $\alpha_1\oplus\alpha_2 = \gr(*\alpha_1 \oplus
+*\alpha_2)$.
+\end{proof}
+
+\begin{prop}\label{zero-is-neutral-for-nim-sum}
+L'ordinal $0$ est neutre pour $\oplus$.
+\end{prop}
+\begin{proof}[Première démonstration]
+Par induction sur $\alpha$, on prouve $\alpha \oplus 0 = \alpha$ : en
+effet, $\alpha \oplus 0 = \mex \{\beta\oplus 0: \beta<\alpha\}$, et
+par hypothèse d'induction ceci vaut $\mex \{\beta: \beta<\alpha\} =
+\mex \alpha = \alpha$.
+\end{proof}
+\begin{proof}[Seconde démonstration]
+Cela résulte de l'observation que $\alpha\oplus 0 = \gr(*\alpha_1
+\oplus *0)$ et du fait que $*0$ est le jeu trivial ayant une seule
+position, si bien que $G\oplus *0 \cong G$ pour n'importe quel $G$.
+\end{proof}
+
+\begin{prop}\label{nim-sum-cancellative}
+Pour tous $\alpha_1,\alpha_2,\alpha_2'$, si $\alpha_1\oplus\alpha_2 =
+\alpha_1\oplus\alpha_2'$, alors $\alpha_2=\alpha_2'$.
+\end{prop}
+\begin{proof}
+Si ce n'est pas le cas, supposons sans perte de généralité que
+$\alpha_2'<\alpha_2$.  Alors $\alpha_1\oplus\alpha_2$ est le $\mex$ d'un
+ensemble contenant $\alpha_1\oplus\alpha_2'$, donc il ne peut pas lui
+être égal, d'où une contradiction.
+\end{proof}
+
+\begin{prop}\label{nim-sum-for-games-versus-ordinals}
+Si $G_1,G_2$ sont deux jeux combinatoires impartiaux bien-fondés ayant
+valeurs de Grundy respectivement $\alpha_1,\alpha_2$, alors la valeur
+de Grundy de $G_1\oplus G_2$ est $\alpha_2\oplus\alpha_2$.
+\end{prop}
+\begin{proof}
+On procède par induction bien-fondée sur les positions de $G_1\oplus
+G_2$ (ce qui est justifié d'après \ref{nim-sum-is-well-founded}) : il
+s'agit de montrer que $\gr(y_1 \oplus y_2) = \gr(y_1) \oplus \gr(y_2)$
+(en notant $y_1\oplus y_2$ la position $(y_1,y_2)$ de $G_1\oplus
+G_2$), et on peut supposer ce fait déjà connu lorsque l'un de $y_1$ ou
+exclusif $y_2$ est remplacé par un voisin sortant.  Or $\gr(y_1 \oplus
+y_2)$ est le plus petit ordinal qui n'est ni de la forme $\gr(z_1
+\oplus y_2)$ (avec $z_1$ voisin sortant de $y_1$) ni de la forme
+$\gr(y_1 \oplus z_2)$ (avec $z_2$ voisin sortant de $y_2$),
+c'est-à-dire, par hypothèse d'induction, ni de la forme $\gr(z_1)
+\oplus \gr(y_2)$ ni de la forme $\gr(y_1) \oplus \gr(z_2)$.  Mais
+quand $z_1$ parcourt les voisins sortants de $y_1$, les ordinaux
+$\gr(z_1)$ sont tous distincts de $\gr(y_1)$ et parcourent au moins
+tous les ordinaux strictement plus petits que lui (c'est la définition
+de $\gr$) : par conséquent, les $\gr(z_1) \oplus \gr(y_2)$ sont tous
+distincts de $\gr(y_1) \oplus \gr(y_2)$ (on a
+utilisé \ref{nim-sum-cancellative}) et parcourent au moins tous les
+$\beta_1 \oplus \gr(y_2)$ pour $\beta_1 < \gr(y_1)$, et de même, les
+$\gr(y_1) \oplus \gr(z_2)$ sont tous distincts de $\gr(y_1) \oplus
+\gr(y_2)$ et parcourent au moins tous les $\gr(y_2) \oplus \beta_2$
+pour $\beta_2 < \gr(y_2)$ : ceci montre bien que le mex de toutes ces
+valeurs est $\gr(y_1) \oplus \gr(y_2)$, c'est-à-dire $\gr(y_1 \oplus
+y_2) = \gr(y_1) \oplus \gr(y_2)$.
+\end{proof}
+
+\begin{prop}\label{nim-sum-associative}
+L'opération $\oplus$ est associative.
+\end{prop}
+\begin{proof}[Première démonstration]
+Par induction sur $\alpha_1$, $\alpha_2$ et $\alpha_3$, on prouve
+$(\alpha_1\oplus\alpha_2) \oplus \alpha_3 = \alpha_1 \oplus
+(\alpha_2\oplus\alpha_3)$.  Pour cela, il suffit de prouver que tout
+ordinal $\xi$ strictement inférieur à l'un des deux membres est
+différent de l'autre.  Par symétrie, supposons $\xi <
+(\alpha_1\oplus\alpha_2) \oplus \alpha_3$ et on veut prouver $\xi \neq
+\alpha_1 \oplus (\alpha_2\oplus\alpha_3)$ : alors on a soit $\xi =
+\gamma \oplus \alpha_3$ avec $\gamma < \alpha_1\oplus\alpha_2$ qui
+peut lui-même s'écrire (A) $\gamma = \beta_1\oplus\alpha_2$ où
+$\beta_1<\alpha_1$ ou bien (B) $\gamma = \alpha_1\oplus\beta_2$ où
+$\beta_2<\alpha_2$, soit (C) $\xi = (\alpha_1\oplus\alpha_2) \oplus
+\alpha_3'$ où $\alpha_3'<\alpha_3$.  Dans le cas (A), en utilisant
+l'hypothèse d'induction, on a maintenant $\xi =
+(\beta_1\oplus\alpha_2) \oplus \alpha_3 = \beta_1 \oplus
+(\alpha_2\oplus\alpha_3)$ et d'après \ref{nim-sum-cancellative} ceci
+est différent de $\alpha_1 \oplus (\alpha_2\oplus\alpha_3)$.  Les cas
+(B) et (C) sont tout à fait analogues.
+\end{proof}
+\begin{proof}[Seconde démonstration]
+Cela résulte de l'associativité de $\oplus$ sur les jeux et de
+l'observation que $\alpha_1\oplus\alpha_2\oplus\alpha_2 =
+\gr(*\alpha_1 \oplus *\alpha_2 \oplus *\alpha_3)$ en
+utilisant \ref{nim-sum-for-games-versus-ordinals}.
+\end{proof}
+
+\begin{prop}\label{nim-sum-has-characteristic-two}
+Pour tout $\alpha$ on a $\alpha\oplus\alpha = 0$.
+\end{prop}
+\begin{proof}[Première démonstration]
+Par induction sur $\alpha$, on prouve $\alpha\oplus\alpha = 0$.  Or on
+a $\alpha\oplus\alpha = \mex\{\beta\oplus\alpha:\beta<\alpha\}$, donc
+il suffit de montrer $\beta\oplus\alpha \neq 0$ pour tout
+$\beta<\alpha$.  Mais si $\beta\oplus\alpha = 0$, puisque l'hypothèse
+d'induction assure $\beta\oplus\beta = 0$,
+avec \ref{nim-sum-cancellative} on conclut $\alpha=\beta$, d'où une
+contradiction.
+\end{proof}
+\begin{proof}[Seconde démonstration]
+Le second joueur a une stratégie gagnante au jeu
+$(*\alpha)\oplus(*\alpha)$ consistant à reproduire chaque coup de son
+adversaire sur l'autre ligne (assurant que la position reste toujours
+de la forme $(*\beta)\oplus(*\beta)$).  On a donc
+$\gr((*\alpha)\oplus(*\alpha))$, c'est-à-dire $\alpha \oplus \alpha =
+0$.
+\end{proof}
+
+
+
 %
 %
 %