diff options
| -rw-r--r-- | notes-mitro206.tex | 243 |
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} + + + % % % |