\documentclass[12pt,a4paper,notitlepage]{report}
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{ifthen}
\usepackage{chessboard}
\usepackage[top=2.5cm,bottom=2.5cm,left=2.5cm,
right=2.5cm]{geometry}
\author{Alain Busser\\IREMI 974}
\usepackage{tikz}
\usetikzlibrary{automata,shapes,arrows,shadings}
\tikzset{
v/.style={circle,draw,ultra thick,minimum width=1.4cm},
rouge/.style={->,>=stealth',ultra thick,color=red},
bleu/.style={->,>=stealth',ultra thick,color=blue}
}

\usepackage{comment}

\setcounter{chapter}{1}

\title{Construction du nombre par John Conway\\1. Entiers et fractions}
\begin{document}
\renewcommand{\labelitemi}{$\bullet$}
\renewcommand{\labelitemii}{$\circ$}

\maketitle
\vfill

\hfill
\includegraphics[scale=0.2]{LogoIREMI}

\newpage

%\begin{comment}




\section{Règle du jeu}
\subsection{Mouvements du pion}

On joue avec un pion sur un graphe orienté dont les arcs sont rouges ou bleus. Les joueurs s'appellent Bleu et Rouge. Chacun son tour déplace le pion en suivant un arc du graphe orienté, mais

\begin{itemize}
\item Bleu n'a pas le droit de glisser le pion le long d'un arc rouge.
\item Rouge n'a pas le droit de glisser le pion le long d'un arc bleu.
\item Les arcs sont à sens unique (montré par la flèche) et il est interdit de remonter un arc dans le sens inverse de la flèche. 
\end{itemize} 

Autrement dit, Rouge peut glisser le pion le long d'un arc rouge, et Bleu peut glisser le pion le long d'un arc bleu.

Un sommet peut très bien être accessible aux deux joueurs~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (c) at (-1,1) {};
\node[v,accepting] (d) at (1,1) {};
\draw[bend left,bleu] (c) to (d);
\draw[bend right,rouge] (c) to (d);
\end{tikzpicture}
\end{center}

\subsection{Fin de la partie}

Lorsque le joueur dont c'est le tour ne peut plus bouger le pion (parce que celui-ci est sur un sommet dont ne part aucun arc bleu alors que c'est à Bleu de jouer, ou sur un sommet dont ne part aucun arc rouge alors que c'est à Rouge de jouer), ce joueur a perdu. Le jeu s'arrête donc dès que le pion ne peut plus bouger. Typiquement cela arrive lorsque le pion est sur un sommet dont ne part aucun arc.

\subsection{Exemple}

\begin{center}
    \begin{tikzpicture}[scale=1.4]
        \node[v] (o) at (0,0){};
        \node[v] (a) at (90:2){$\BlackPawnOnWhite$};
        \node[v] (b) at (162:2){};
        \node[v,accepting] (c) at (234:2){};
        \node[v] (d) at (306:2){};
        \node[v] (e) at (18:2){};
        \draw[bleu] (a) to (b);
        \draw[bleu,bend left=15] (a) to (o);
        \draw[rouge,bend right=15] (a) to (o);
        \draw[rouge] (a) to (e);
        \draw[rouge] (b) to (o);
        \draw[rouge] (b) to (c);
        \draw[bleu] (o) to (c);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[rouge,bend right=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (e);
        \draw[rouge,bend right=15] (o) to (e);
        \draw[bleu] (e) to (d);
        \draw[bleu,bend left=15] (d) to (c);
        \draw[rouge,bend right=15] (d) to (c);
    \end{tikzpicture}
\end{center}

C'est à Bleu de jouer. Comme l'arc de droite est rouge, Bleu ne peut pas jouer cet arc. Bleu ne peut jouer que l'arc bleu de gauche ou celui du centre. Mais si Bleu joue l'arc bleu à gauche

\begin{center}
    \begin{tikzpicture}[scale=1.4]
        \node[v] (o) at (0,0){};
        \node[v] (a) at (90:2){};
        \node[v] (b) at (162:2){$\BlackPawnOnWhite$};
        \node[v,accepting] (c) at (234:2){};
        \node[v] (d) at (306:2){};
        \node[v] (e) at (18:2){};
        \draw[bleu] (a) to (b);
        \draw[bleu,bend left=15] (a) to (o);
        \draw[rouge,bend right=15] (a) to (o);
        \draw[rouge] (a) to (e);
        \draw[rouge] (b) to (o);
        \draw[rouge] (b) to (c);
        \draw[bleu] (o) to (c);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[rouge,bend right=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (e);
        \draw[rouge,bend right=15] (o) to (e);
        \draw[bleu] (e) to (d);
        \draw[bleu,bend left=15] (d) to (c);
        \draw[rouge,bend right=15] (d) to (c);
    \end{tikzpicture}
\end{center}

Rouge gagne juste après~:

\begin{center}
    \begin{tikzpicture}[scale=1.4]
        \node[v] (o) at (0,0){};
        \node[v] (a) at (90:2){};
        \node[v] (b) at (162:2){};
        \node[v,accepting] (c) at (234:2){$\BlackPawnOnWhite$};
        \node[v] (d) at (306:2){};
        \node[v] (e) at (18:2){};
        \draw[bleu] (a) to (b);
        \draw[bleu,bend left=15] (a) to (o);
        \draw[rouge,bend right=15] (a) to (o);
        \draw[rouge] (a) to (e);
        \draw[rouge] (b) to (o);
        \draw[rouge] (b) to (c);
        \draw[bleu] (o) to (c);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[rouge,bend right=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (e);
        \draw[rouge,bend right=15] (o) to (e);
        \draw[bleu] (e) to (d);
        \draw[bleu,bend left=15] (d) to (c);
        \draw[rouge,bend right=15] (d) to (c);
    \end{tikzpicture}
\end{center}
Bleu a donc tout intérêt à jouer l'arc bleu au centre~:

\begin{center}
    \begin{tikzpicture}[scale=1.4]
        \node[v] (o) at (0,0){$\BlackPawnOnWhite$};
        \node[v] (a) at (90:2){};
        \node[v] (b) at (162:2){};
        \node[v,accepting] (c) at (234:2){};
        \node[v] (d) at (306:2){};
        \node[v] (e) at (18:2){};
        \draw[bleu] (a) to (b);
        \draw[bleu,bend left=15] (a) to (o);
        \draw[rouge,bend right=15] (a) to (o);
        \draw[rouge] (a) to (e);
        \draw[rouge] (b) to (o);
        \draw[rouge] (b) to (c);
        \draw[bleu] (o) to (c);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[rouge,bend right=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (e);
        \draw[rouge,bend right=15] (o) to (e);
        \draw[bleu] (e) to (d);
        \draw[bleu,bend left=15] (d) to (c);
        \draw[rouge,bend right=15] (d) to (c);
    \end{tikzpicture}
\end{center}

C'est au tour de Rouge de jouer. Elle doit jouer un des deux arcs rouges partant de ce sommet. Pas celui du bas~:

\begin{center}
    \begin{tikzpicture}[scale=1.4]
        \node[v] (o) at (0,0){};
        \node[v] (a) at (90:2){};
        \node[v] (b) at (162:2){};
        \node[v,accepting] (c) at (234:2){};
        \node[v] (d) at (306:2){$\BlackPawnOnWhite$};
        \node[v] (e) at (18:2){};
        \draw[bleu] (a) to (b);
        \draw[bleu,bend left=15] (a) to (o);
        \draw[rouge,bend right=15] (a) to (o);
        \draw[rouge] (a) to (e);
        \draw[rouge] (b) to (o);
        \draw[rouge] (b) to (c);
        \draw[bleu] (o) to (c);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[rouge,bend right=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (e);
        \draw[rouge,bend right=15] (o) to (e);
        \draw[bleu] (e) to (d);
        \draw[bleu,bend left=15] (d) to (c);
        \draw[rouge,bend right=15] (d) to (c);
    \end{tikzpicture}
\end{center}

parce que dans ce cas, Bleu gagnerait au prochain coup. Elle choisit donc l'autre arc rouge~:

\begin{center}
    \begin{tikzpicture}[scale=1.4]
        \node[v] (o) at (0,0){};
        \node[v] (a) at (90:2){};
        \node[v] (b) at (162:2){};
        \node[v,accepting] (c) at (234:2){};
        \node[v] (d) at (306:2){};
        \node[v] (e) at (18:2){$\BlackPawnOnWhite$};
        \draw[bleu] (a) to (b);
        \draw[bleu,bend left=15] (a) to (o);
        \draw[rouge,bend right=15] (a) to (o);
        \draw[rouge] (a) to (e);
        \draw[rouge] (b) to (o);
        \draw[rouge] (b) to (c);
        \draw[bleu] (o) to (c);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[rouge,bend right=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (e);
        \draw[rouge,bend right=15] (o) to (e);
        \draw[bleu] (e) to (d);
        \draw[bleu,bend left=15] (d) to (c);
        \draw[rouge,bend right=15] (d) to (c);
    \end{tikzpicture}
\end{center}

C'est à Bleu de jouer maintenant. Il joue le seul arc qu'il peut jouer, qui est justement bleu~:

\begin{center}
    \begin{tikzpicture}[scale=1.4]
        \node[v] (o) at (0,0){};
        \node[v] (a) at (90:2){};
        \node[v] (b) at (162:2){};
        \node[v,accepting] (c) at (234:2){};
        \node[v] (d) at (306:2){$\BlackPawnOnWhite$};
        \node[v] (e) at (18:2){};
        \draw[bleu] (a) to (b);
        \draw[bleu,bend left=15] (a) to (o);
        \draw[rouge,bend right=15] (a) to (o);
        \draw[rouge] (a) to (e);
        \draw[rouge] (b) to (o);
        \draw[rouge] (b) to (c);
        \draw[bleu] (o) to (c);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[rouge,bend right=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (e);
        \draw[rouge,bend right=15] (o) to (e);
        \draw[bleu] (e) to (d);
        \draw[bleu,bend left=15] (d) to (c);
        \draw[rouge,bend right=15] (d) to (c);
    \end{tikzpicture}
\end{center}

C'est au tour de Rouge de jouer. Elle ne peut alors que glisser le pion sur le seul arc rouge qui sort de ce sommet~:

\begin{center}
    \begin{tikzpicture}[scale=1.4]
        \node[v] (o) at (0,0){};
        \node[v] (a) at (90:2){};
        \node[v] (b) at (162:2){};
        \node[v,accepting] (c) at (234:2){$\BlackPawnOnWhite$};
        \node[v] (d) at (306:2){};
        \node[v] (e) at (18:2){};
        \draw[bleu] (a) to (b);
        \draw[bleu,bend left=15] (a) to (o);
        \draw[rouge,bend right=15] (a) to (o);
        \draw[rouge] (a) to (e);
        \draw[rouge] (b) to (o);
        \draw[rouge] (b) to (c);
        \draw[bleu] (o) to (c);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[rouge,bend right=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (e);
        \draw[rouge,bend right=15] (o) to (e);
        \draw[bleu] (e) to (d);
        \draw[bleu,bend left=15] (d) to (c);
        \draw[rouge,bend right=15] (d) to (c);
    \end{tikzpicture}
\end{center}

Le pion ne peut plus bouger (il n'y a aucun arc qui part de ce sommet) donc Rouge, qui a effectué le dernier mouvement, a gagné ce jeu. La question est de savoir combien elle a gagné. Pour préciser cela, on introduit des nombres.


\section{Nombres entiers} 

On adopte (comme le faisait Conway) le point de vue de Bleu.



\subsection{Graphes orientés}

On appelle \emph{degré sortant} d'un sommet, le nombre d'arcs qui émanent de ce sommet. Les degrés sortants du graphe de l'exemple précédent sont~:

\begin{center}
    \begin{tikzpicture}[scale=1.4]
        \node[v] (o) at (0,0){5};
        \node[v] (a) at (90:2){4};
        \node[v] (b) at (162:2){2};
        \node[v,accepting] (c) at (234:2){0};
        \node[v] (d) at (306:2){2};
        \node[v] (e) at (18:2){1};
        \draw[bleu] (a) to (b);
        \draw[bleu,bend left=15] (a) to (o);
        \draw[rouge,bend right=15] (a) to (o);
        \draw[rouge] (a) to (e);
        \draw[rouge] (b) to (o);
        \draw[rouge] (b) to (c);
        \draw[bleu] (o) to (c);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[rouge,bend right=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (e);
        \draw[rouge,bend right=15] (o) to (e);
        \draw[bleu] (e) to (d);
        \draw[bleu,bend left=15] (d) to (c);
        \draw[rouge,bend right=15] (d) to (c);
    \end{tikzpicture}
\end{center}

On remarque que le sommet de degré sortant 0 est marqué d'un double trait circulaire. Cette convention\footnote{Proposée par Ivan Riou de l'IREM de Mayotte} sera utilisée dans tout l'article même s'il y a plusieurs tels sommets. 

On appelle \emph{degré entrant} d'un sommet, le nombre d'arcs qui arrivent à ce sommet. Les degrés entrants du graphe précédent sont~:


\begin{center}
    \begin{tikzpicture}[scale=1.4]
        \node[v] (o) at (0,0){3};
        \node[v] (a) at (90:2){0};
        \node[v] (b) at (162:2){1};
        \node[v,accepting] (c) at (234:2){4};
        \node[v] (d) at (306:2){3};
        \node[v] (e) at (18:2){3};
        \draw[bleu] (a) to (b);
        \draw[bleu,bend left=15] (a) to (o);
        \draw[rouge,bend right=15] (a) to (o);
        \draw[rouge] (a) to (e);
        \draw[rouge] (b) to (o);
        \draw[rouge] (b) to (c);
        \draw[bleu] (o) to (c);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[rouge,bend right=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (d);
        \draw[bleu,bend left=15] (o) to (e);
        \draw[rouge,bend right=15] (o) to (e);
        \draw[bleu] (e) to (d);
        \draw[bleu,bend left=15] (d) to (c);
        \draw[rouge,bend right=15] (d) to (c);
    \end{tikzpicture}
\end{center}


Un sommet de degré sortant nul est un \emph{puits} (ou une \emph{arrivée}). Un sommet de degré entrant nul est une \emph{source} (ou \emph{départ}). Pour un jeu combinatoire on n'a qu'un seul départ, c'est là où on pose le pion avant de jouer. Par contre on peut avoir plusieurs arrivées. Une stratégie gagnante peut alors consister à guider le pion vers une arrivée gagnante.







\section{La construction de Conway}

Les premiers jeux définis par Conway ressemblent à ceci~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (a) at (-3,1) {$\BlackPawnOnWhite$};
\node[v] (b) at (-4,0) {};
\node[v] (b1) at (-4,-1) {};
\node[v,accepting] (b2) at (-4,0-2) {};
\node[v] (c) at (-2,0) {};
\node[v] (c1) at (-2,-1) {};
\node[v] (c2) at (-2,-2) {};
\node[v,accepting] (c3) at (-2,-3) {};
\draw[bleu] (a) to (b);
\draw[rouge] (a) to (c);
\node[v] (d) at (0,1) {$\BlackPawnOnWhite$};
\node[v] (e) at (-1,0) {};
\node[v] (e1) at (-1,-1) {};
\node[v,accepting] (e2) at (-1,-2) {};
\node[v] (f) at (1,0) {};
\node[v] (f1) at (1,-1) {};
\node[v] (f2) at (1,-2) {};
\node[v,accepting] (f3) at (1,-3) {};
\draw[bleu] (d) to (e);
\draw[rouge] (d) to (f);
\draw[rouge] (b) to (b1);
\draw[rouge] (b1) to (b2);
\draw[bleu] (c) to (c1);
\draw[bleu] (c1) to (c2);
\draw[bleu] (c2) to (c3);
\draw[bleu] (e) to (e1);
\draw[bleu] (e1) to (e2);
\draw[bleu] (f) to (f1);
\draw[bleu] (f1) to (f2);
\draw[bleu] (f2) to (f3);
\end{tikzpicture}
\end{center}

Les deux jeux ci-dessus sont des nombres (respectivement 0 et 2,5), mais certains jeux de ce genre ne sont pas des nombres.

Voici comment Conway construit les nombres, dans l'ordre de complexité croissante.

\subsection{Le nombre zéro}

Le jeu le plus simple est le nombre 0 (le prochain qui joue a perdu). C'est juste \tikz{\node[v,accepting] at (0,0) {$\BlackPawnOnWhite$};} et c'est un jeu juste car il est équitable.

\subsection{Le nombre un}

Ce jeu vaut 1~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v,accepting] (a) at (1,0) {}; 
\draw[bleu] (o) to (a);
\end{tikzpicture}
\end{center}

\subsection{Le nombre -1}

Ce jeu vaut -1~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v,accepting] (a) at (1,0) {}; 
\draw[rouge] (o) to (a);
\end{tikzpicture}
\end{center}

L'opposé d'un nombre est ce qu'on obtient en intervertissant les rôles des deux joueurs. Ainsi, le jeu -1 est à l'avantage de Rouge comme le jeu 1 est à l'avantage de Bleu.

Ce jeu n'est pas un nombre~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v,accepting] (a) at (1,0) {}; 
\node[v,accepting] (b) at (-1,0) {}; 
\draw[rouge] (o) to (a);
\draw[bleu] (o) to (b);
\end{tikzpicture}
\end{center}

Conway l'appelle \emph{étoile} et c'est un jeu plutôt équitable puisque le prochain joueur, quelle que soit sa couleur, gagne ce jeu. Mais beaucoup de jeux sont des nombres, par exemple

\subsection{Le nombre 2}

Ce jeu vaut 2~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (a) at (1,0) {}; 
\node[v,accepting] (b) at (2,0) {}; 
\draw[bleu] (o) to (a);
\draw[bleu] (a) to (b);
\end{tikzpicture}
\end{center}

Comme Bleu est censé jouer au mieux de ses intérêts, ce jeu aussi vaut 2~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (a) at (1,0) {}; 
\node[v,accepting] (a1) at (2,0) {}; 
\node[v] (b) at (-1,0) {}; 
\node[v] (b1) at (-2,0) {}; 
\node[v] (b2) at (-3,0) {}; 
\node[v,accepting] (b3) at (-4,0) {}; 
\draw[bleu] (o) to (a);
\draw[bleu] (o) to (b);
\draw[bleu] (a) to (a1);
\draw[rouge] (b) to (b1);
\draw[rouge] (b1) to (b2);
\draw[rouge] (b2) to (b3);
\end{tikzpicture}
\end{center}

\subsection{Le nombre 3}

Ce jeu vaut 3~:


\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (a) at (1,0) {}; 
\node[v] (b) at (2,0) {}; 
\node[v,accepting] (c) at (3,0) {}; 
\draw[bleu] (o) to (a);
\draw[bleu] (a) to (b);
\draw[bleu] (b) to (c);
\end{tikzpicture}
\end{center}

\subsection{Le nombre 4}

Ce jeu vaut 4~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (a) at (1,0) {}; 
\node[v] (b) at (2,0) {}; 
\node[v] (c) at (3,0) {}; 
\node[v,accepting] (d) at (4,0) {}; 
\draw[bleu] (o) to (a);
\draw[bleu] (a) to (b);
\draw[bleu] (b) to (c);
\draw[bleu] (c) to (d);
\end{tikzpicture}
\end{center}

Tous les entiers (positifs ou négatifs) peuvent être représentés par des jeux, par exemple l'entier -3~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (a) at (1,0) {}; 
\node[v] (b) at (2,0) {}; 
\node[v,accepting] (c) at (3,0) {}; 
\draw[rouge] (o) to (a);
\draw[rouge] (a) to (b);
\draw[rouge] (b) to (c);
\end{tikzpicture}
\end{center}
\subsection{Des fractions}

Le nombre \emph{un demi} (pour comprendre d'où vient cette valeur, voir plus bas l'addition)~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v,accepting] (a) at (-1,-1) {}; 
\node[v] (b) at (1,-1) {}; 
\node[v,accepting] (b1) at (2,-1) {}; 
\draw[bleu] (o) to (a);
\draw[rouge] (o) to (b);
\draw[bleu] (b) to (b1);
\end{tikzpicture}
\end{center}

ou alors cette variante~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v,accepting] (a) at (-1,-1) {}; 
\node[v] (b) at (1,-1) {}; 
\draw[bleu] (o) to (a);
\draw[rouge] (o) to (b);
\draw[bleu] (b) to (a);
\end{tikzpicture}
\end{center}



Le nombre \emph{un et demie}~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (a) at (-1,-1) {}; 
\node[v,accepting] (a1) at (-2,-1) {}; 
\node[v] (b) at (1,-1) {}; 
\node[v] (b1) at (2,-1) {}; 
\node[v,accepting] (b2) at (3,-1) {}; 
\draw[bleu] (o) to (a);
\draw[rouge] (o) to (b);
\draw[bleu] (a) to (a1);
\draw[bleu] (b) to (b1);
\draw[bleu] (b1) to (b2);
\end{tikzpicture}
\end{center}

Le nombre \emph{deux et demie}~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (a) at (-1,-1) {}; 
\node[v] (a1) at (-2,-1) {}; 
\node[v,accepting] (a2) at (-3,-1) {}; 
\node[v] (b) at (1,-1) {}; 
\node[v] (b1) at (2,-1) {}; 
\node[v] (b2) at (3,-1) {}; 
\node[v,accepting] (b3) at (4,-1) {}; 
\draw[bleu] (o) to (a);
\draw[rouge] (o) to (b);
\draw[bleu] (a) to (a1);
\draw[bleu] (a1) to (a2);
\draw[bleu] (b) to (b1);
\draw[bleu] (b1) to (b2);
\draw[bleu] (b2) to (b3);
\end{tikzpicture}
\end{center}


Le nombre \emph{un quart}~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (z) at (-1,1) {$\BlackPawnOnWhite$};
\node[v,accepting] (y) at (-2,0) {};
\node[v] (o) at (0,0) {};
\node[v,accepting] (a) at (-1,-1) {}; 
\node[v] (b) at (1,-1) {}; 
\node[v,accepting] (b1) at (2,-1) {}; 
\draw[bleu] (o) to (a);
\draw[rouge] (o) to (b);
\draw[rouge] (z) to (o);
\draw[bleu] (z) to (y);
\draw[bleu] (b) to (b1);
\end{tikzpicture}
\end{center}

ou cette variante~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (z) at (-1,1) {$\BlackPawnOnWhite$};
\node[v,accepting] (y) at (-2,0) {};
\node[v] (o) at (0,0) {};
\node[v] (b) at (-1,-1) {}; 
\draw[bleu] (o) to (y);
\draw[rouge] (o) to (b);
\draw[rouge] (z) to (o);
\draw[bleu] (z) to (y);
\draw[bleu] (b) to (y);
\end{tikzpicture}
\end{center}



Le nombre \emph{trois quarts}~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (z) at (1,1) {$\BlackPawnOnWhite$};
\node[v] (y) at (2,0) {};
\node[v,accepting] (y1) at (3,0) {};
\node[v] (o) at (0,0) {};
\node[v,accepting] (a) at (-1,-1) {}; 
\node[v] (b) at (1,-1) {}; 
\node[v,accepting] (b1) at (2,-1) {}; 
\draw[bleu] (o) to (a);
\draw[rouge] (o) to (b);
\draw[bleu] (z) to (o);
\draw[rouge] (z) to (y);
\draw[bleu] (y) to (y1);
\draw[bleu] (b) to (b1);
\end{tikzpicture}
\end{center}

ou encore~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (z) at (1,1) {$\BlackPawnOnWhite$};
\node[v] (y) at (2,0) {};
\node[v,accepting] (x) at (3,-1) {};
\node[v] (o) at (0,0) {};
\node[v,accepting] (a) at (-1,-1) {}; 
\node[v] (b) at (1,-1) {}; 
\draw[bleu] (o) to (a);
\draw[rouge] (o) to (b);
\draw[bleu] (z) to (o);
\draw[rouge] (z) to (y);
\draw[bleu] (y) to (x);
\draw[bleu] (b) to (x);
\end{tikzpicture}
\end{center}

Le nombre \emph{trois huitièmes}~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (-1,1) {$\BlackPawnOnWhite$};
\node[v] (a) at (-1,-1) {}; 
\node[v] (b) at (0,0) {}; 
\node[v] (c) at (1,1) {}; 
\node[v,accepting] (d) at (1,-1) {};
\draw[bleu] (o) to (a);
\draw[rouge] (o) to (b);
\draw[rouge] (a) to (b);
\draw[rouge] (b) to (c);
\draw[bleu] (a) to (d);
\draw[bleu] (b) to (d);
\draw[bleu] (c) to (d);
\end{tikzpicture}
\end{center}

Les informaticiens s'intéressent à la construction des nombres par Conway parce que, comme on le voit sur les exemples ci-dessus, les nombres qu'on peut représenter par des graphes finis sont les \emph{fractions dyadiques} c'est-à-dire les fractions dont le dénominateur est 2, 4, 8, 16 etc.
\section{Addition}

\subsection{Calcul du départ}

Pour montrer que le jeu ci-dessus est $\frac{3}{8}$ on commence par calculer l'arrivée~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (-1,1) {};
\node[v] (a) at (-1,-1) {}; 
\node[v] (b) at (0,0) {}; 
\node[v] (c) at (1,1) {}; 
\node[v,accepting] (d) at (1,-1) {$\BlackPawnOnWhite$};
\draw[bleu] (o) to (a);
\draw[rouge] (o) to (b);
\draw[rouge] (a) to (b);
\draw[rouge] (b) to (c);
\draw[bleu] (a) to (d);
\draw[bleu] (b) to (d);
\draw[bleu] (c) to (d);
\end{tikzpicture}
\end{center}

Comme aucun arc n'émane de l'arrivée, le jeu formé par l'arrivée seule est égal à 0 (le prochain joueur perd ce jeu). Ce qui permet de vérifier que le jeu ci-dessous est égal à 1~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (-1,1) {};
\node[v] (a) at (-1,-1) {}; 
\node[v] (b) at (0,0) {}; 
\node[v] (c) at (1,1) {$\BlackPawnOnWhite$}; 
\node[v,accepting] (d) at (1,-1) {0};
\draw[bleu] (o) to (a);
\draw[rouge] (o) to (b);
\draw[rouge] (a) to (b);
\draw[rouge] (b) to (c);
\draw[bleu] (a) to (d);
\draw[bleu] (b) to (d);
\draw[bleu] (c) to (d);
\end{tikzpicture}
\end{center}

En effet, comme le pion ne peut pas remonter les flèches, c'est comme s'il n'y avait que les deux sommets à droite, et on y reconnaît le nombre 1 tel qu'il est défini.

Mais du coup on reconnaît le nombre 0,5 au centre du graphe, puisque Bleu va vers un sommet vide et Rouge va vers un sommet de valeur 1~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (-1,1) {};
\node[v] (a) at (-1,-1) {}; 
\node[v] (b) at (0,0) {$\BlackPawnOnWhite$}; 
\node[v] (c) at (1,1) {1}; 
\node[v,accepting] (d) at (1,-1) {0};
\draw[bleu] (o) to (a);
\draw[rouge] (o) to (b);
\draw[rouge] (a) to (b);
\draw[rouge] (b) to (c);
\draw[bleu] (a) to (d);
\draw[bleu] (b) to (d);
\draw[bleu] (c) to (d);
\end{tikzpicture}
\end{center}

Ce qui permet alors de calculer ce jeu (qui est un graphe à 4 sommets)~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (-1,1) {};
\node[v] (a) at (-1,-1) {$\BlackPawnOnWhite$}; 
\node[v] (b) at (0,0) {$\frac{1}{2}$}; 
\node[v] (c) at (1,1) {1}; 
\node[v,accepting] (d) at (1,-1) {0};
\draw[bleu] (o) to (a);
\draw[rouge] (o) to (b);
\draw[rouge] (a) to (b);
\draw[rouge] (b) to (c);
\draw[bleu] (a) to (d);
\draw[bleu] (b) to (d);
\draw[bleu] (c) to (d);
\end{tikzpicture}
\end{center}

En effet on voit que Bleu a accès à zéro alors que Rouge a accès à 0,5~: on reconnaît la définition de 0,25~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (-1,1) {$\BlackPawnOnWhite$};
\node[v] (a) at (-1,-1) {$\frac{1}{4}$}; 
\node[v] (b) at (0,0) {$\frac{1}{2}$}; 
\node[v] (c) at (1,1) {1}; 
\node[v,accepting] (d) at (1,-1) {0};
\draw[bleu] (o) to (a);
\draw[rouge] (o) to (b);
\draw[rouge] (a) to (b);
\draw[rouge] (b) to (c);
\draw[bleu] (a) to (d);
\draw[bleu] (b) to (d);
\draw[bleu] (c) to (d);
\end{tikzpicture}
\end{center}

L'issue de Bleu est $\frac{1}{4}$ et l'issue de Rouge est $\frac{1}{2}$ donc la valeur du jeu (nombre le plus simple possible entre 0,5 et 0,25) est bien $0,375=\frac{3}{8}$.

Ainsi, si un jeu est un nombre, c'est souvent parce que les jeux obtenus en plaçant le pion ailleurs qu'au départ avant de jouer sont aussi des nombres. On peut alors voir chaque sommet du graphe comme un nombre (celui du jeu qu'on obtiendrait en enlevant les sommets qui sont avant ce sommet). C'est de cette constatation que vient la notion de somme de jeux.

\subsection{Addition des jeux}

On additionne des nombres (et plus généralement des jeux) en plaçant plusieurs pions sur le graphe. Par exemple ce jeu

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (-1,1) {$\BlackPawnOnWhite$};
\node[v] (a) at (-1,-1) {$\BlackPawnOnWhite$}; 
\node[v] (b) at (0,0) {}; 
\node[v] (c) at (1,1) {}; 
\node[v,accepting] (d) at (1,-1) {};
\draw[bleu] (o) to (a);
\draw[rouge] (o) to (b);
\draw[rouge] (a) to (b);
\draw[rouge] (b) to (c);
\draw[bleu] (a) to (d);
\draw[bleu] (b) to (d);
\draw[bleu] (c) to (d);
\end{tikzpicture}
\end{center}

est égal à 0,625~: un pion est sur le départ de valeur 0,375 et l'autre est sur un sommet de valeur 0,25 et 0,375+0,25~=~0,625.

Ce jeu est terminé lorsque les deux pions sont à l'arrivée.

\subsection{Addition des entiers naturels}

Ce jeu, de valeur 5, illustre que 3+2=5~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (0,1) {$\BlackPawnOnWhite$};
\node[v] (b) at (1,1) {};
\node[v] (c) at (2,1) {};
%\node[v] (d) at (3,1) {};
\node[v] (e) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (f) at (1,0) {};
\node[v,accepting] (g) at (2,0) {};
\draw[bleu] (a) to (b);
\draw[bleu] (b) to (c);
\draw[bleu] (c) to (g);
\draw[bleu] (e) to (f);
\draw[bleu] (f) to (g);
\end{tikzpicture}
\end{center}

Le pion du haut peut bouger 3 fois sur des arcs bleus et le pion du bas peut jouer 2 fois sur des arcs bleus, donc ils représentent des jeux de valeurs respectives 3 et 2. Et Bleu peut au total avancer 5 fois le pion tandis que Rouge s'ennuie à le regarder avancer ce pion.

Le jeu ci-dessus est le même que celui-ci~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (0,1) {$\BlackPawnOnWhite$};
\node[v] (b) at (1,1) {$\BlackPawnOnWhite$};
\node[v] (c) at (2,1) {};
%\node[v] (d) at (3,1) {};
\node[v] (e) at (0,0) {};
\node[v] (f) at (1,0) {};
\node[v,accepting] (g) at (2,0) {};
\draw[bleu] (a) to (b);
\draw[bleu] (b) to (c);
\draw[bleu] (c) to (g);
\draw[bleu] (e) to (f);
\draw[bleu] (f) to (g);
\end{tikzpicture}
\end{center}

ou celui-ci~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (0,1) {$\BlackPawnOnWhite$};
\node[v] (b) at (1,1) {$\BlackPawnOnWhite$};
\node[v] (c) at (2,1) {};
%\node[v] (d) at (3,1) {};
\node[v,accepting] (g) at (2,0) {};
\draw[bleu] (a) to (b);
\draw[bleu] (b) to (c);
\draw[bleu] (c) to (g);
\end{tikzpicture}
\end{center}





\subsection{Addition des entiers relatifs}

Ce jeu, de valeur 1, illustre que 3+(-2)=1~:

\begin{center}
\begin{tikzpicture}[scale=3]
\node[v] (a) at (0,1) {$\BlackPawnOnWhite$};
\node[v] (b) at (1,1) {};
\node[v] (c) at (2,1) {};
%\node[v] (d) at (3,1) {};
\node[v] (e) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (f) at (1,0) {};
\node[v,accepting] (g) at (2,0) {};
\draw[bleu] (a) to (b);
\draw[bleu] (b) to (c);
\draw[bleu] (c) to (g);
\draw[rouge] (e) to (f);
\draw[rouge] (f) to (g);
\end{tikzpicture}
\end{center}

En effet Bleu peut avancer le pion du haut 3 fois de suite alors que Rouge ne peut avancer le pion du bas que 2 fois. Donc Bleu qui peut continuer à jouer plus longtemps, gagne ce jeu, qu'il joue en premier ou en second.

Remarques~:

\begin{itemize}
\item Beaucoup d'enfants croient au contraire que c'est Rouge qui gagne ce jeu (à la course). Il faut leur expliquer que ce genre de jeu n'est pas similaire au jeu de l'oie (où celui qui va plus vite, va plus loin, ce qui n'est pas le cas ici).
\item L'addition 3+(-2) ci-dessus revient à la soustraction 3-2. Conway modélise donc également la soustraction des entiers (et de tous les jeux possédant un opposé).
\end{itemize}

\subsection{Incrémentation et décrémentation}

On peut voir la construction qui, à partir d'un entier, donne l'entier suivant. On passe d'un entier à son successeur en additionnant 1. Pour le successeur de 4~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (a) at (1,0) {}; 
\node[v] (b) at (2,0) {}; 
\node[v] (c) at (3,0) {}; 
\node[v,accepting] (d) at (4,0) {}; 
\draw[bleu] (o) to (a);
\draw[bleu] (a) to (b);
\draw[bleu] (b) to (c);
\draw[bleu] (c) to (d);
\end{tikzpicture}
\end{center}

on a~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (a) at (1,0) {}; 
\node[v] (b) at (2,0) {}; 
\node[v] (c) at (3,0) {}; 
\node[v,accepting] (d) at (4,0) {}; 
\node[v] (e) at (4,-1) {$\BlackPawnOnWhite$};
\draw[bleu] (o) to (a);
\draw[bleu] (a) to (b);
\draw[bleu] (b) to (c);
\draw[bleu] (c) to (d);
\draw[bleu] (e) to (d);
\end{tikzpicture}
\end{center}

ou

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {};
\node[v] (a) at (1,0) {}; 
\node[v] (b) at (2,0) {}; 
\node[v] (c) at (3,0) {}; 
\node[v,accepting] (d) at (4,0) {}; 
\node[v] (e) at (-1,0) {$\BlackPawnOnWhite$}; 
\draw[bleu] (o) to (a);
\draw[bleu] (a) to (b);
\draw[bleu] (b) to (c);
\draw[bleu] (c) to (d);
\draw[bleu] (e) to (o);
\end{tikzpicture}
\end{center}

obtenu en déplaçant le nouvel arc bleu à l'autre bout et en enlevant le pion supplémentaire, puis replaçant l'ancien pion tout à gauche (déplacement vers la gauche d'un cran).

Cette construction fonctionne avec tout entier naturel, y compris 0~: elle donne immédiatement que le successeur de 0 est 1. Par contre avec un nombre négatif il faut neutraliser l'un des arcs rouges par l'arc bleu qu'on vient de rajouter. De même, pour obtenir le prédécesseur d'un entier naturel, on neutralise un des arcs bleus par l'arc rouge. Par exemple pour construire le prédécesseur de 4~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (a) at (1,0) {}; 
\node[v] (b) at (2,0) {}; 
\node[v] (c) at (3,0) {}; 
\node[v,accepting] (d) at (4,0) {}; 
\draw[bleu] (o) to (a);
\draw[bleu] (a) to (b);
\draw[bleu] (b) to (c);
\draw[bleu] (c) to (d);
\end{tikzpicture}
\end{center}

on a

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (a) at (1,0) {}; 
\node[v] (b) at (2,0) {}; 
\node[v] (c) at (3,0) {}; 
\node[v,accepting] (d) at (4,0) {}; 
\node[v] (e) at (4,-1) {$\BlackPawnOnWhite$};
\draw[bleu] (o) to (a);
\draw[bleu] (a) to (b);
\draw[bleu] (b) to (c);
\draw[bleu] (c) to (d);
\draw[rouge] (e) to (d);
\end{tikzpicture}
\end{center}

L'arc rouge neutralise l'arc bleu de gauche, avec suppression du nouveau pion et déplacement de l'ancien vers la droite~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v] (o) at (0,0) {$\BlackPawnOnWhite$};
\node[v] (a) at (1,0) {}; 
\node[v] (b) at (2,0) {}; 
\node[v,accepting] (c) at (3,0) {}; 
\draw[bleu] (o) to (a);
\draw[bleu] (a) to (b);
\draw[bleu] (b) to (c);
\end{tikzpicture}
\end{center}

Cette construction donne que le prédécesseur de 1 est 0 et que le prédécesseur de 0 est -1.

\subsection{Addition des fractions}

Ce jeu est le nombre zéro~:

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v,accepting] (o) at (0,0) {};
\node[v] (a) at (2,0) {}; 
\node[v] (b) at (1,1) {$\BlackPawnOnWhite$}; 
\node[v] (c) at (1,-1) {$\BlackPawnOnWhite$}; 
\node[v] (d) at (-2,0) {$\BlackPawnOnWhite$};
\draw[bleu] (a) to (o);
\draw[bleu] (b) to (o);
\draw[bleu] (c) to (o);
\draw[rouge] (b) to (a);
\draw[rouge] (c) to (a);
\draw[rouge] (d) to (o);
\end{tikzpicture}
\end{center}

En effet il est facile de voir que si Bleu commence, Rouge gagne et si Rouge commence, Bleu gagne.

Mais le jeu ci-dessus est la somme de -1 (à gauche) et du jeu

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v,accepting] (o) at (0,0) {};
\node[v] (a) at (2,0) {}; 
\node[v] (b) at (1,1) {$\BlackPawnOnWhite$}; 
\node[v] (c) at (1,-1) {$\BlackPawnOnWhite$}; 
\draw[bleu] (a) to (o);
\draw[bleu] (b) to (o);
\draw[bleu] (c) to (o);
\draw[rouge] (b) to (a);
\draw[rouge] (c) to (a);
\end{tikzpicture}
\end{center}

Puisqu'en soustrayant 1 au jeu ci-dessus, on a zéro, cela signifie que le jeu ci-dessus est égal à 1. Mais il est lui-même la somme de

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v,accepting] (o) at (0,0) {};
\node[v] (a) at (2,0) {}; 
\node[v] (b) at (1,1) {$\BlackPawnOnWhite$}; 
\draw[bleu] (a) to (o);
\draw[bleu] (b) to (o);
\draw[rouge] (b) to (a);
\end{tikzpicture}
\end{center}

et

\begin{center}
\begin{tikzpicture}[scale=2]
\node[v,accepting] (o) at (0,0) {};
\node[v] (a) at (2,0) {}; 
\node[v] (c) at (1,-1) {$\BlackPawnOnWhite$}; 
\draw[bleu] (a) to (o);
\draw[bleu] (c) to (o);
\draw[rouge] (c) to (a);
\end{tikzpicture}
\end{center}

qui valent chacun 0,5. Ce qui veut dire que 0,5+0,5=1 (ou plutôt $\frac{1}{2}+\frac{1}{2}=1$).


\end{document}

