summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-mitro206.tex84
1 files changed, 76 insertions, 8 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index b3df179..b013023 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1009,11 +1009,11 @@ parfaite, dont le modèle est décrit en \ref{introduction-graph-game}
(cf. \ref{introduction-nim-game}) ou le Hackenbush impartial (=vert)
(cf. \ref{introduction-hackenbush}).
-On parlera ensuite des jeux \emph{partiaux} à information parfaite,
-dont l'archétype est le Hackenbush bicolore ou tricolore, et de la
-théorie des nombres de Conway.
-
-Enfin, on évoquera quelques jeux en vrac et des liens avec la logique.
+On parlera ensuite rapidement dans la
+partie \ref{section-combinatorial-partizan-games} des jeux
+\emph{partisans} à information parfaite, dont l'archétype est le
+Hackenbush bicolore ou tricolore, et de la théorie des nombres
+surréels de Conway.
%
@@ -5159,7 +5159,7 @@ $2^{\gamma_i}$ dans l'écriture binaire en question. Ceci prouve (2).
Récapitulons ce qu'on a montré :
-\begin{thm}
+\begin{thm}\label{summary-of-grundy-theory}
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
@@ -5280,8 +5280,8 @@ est nulle (et notamment que ces jeux ont la propriété qu'on peut les
ignorer dans une somme de nim).
On définit aussi $G \geq 0$ (le jeu est alors qualifié de positif)
-lorsque $G > 0$ ou bien $G = 0$ : concrètement, cela signifie donc que
-Blaise a une stratégie gagnante à condition qu'il joue en
+lorsque $G > 0$ ou bien $G \doteq 0$ : concrètement, cela signifie
+donc que Blaise a une stratégie gagnante à condition qu'il joue en
\emph{second}. De même, $G \leq 0$ signifie que Roxane a une
stratégie gagnante à condition qu'elle joue en second. On note
parfois $G \vartriangleleft 0$ pour dire que $G<0$ ou bien $G\fuzzy 0$
@@ -5434,6 +5434,37 @@ $\doteq$ près), et comme $G + (-G) \doteq 0$, on a bien l'existence
d'un symétrique.
\end{proof}
+\thingy La théorie des jeux combinatoires partisans bien-fondés
+développée par John H. Conway s'intéresse essentiellement aux jeux
+\emph{modulo} la relation $\doteq$. C'est-à-dire, aux propriétés des
+jeux ou opérations dessus qui sont préservées par cette relation
+d'équivalence : comme on vient de le voir, le « signe » du jeu, ou la
+somme disjonctive en sont ; un exemple d'une opération qui \emph{n'est
+ pas} compatible à $\doteq$ est l'« impartialisation » du jeu définie
+en \ref{partizan-games-as-impartial-games} ci-dessous, ou une
+opération plus simple consistant à rendre vertes toutes les arêtes du
+jeu — il n'est pas difficile de trouver des exemples de jeux tels que
+$G \doteq G'$ mais que cette relation ne vaille plus après
+l'opération.
+
+On peut appeler \defin[valeur (d'un jeu combinatoire parisan)]{valeur}
+d'un jeu $G$ la classe de $G$ pour la relation $\doteq$. La
+proposition ci-dessus affirme donc que les \emph{valeurs} des jeux
+combinatoires partisans bien-fondés forment un groupe abélien
+partiellement ordonné. Cette notion de valeur peut être considérée
+comme une généralisation de la fonction de Grundy (puisque
+d'après \ref{summary-of-grundy-theory}, pour deux jeux impartiaux
+$H,H'$, la relation $H\doteq H'$ équivaut à $H \oplus H' \doteq 0$
+c'est-à-dire $\gr(H\oplus H') = 0$ c'est-à-dire $\gr(H) \oplus \gr(H')
+= 0$, c'est-à-dire $\gr(H) = \gr(H')$), et les \emph{nimbres} peuvent
+être considérés comme les valeurs particulières des jeux impartiaux
+(sur lesquelles la loi de groupe est le « ou exclusif » des
+représentations binaires). La structure du groupe des valeurs des
+jeux combinatoires partisans (bien-fondés) généraux est cependant
+beaucoup plus difficile à comprendre. Les \emph{nombres surréels}
+évoqués en \ref{subsection-surreal-numbers} permettent d'éclaircir un
+petit peu cette structure.
+
\subsection{Lien entre jeux partisans et jeux impartiaux}
@@ -5582,6 +5613,43 @@ Les autres cas sont analogues.
\end{proof}
+\subsection{Les nombres surréels (une esquisse)}\label{subsection-surreal-numbers}
+
+\thingy Parmi les jeux combinatoires partisans (ou leurs valeurs,
+c'est-à-dire ces mêmes jeux vus modulo $\doteq$), il en est de
+particulièrement importants qui sont appelés « nombres surréels » (ou
+simplement « nombres ») : ils sont \emph{totalement} ordonnés (entre
+deux nombres surréels $x,x'$, on peut avoir $x<x'$ ou $x\doteq x'$ ou
+$x>x'$ mais jamais $x\fuzzy x'$), ils forment eux aussi un groupe
+abélien (et même un corps !), et on peut s'en servir pour comparer les
+jeux combinatoires partisans (bien-fondés) généraux.
+
+Les nombres surréels sont par ailleurs remarquables en ce qu'ils
+généralisent \emph{à la fois} les ordinaux et les nombres réels (et
+contiennent des éléments surprenants comme $\omega-42$ ou
+$\omega+\sqrt{2}$ ou $2\pi\omega$ ou $1/\omega$ ou $\sqrt{\omega}$).
+
+\begin{defin}
+Soit $\alpha$ un ordinal et $\sigma\colon\{\beta : \beta<\alpha\} \to
+\{+1,-1\}$ une fonction quelconque définie sur les ordinaux $<\alpha$
+et à valeurs dans $\{+1,-1\}$ (on dira que $\sigma$ est une
+\defin{suite de signes}). Le \index{surréel (nombre)}\defin{nombre
+ surréel} associé à ces données est le jeu combinatoire partisan
+bien-fondé dont
+\begin{itemize}
+\item l'ensemble des positions est l'ensemble des ordinaux $\beta \leq
+ \alpha$,
+\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$,
+\item l'arête $(\beta,\beta')$ est colorée en bleu si $\sigma(\beta')
+ = +1$ et el rouge si $\sigma(\beta') = -1$, et
+\item la position initiale est $\alpha$.
+\end{itemize}
+\end{defin}
+
+
+
%