Nim sum is XOR.

1 files changed, 123 insertions, 9 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 2646625..cafa9d2 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -569,9 +569,9 @@ impartial à connaissance parfaite (un cas particulier du jeu général
 défini en \ref{introduction-graph-game}).  On verra que la théorie de
 Grundy permet de décrire exactement la stratégie gagnante : en
 anticipant sur la suite, il s'agit de calculer le XOR (= « ou
-  exclusif », appelé aussi \textit{somme de nim} dans ce contexte des
+  exclusif », appelé aussi \index{nim (somme de)}\index{somme de nim}\textit{somme de nim} dans ce contexte des
 nombres $n_i$ d'allumettes des différentes lignes (écrits en
-binaire) : ce XOR s'appelle la \textit{fonction de Grundy} de la
+binaire) : ce XOR s'appelle la \index{Grundy (fonction de)}\textit{fonction de Grundy} de la
 position, et le jeu est gagnable par le second joueur (c'est-à-dire,
 celui qui \emph{vient de} jouer) si et seulement cette fonction de
 Grundy vaut $0$.  (À titre d'exemple, la position de départ la plus
@@ -4152,8 +4152,8 @@ Les résultats de cette section seront admis (ils ne sont pas très
 difficiles à montrer — presque toujours par induction transfinie —
 mais seraient trop longs à traiter en détails).
 
-\thingy Il existe deux façons équivalentes de définir la somme
-$\alpha+\beta$ de deux ordinaux.
+\thingy\label{definition-sum-of-ordinals} Il existe deux façons
+équivalentes de définir la somme $\alpha+\beta$ de deux ordinaux.
 
 La première façon consiste à prendre un ensemble bien-ordonné $W$ tel
 que $\alpha = \#W$ et un ensemble bien-ordonné $W'$ tel que $\beta =
@@ -4608,10 +4608,10 @@ pour $\beta<\alpha$, c'est donc exactement $\alpha$.
 
 \subsection{Somme de nim}
 
-\begin{defn}
+\begin{defn}\label{definition-nim-sum-of-games}
 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
+On appelle \index{nim (somme de)}\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$,
@@ -4665,8 +4665,8 @@ 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
+\begin{defn}\label{definition-nim-sum-of-ordinals}
+Soient $\alpha_1,\alpha_2$ deux ordinaux.  On appelle \index{nim (somme de)}\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
@@ -4711,6 +4711,12 @@ 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}.
 
+\thingy\label{remark-on-dealing-with-mex} Dans ce qui suit, on
+utilisera souvent implicitement le raisonnement suivant : pour montrer
+que $\mex S = \alpha$, il suffit de montrer que (1) tout élément de
+$S$ est différent de $\alpha$, et que (2) tout ordinal $<\alpha$
+appartient à $S$.
+
 \begin{prop}\label{nim-sum-is-commutative}
 L'opération $\oplus$ est commutative sur les ordinaux.
 \end{prop}
@@ -4781,7 +4787,8 @@ 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
+pour $\beta_2 < \gr(y_2)$ : ceci montre bien
+(cf. \ref{remark-on-dealing-with-mex}) 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}
@@ -4836,6 +4843,113 @@ $\gr((*\alpha)\oplus(*\alpha))$, c'est-à-dire $\alpha \oplus \alpha =
 0$.
 \end{proof}
 
+\begin{prop}\label{nim-sum-multiple-sum}
+La somme de nim $\alpha_1\oplus\cdots\oplus\alpha_n$ est le plus petit
+ordinal qui n'est pas de la forme
+$\alpha_1\oplus\cdots\oplus\beta_i\oplus \cdots\oplus\alpha_n$, où
+exactement un des $\alpha_i$ a été remplacé par un ordinal $\beta_i$
+strictement plus petit.
+\end{prop}
+\begin{proof}
+On procède par récurrence sur $n$.  Tout d'abord, en
+utilisant \ref{nim-sum-cancellative}, on voit que chaque $\alpha_1
+\oplus \cdots \oplus \beta_i \oplus \cdots \oplus \alpha_n$ est
+différent de $\alpha_1 \oplus \cdots \oplus \alpha_n$.  D'autre part,
+si $\xi < \alpha_1 \oplus \cdots \oplus \alpha_n$, alors quitte à
+écrire $\alpha_1 \oplus \cdots \oplus \alpha_n = \alpha' \oplus
+\alpha_n$ avec $\alpha' := \alpha_1 \oplus \cdots \oplus
+\alpha_{n-1}$, on a soit $\xi = \gamma \oplus \alpha_n$ où $\gamma <
+\alpha'$, soit $\xi = \alpha' \oplus \beta_n$ où $\beta_n <
+\alpha_n$ ; le second cas a bien la forme $\xi = \alpha_1 \oplus
+\cdots \oplus \alpha_{n-1} \oplus \beta_n$ voulue, et dans le premier
+cas l'hypothèse de récurrence permet d'écrire $\gamma = \alpha_1
+\oplus \cdots \oplus \beta_i \oplus \cdots \oplus \alpha_{n-1}$ avec
+$\beta_i < \alpha_i$ (où $i\leq n-1$), d'où $\xi = \alpha_1 \oplus
+\cdots \oplus \beta_i \oplus \cdots \oplus \alpha_n$.  Ceci prouve
+bien que $\alpha_1 \oplus \cdots \oplus \alpha_n$ est le plus petit
+ordinal qui ne soit pas de la forme $\alpha_1 \oplus \cdots \oplus
+\beta \oplus \cdots \oplus \alpha_n$, comme souhaité.
+\end{proof}
+
+\begin{prop}\label{nim-sum-of-powers-of-two-is-ordinary-sum}
+Soient $\gamma_1 > \cdots > \gamma_r$ des ordinaux : alors la somme
+usuelle (cf. \ref{definition-sum-of-ordinals}) $2^{\gamma_1} + \cdots
++ 2^{\gamma_r}$ des puissances de $2$ correspondantes coïncide avec la
+somme de nim $2^{\gamma_1} \oplus \cdots \oplus 2^{\gamma_r}$.
+\end{prop}
+\begin{proof}
+On procède par induction transfinie sur $2^{\gamma_1} + \cdots +
+2^{\gamma_r}$.  On veut montrer que $\alpha := 2^{\gamma_1} + \cdots +
+2^{\gamma_r}$ est égal à $2^{\gamma_1} \oplus \cdots \oplus
+2^{\gamma_r}$, c'est-à-dire, d'après \ref{nim-sum-multiple-sum}, qu'il
+s'agit du plus petit ordinal qui n'est pas de la forme $2^{\gamma_1}
+\oplus \cdots \oplus \beta_i \oplus \cdots \oplus 2^{\gamma_r}$ pour
+un certain $\beta_i < 2^{\gamma_i}$.  Pour ceci
+(cf. \ref{remark-on-dealing-with-mex}), il suffit de montrer que
+(1) $\alpha$ n'est pas de la forme qu'on vient de dire, et que
+(2) tout ordinal $<\alpha$ l'est.
+
+Or dans la somme de nim $2^{\gamma_1} \oplus \cdots \oplus \beta_i
+\oplus \cdots \oplus 2^{\gamma_r}$ avec $\beta_i < 2^{\gamma_i}$, en
+écrivant $\beta_i$ en binaire et en utilisant l'hypothèse d'induction,
+on a $beta_i = 2^{\gamma'_1} \oplus \cdots \oplus 2^{\gamma'_s}$ où
+$\gamma_i > \gamma'_1 > \cdots > \gamma'_s$.  Avec les propriétés déjà
+démontrées sur la somme de nim (commutativité, associativité, et
+surtout \ref{nim-sum-has-characteristic-two}), on peut supprimer les
+puissances de $2$ qui apparaissent deux fois et on obtient ainsi une
+somme de nim de puissances de $2$ distinctes qui fait intervenir les
+puissances $2^{\gamma_1}$ à $2^{\gamma_{i-1}}$ et certaines puissances
+strictement plus petites que $2^{\gamma_i}$.  En utilisant de nouveau
+l'hypothèse d'induction, cette somme se revoit comme une écriture
+binaire, et puisqu'il n'y a pas $2^{\gamma_i}$ dedans, elle est
+strictement plus petite que $\alpha$ (on rappelle que les écritures
+binaires des ordinaux se comparent lexicographiquement).  Ceci
+montre (1).
+
+Pour ce qui est de (2), considérons un ordinal $\alpha'<\alpha$, qui
+s'écrit donc en binaire comme une somme de la forme $2^{\gamma_1} +
+\cdots + 2^{\gamma_{i-1}} + 2^{\gamma''_1} + \cdots + 2^{\gamma''_s}$
+avec $\gamma_i > \gamma''_1 > \cdots > \gamma''_s$.  L'hypothèse
+d'induction permet de réécrire cette somme comme une somme de nim.
+Quitte à ajouter $2^{\gamma_{i+1}},\ldots,2^{\gamma_r}$ dans la somme
+et annuler les puissances de $2$ qui apparaissent deux fois, on voit
+qu'on peut écrire $\alpha'$ sous la forme $2^{\gamma_1} \oplus \cdots
+\oplus \beta_i \oplus \cdots \oplus 2^{\gamma_r}$ où $\beta_i$ est une
+somme de nim de puissances de $2$ toutes strictement plus petites
+que $2^{\gamma_i}$.  En utilisant de nouveau l'hypothèse d'induction,
+cette somme de nim est une somme usuelle, c'est-à-dire une écriture
+binaire, et $\beta_i < 2^{\gamma_i}$ puisqu'il n'y a pas de
+$2^{\gamma_i}$ dans l'écriture binaire en question.  Ceci prouve (2).
+\end{proof}
+
+Récapitulons ce qu'on a montré :
+
+\begin{thm}
+La somme de nim d'ordinaux (définie
+en \ref{definition-nim-sum-of-ordinals}) peut se calculer en écrivant
+les ordinaux en question en binaire et en effectuant le \emph{ou
+  exclusif} de ces écritures binaires (c'est-à-dire que le coefficient
+devant chaque puissance de $2$ donnée vaut $1$ lorsque exactement l'un
+des coefficients des nombres ajoutés vaut $1$, et $0$ sinon).
+
+La fonction de Grundy de la somme de nim de jeux combinatoires
+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.
+\end{thm}
+\begin{proof}
+L'affirmation du premier paragraphe résulte
+de \ref{nim-sum-of-powers-of-two-is-ordinary-sum} et
+de \ref{nim-sum-has-characteristic-two} (ainsi que de la commutativité
+et l'associativité, \textit{ad lib.}) pour annuler les puissances
+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}).
+\end{proof}
+
 
 
 %