summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-04-11 12:10:53 +0200
committerDavid A. Madore <david+git@madore.org>2016-04-11 12:10:53 +0200
commit6a14a27736d556adc96a2b26f1ba30cd420b0b47 (patch)
treeed9cc32f998951b168415243ca0f663ba01aa0f8 /notes-mitro206.tex
parentfbd670b7ae91d864109059e461e5465fd92cb0d5 (diff)
downloadmitro206-6a14a27736d556adc96a2b26f1ba30cd420b0b47.tar.gz
mitro206-6a14a27736d556adc96a2b26f1ba30cd420b0b47.tar.bz2
mitro206-6a14a27736d556adc96a2b26f1ba30cd420b0b47.zip
Various additions or clarifications after course on 2016-04-11.
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex24
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