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