diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 132 |
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} + % |