diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 24 |
1 files changed, 17 insertions, 7 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index b54d3a1..ad8edda 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -4965,11 +4965,11 @@ 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} +\begin{thm}\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} +\end{thm} \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 @@ -5021,9 +5021,9 @@ est différent de $\alpha_1 \oplus (\alpha_2\oplus\alpha_3)$. Les cas \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}. +l'observation que $(\alpha_1\oplus\alpha_2)\oplus\alpha_3 = +\gr(((*\alpha_1) \oplus (*\alpha_2)) \oplus (*\alpha_3))$ qui +utilise \ref{nim-sum-for-games-versus-ordinals}. \end{proof} \begin{prop}\label{nim-sum-has-characteristic-two} @@ -5054,7 +5054,7 @@ $\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} +\begin{proof}[Première démonstration] 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 @@ -5074,6 +5074,16 @@ 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{proof}[Seconde démonstration] +En appliquant \ref{nim-sum-for-games-versus-ordinals} (et une +récurrence immédiate sur $n$), on voit que +$\alpha_1\oplus\cdots\oplus\alpha_n = +\gr((*\alpha_1)\oplus\cdots\oplus(*\alpha_n))$. Or les positions de +$(*\alpha_1)\oplus\cdots\oplus(*\alpha_n)$ sont justement les +$(*\alpha_1)\oplus\cdots\oplus(*\beta_i)\oplus +\cdots\oplus(*\alpha_n)$ pour $\beta_i < \alpha_i$, et la conclusion +découle de la définition de $\gr$. +\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 @@ -5096,7 +5106,7 @@ un certain $\beta_i < 2^{\gamma_i}$. Pour ceci 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ù +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 |