Copy exercises from last year's exam to course notes.

1 files changed, 487 insertions, 1 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 4679aef..1fb8099 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -6505,6 +6505,189 @@ $0$&$\frac{5}{7}$&$\frac{2}{7}$&$0$&$\frac{3}{7}$&$\frac{4}{7}$&$4+\frac{6}{7}$\
 et on a prouvé que c'étaient bien les seuls.
 \end{corrige}
 
+
+%
+%
+%
+
+\exercice\label{three-player-game-exercise}
+
+On considère le jeu en forme normale suivant : \emph{trois} joueurs
+(Alice, Bob et Charlie, par exemple) choisissent indépendamment les
+uns des autres un élément de l'ensemble $\{\mathtt{0},\mathtt{1}\}$ :
+\begin{itemize}
+\item s'ils ont tous les trois choisi la même option, ils gagnent
+  tous $0$,
+\item si l'un d'entre eux a choisi une option différente des deux
+  autres, celui qui a choisi cette option gagne $2$ et chacun des deux
+  autres gagne $-1$.
+\end{itemize}
+
+Il sera utile de remarquer que les joueurs ont des rôles complètement
+symétriques, et que les options sont également symétriques.
+
+(Attention, même si la somme des gains des trois joueurs vaut
+toujours $0$, ce n'est pas un « jeu à somme nulle » au sens classique,
+car ces derniers ne sont définis que pour \emph{deux} joueurs.)
+
+\smallbreak
+
+(1) Écrire le tableau des gains du jeu considéré.  (On choisira une
+façon raisonnable de présenter un tableau à trois entrées, par exemple
+comme plusieurs tableaux à deux entrées mis côte à côte.)
+
+\begin{corrige}
+On fait deux tableaux, l'un pour le cas où Alice joue $\mathtt{0}$,
+\begin{center}
+\begin{tabular}{r|cc}
+$\mathtt{0}$A, $\downarrow$B, C$\rightarrow$&$\mathtt{0}$&$\mathtt{1}$\\\hline
+$\mathtt{0}$&$0,0,0$&$-1,-1,+2$\\
+$\mathtt{1}$&$-1,+2,-1$&$+2,-1,-1$\\
+\end{tabular}
+\end{center}
+et l'autre pour le cas où Alice joue $\mathtt{1}$,
+\begin{center}
+\begin{tabular}{r|cc}
+$\mathtt{1}$A, $\downarrow$B, C$\rightarrow$&$\mathtt{0}$&$\mathtt{1}$\\\hline
+$\mathtt{0}$&$+2,-1,-1$&$-1,+2,-1$\\
+$\mathtt{1}$&$-1,-1,+2$&$0,0,0$\\
+\end{tabular}
+\end{center}
+Chacune des entrées doit bien sûr lister trois nombres, pour les gains
+d'Alice, Bob et Charlie respectivement.
+\end{corrige}
+
+\smallbreak
+
+Si $p \in [0;1]$, on notera simplement $p$ la stratégie mixte d'un
+joueur qui consiste à choisir l'option $\mathtt{1}$ avec
+probabilité $p$, et l'option $\mathtt{0}$ avec probabilité $1-p$.
+
+(2) Vérifier que l'espérance de gain d'Alice si elle joue selon la
+stratégie mixte $p$ tandis que Bob joue selon la stratégie mixte $q$
+et Charlie selon la stratégie mixte $r$ vaut : $-2pq -2pr +4qr + 2p -
+q -r$.  (Ici, $p,q,r$ sont trois réels entre $0$ et $1$.)
+
+\begin{corrige}
+Si Alice joue $\mathtt{0}$, son espérance de gain est $-q(1-r) -
+(1-q)r + 2qr$ d'après le premier tableau donné en réponse à la
+question précédente, soit $4qr - q - r$.  Si Alice joue $\mathtt{1}$,
+son espérance de gain vaut $2(1-q)(1-r) -q(1-r) - (1-q)r = 4qr - 3q -
+3r + 2$.  Si elle joue $p$, son espérance de gain vaut $1-p$ fois $4qr
+- q - r$ plus $p$ fois $4qr - 3q - 3r + 2$, ce qui vaut l'expression
+$-2pq -2pr +4qr + 2p - q -r$ annoncée.
+\end{corrige}
+
+\smallbreak
+
+(3) On se demande à quelle condition sur la stratégie mixte $q$ jouée
+par Bob et la stratégie mixte $r$ jouée par Charlie les options
+$\mathtt{0}$ et $\mathtt{1}$ d'Alice sont indifférentes pour elle
+(c'est-à-dire, lui apportent la même espérance de gain).  Montrer que
+c'est le cas si et seulement si $q + r = 1$.
+
+\begin{corrige}
+On cherche à quelle condition la valeur $4qr - q - r$ (qui se retrouve
+en substituant $0$ à $p$ dans $-2pq -2pr +4qr + 2p - q -r$) est égale
+à $4qr - 3q - 3r + 2$ (obtenue en mettant $p$ à $1$).  La différence
+entre les deux vaut $2 - 2q - 2r$, qui est donc nulle si et seulement
+si $q+r = 1$, comme annoncé.
+\end{corrige}
+
+\smallbreak
+
+(4) Déduire de la question (3) que si un profil $(p,q,r)$ de
+stratégies mixtes est un équilibre de Nash et que $0<p<1$ alors
+$q+r=1$.
+
+\begin{corrige}
+Si $(p,q,r)$ est un équilibre de Nash en stratégies mixtes et si
+$0<p<1$, c'est-à-dire si Alice pondère effectivement ses deux
+stratégies pures, c'est que les gains espérés qu'elles lui apportent
+sont égaux (si l'une était strictement meilleure que l'autre, Alice
+aurait strictement intérêt à ne jouer que celle-là), c'est-à-dire
+$q+r=1$ comme on vient de le voir.
+\end{corrige}
+
+\smallbreak
+
+(5) En déduire tous les équilibres de Nash $(p,q,r)$ du jeu (on pourra
+distinguer des cas selon que $p=0$, $p=1$ ou $0<p<1$ et de même pour
+$q$ et $r$ ; la symétrie doit permettre de simplifier le travail).
+
+\begin{corrige}
+Considérons un équilibre de Nash $(p,q,r)$.  On a vu en (4) que si
+l'un des trois nombres n'est ni $0$ ni $1$, la somme des deux autres
+vaut nécessairement $1$.
+
+(A) Si au moins deux des trois nombres sont strictement entre $0$ et
+$1$, disons sans perte de généralité que $p$ et $q$ le sont.  Alors
+$q+r=1$ et $p+r=1$, ce qui donne $p=q$.  Mais le fait que $r=1-q$ avec
+$0<q<1$ implique que $0<r<1$.  On a donc aussi $p+q=1$, ce qui
+implique $p=q=\frac{1}{2}$ et du coup $r=\frac{1}{2}$ puisque le
+raisonnement est complètement symétrique.  Or il est clair que
+$(\frac{1}{2},\frac{1}{2},\frac{1}{2})$ est bien un équilibre de Nash
+(toutes les options deviennent indifférentes pour tout le monde).
+
+(B) Si un seul des trois nombres est strictement entre $0$ et $1$,
+disons sans perte de généralité que $p$ l'est.  Alors $q+r=1$, et
+comme $q$ et $r$ doivent valoir chacun $0$ ou $1$, les seules
+possibilités sont $(p,0,1)$ et symétriquement $(p,1,0)$.  Vérifions
+que $(p,0,1)$ constitue bien un équilibre de Nash, y compris si $p=0$
+ou $p=1$ (le cas $(p,1,0)$ étant bien sûr symétrique) : dans
+$(p,0,1)$, Alice a un gain espéré de $-1$ qui ne varie pas selon $p$ ;
+Bob y a un gain espéré de $3p-1$, qui est supérieur ou égal au gain
+$-3p+2$ qu'il espère obtenir en changeant d'option, et le cas de
+Charlie est exactement symétrique.  On a donc bien affaire à un
+équilibre de Nash.
+
+(C) Enfin, si $p,q,r$ dont tous dans $\{0,1\}$, on a déjà vu en (B)
+que si deux valent $0$ et un vaut $1$ ou le contraire, on a affaire à
+un équilibre de Nash.  Reste le cas de $(0,0,0)$ ou $(1,1,1)$, et ce
+ne sont certainement pas des équilibres de Nash car les trois joueurs
+ont intérêt à changer unilatéralement de stratégie.
+
+Finalement, on a trouvé comme équilibre de Nash : le point isolé
+$(\frac{1}{2},\frac{1}{2},\frac{1}{2})$, et l'hexagone formé des
+segments paramétrés par $(p,0,1)$, $(1,0,r)$, $(1,q,0)$, $(p,1,0)$,
+$(0,1,r)$ et $(0,q,1)$ où la seule variable prend une valeur
+quelconque dans $[0;1]$ (intuitivement, ce sont des équilibres où deux
+joueurs sont en position de gagner, et le troisième, qui est en
+position de « faiseur de roi », ne peut pas gagner mais choisit au
+hasard lequel des deux autres gagne).
+\end{corrige}
+
+\smallbreak
+
+(6) Dans cette question, on modifie le jeu : plutôt que faire leurs
+choix indépendamment, les joueurs les font et les déclarent
+successivement (Alice, puis Bob, puis Charlie).  (a) Que va faire Bob
+si Alice choisit $\mathtt{0}$ ?  (b) Informellement, expliquer qui est
+avantagé ou désavantagé par cette modification de la règle.
+
+\begin{corrige}
+(a) Si Alice choisit $\mathtt{0}$, Bob a bien sûr intérêt à
+  choisir $\mathtt{1}$ (car s'il choisit lui-même $\mathtt{0}$,
+  Charlie choisira $\mathtt{1}$ et Bob a le pire gain possible
+  de $-1$).  Charlie sera alors dans la situation de choisir qui
+  d'Alice ou de Bob gagne sans pouvoir gagner lui-même (il est
+  « faiseur de roi »).  La situation est complètement symétrique si
+  Alice choisit $\mathtt{1}$, et le choix d'Alice est complètement
+  indifférent puisque les deux options sont équivalentes de son point
+  de vue.
+
+(b) On peut donc dire que Charlie est désavantagé par le fait de jouer
+  en dernier : il ne pourra pas gagner, seulement choisir lequel des
+  deux autres joueurs gagne.  (Ceci est un peu paradoxal quand on se
+  rappelle que dans un jeu à \emph{deux} joueurs à somme nulle, on ne
+  peut qu'être avantagé par le fait d'avoir connaissance de l'option
+  choisie par l'adversaire.)
+\end{corrige}
+
+%
+%
+%
+
 \subsection{Jeux de Gale-Stewart et détermination}
 
 \exercice
@@ -7153,7 +7336,7 @@ deux exercices précédents) ?\spaceout (À chaque fois, plusieurs
 %
 %
 
-\subsection{Jeux combinatoires impartiaux à information parfaite}
+\subsection{Jeux combinatoires à information parfaite}
 
 \exercice
 
@@ -7921,6 +8104,309 @@ a une racine.  Les entiers naturels strictement inférieurs
 d'éléments.)
 \par}
 
+%
+%
+%
+
+\exercice\label{tree-hackenbush-exercise}
+
+On s'intéresse dans cet exercice au jeu de \emph{Hackenbush impartial
+  en arbre}, défini comme suit.  L'état du jeu est représenté par un
+arbre (fini, enraciné\footnote{C'est-à-dire que la racine fait partie
+  de la donnée de l'arbre, ce qui est la convention la plus
+  courante.}).  Deux joueurs alternent et chacun à son tour choisit
+une arête de l'arbre et l'efface, ce qui fait automatiquement
+disparaître du même coup tout le sous-arbre qui descendait de cette
+arête (voir figure).  Le jeu se termine lorsque plus aucun coup n'est
+possible (c'est-à-dire que l'arbre est réduit à sa seule racine),
+auquel cas, selon la convention habituelle, le joueur qui ne peut plus
+jouer a perdu.
+
+\begin{center}
+\begin{tikzpicture}[baseline=0]
+\fill [gray!50!white] (-1.5,0) rectangle (1.5,-0.2);
+\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}]
+\node (P0) at (0,0) {};
+\node (P1) at (0,1) {};
+\node (P2) at (-1.5,2) {};
+\node (P3) at (-2.0,3) {};
+\node (P4) at (-1.0,3) {};
+\node (P5) at (1.5,2) {};
+\node (P6) at (0.75,3) {};
+\node (P7) at (1.5,3) {};
+\node (P8) at (2.25,3) {};
+\node (P9) at (1.75,1) {};
+\end{scope}
+\begin{scope}[line width=1.5pt]
+\draw (P0) -- (P1);
+\draw (P1) -- (P2);
+\draw (P1) -- (P5);
+\draw (P2) -- (P3);
+\draw (P2) -- (P4);
+\draw (P5) -- (P6);
+\draw (P5) -- (P7);
+\draw (P5) -- (P8);
+\draw (P0) -- (P9);
+\end{scope}
+\begin{scope}[line width=3pt,red]
+\draw ($0.5*(P1) + 0.5*(P5) + (-0.2,-0.2)$) -- ($0.5*(P1) + 0.5*(P5) + (0.2,0.2)$);
+\draw ($0.5*(P1) + 0.5*(P5) + (-0.2,0.2)$) -- ($0.5*(P1) + 0.5*(P5) + (0.2,-0.2)$);
+\end{scope}
+\end{tikzpicture}
+devient
+\begin{tikzpicture}[baseline=0]
+\fill [gray!50!white] (-1.5,0) rectangle (1.5,-0.2);
+\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}]
+\node (P0) at (0,0) {};
+\node (P1) at (0,1) {};
+\node (P2) at (-1.5,2) {};
+\node (P3) at (-2.0,3) {};
+\node (P4) at (-1.0,3) {};
+\node (P9) at (1.75,1) {};
+\end{scope}
+\begin{scope}[line width=1.5pt]
+\draw (P0) -- (P1);
+\draw (P1) -- (P2);
+\draw (P2) -- (P3);
+\draw (P2) -- (P4);
+\draw (P0) -- (P9);
+\end{scope}
+\end{tikzpicture}
+\end{center}
+
+(1) Expliquer pourquoi une position de ce jeu peut être considérée
+comme une somme de nim de différents jeux du même type.  Plus
+exactement, soit $T$ un arbre de racine $x$, soient $y_1,\ldots,y_r$
+les fils de $x$, soient $T_1,\ldots,T_r$ les sous-arbres ayant pour
+racines $y_1,\ldots,y_r$ et soient $T'_1,\ldots,T'_r$ les arbres de
+racine $x$ où $T'_i$ est formé de $x$ et de $T_i$ (avec une arête
+entre $x$ et $y_i$) : expliquer pourquoi la position représentée par
+l'arbre $T$ est la somme de nim de celles représentées par
+$T'_1,\ldots,T'_r$.  Qu'en déduit-on sur la valeur de Grundy de la
+position $T$ ?
+
+\begin{corrige}
+Il s'agit simplement d'observer que les différentes branches de
+l'arbre n'interagissent pas du tout.  Jouer à la somme de nim des jeux
+de Hackenbush représentés par les arbres $T'_1,\ldots,T'_r$ revient,
+si on veut, à jouer à Hackenbush sur la réunion disjointe de ces
+arbres, et comme la racine n'intervient pas, cela ne change rien au
+jeu de réunir leurs racines en une seule, ce qui donne l'arbre $T$.
+
+On en déduit que $\gr(T) = \gr(T'_1) \oplus \cdots \gr(T'_r)$ où
+$\gr(T)$ désigne, par abus de notation, la valeur de Grundy de la
+position de Hackenbush représentée par l'arbre $T$, et où $\oplus$
+désigne la somme de nim des entiers naturels.
+\end{corrige}
+
+\smallbreak
+
+\centerline{* * *}
+
+Indépendamment de ce qui précède, on va considérer une nouvelle
+opération sur les jeux : si $G$ est un jeu combinatoire impartial, vu
+comme un graphe orienté (bien-fondé), on définit un jeu noté $*{:}G$
+défini en ajoutant une unique position $0$ à $G$ comme on va
+l'expliquer.  Pour chaque position $z$ de $G$ il y a une position
+notée $*{:}z$ de $*{:}G$, et il y a une unique autre position,
+notée $0$, dans $*{:}G$ ; pour chaque arête $z \to z'$ de $G$, il y a
+une arête $*{:}z\, \to \, *{:}z'$ dans $*{:}G$, et il y a de plus une
+arête $*{:}z\, \to 0$ dans $*{:}G$ pour chaque $z$ (en revanche, $0$
+est un puits, c'est-à-dire qu'aucune arête n'en part) ; la position
+initiale de $*{:}G$ est $*{:}z_0$ où $z_0$ est celle de $G$.  De façon
+plus informelle, pour jouer au jeu $*{:}G$, chaque joueur peut soit
+faire un coup normal ($*{:}z\, \to \, *{:}z'$) de $G$, soit appliquer
+un coup « destruction totale » $*{:}z\, \to 0$ qui fait terminer
+immédiatement le jeu (et celui qui l'applique a gagné\footnote{Ce jeu
+  considéré tout seul n'est donc pas très amusant puisqu'on a toujours
+  la possibilité de gagner instantanément.}).
+
+\smallbreak
+
+(2) Montrer par induction bien-fondée que si $G$ est un jeu
+combinatoire impartial (bien-fondé) de valeur de Grundy $\alpha$,
+alors $*{:}G$ a pour valeur de Grundy $1+\alpha$.
+
+\begin{corrige}
+Observons tout d'abord que la valeur de Grundy de la position $0$
+de $*{:}G$ vaut $0$ puisque c'est un puits.  Montrons par induction
+bien-fondée sur les sommets de $*{:}G$ que la valeur de Grundy de la
+position $*{:}z$ vaut $1+\gr(z)$ où $\gr(z)$ désigne la valeur de
+Grundy de la position $z$ dans $G$.  Les voisins sortants de $*{:}z$
+sont $0$ et les $*{:}z'$ pour $z'$ voisin sortant de $z$ (dans $G$) ;
+la définition de la valeur de Grundy assure donc que $\gr(*{:}z) =
+\mex(\{0\} \cup \{\gr(*{:}z') : z'\in\outnb(z)\})$, c'est-à-dire que
+la valeur de Grundy de $*{:}z$ est le plus petit ordinal qui n'est
+ni $0$ ni un $\gr(*{:}z')$ pour $z'$ voisin sortant de $z$ ; mais par
+hypothèse d'induction, on peut remplacer $\gr(*{:}z')$ par
+$1+\gr(z')$, ce qui donne $\gr(*{:}z) = \mex(\{0\} \cup \{1+\gr(z') :
+z'\in\outnb(z)\})$.  Montrons que ce $\mex$ vaut $1+\gr(z)$ : pour
+cela, il suffit d'observer que (A) $1+\gr(z)$ ne vaut ni $0$ ni
+$1+\gr(z')$, et (B) tout ordinal $<1+\gr(z)$ vaut soit $0$ soit
+$1+\gr(z')$.  Or le (A) est clair car $1+\gr(z) > 0$ et que $\gr(z')
+\neq \gr(z)$ assure $1+\gr(z') \neq 1+\gr(z)$, et le (B) est clair car
+si $\beta < 1+\gr(z)$, alors soit $\beta=0$ soit $\beta = 1+\beta'$ où
+$\beta' < \gr(z)$, auquel cas la définition de $\gr$ assure qu'il
+existe $z'$ voisin sortant de $z$ tel que $\beta' = \gr(z')$.
+\end{corrige}
+
+\smallbreak
+
+(3) On revient au jeu de Hackenbush impartial en arbre.  Soit $T$ un
+arbre de racine $y$ et $T'$ l'arbre obtenu en ajoutant une nouvelle
+racine $x$ à $T$, c'est-à-dire que les sommets de $T'$ sont ceux de
+$T$ plus $x$, qui en est la racine, avec une arête entre $x$ et $y$.
+Expliquer pourquoi le jeu de Hackenbush représenté par $T'$ s'obtient
+par la construction « $*{:}$ » considérée en (2) à partir de celui
+représenté par $T$.  Qu'en déduit-on sur la valeur de Grundy de la
+position $T'$ par rapport à celle de $T$ ?
+
+\begin{corrige}
+Un coup dans le jeu de Hackenbush représenté par l'arbre $T'$ peut
+consister soit à couper l'arbre à sa racine, c'est-à-dire couper
+l'arête reliant $x$ et $y$, ce qui met fin au jeu immédiatement, soit
+à jouer dans $T$ (i.e., couper une arête de celui-ci) ; c'est
+précisément la définition qu'on a donnée de la
+construction « $*{:}$ ».
+
+On en déduit que $\gr(T') = 1 + \gr(T)$ (comme par ailleurs on a ici
+affaire à des entiers naturels, le $+$ est commutatif, donc dans cette
+question on peut aussi l'écrire $\gr(T') = \gr(T) + 1$).
+\end{corrige}
+
+\smallbreak
+
+(4) Déduire des questions précédentes une méthode pour calculer la
+valeur de Grundy d'une position quelconque au Hackenbush impartial en
+arbre.
+
+\begin{corrige}
+Des questions précédentes, on déduit que la valeur de Grundy d'un
+arbre $T$ au Hackenbush impartial se calcule comme la somme de nim des
+$\gr(T'_i) = 1+\gr(T_i)$ où les $T_i$ sont les sous-arbres partant des
+fils de la racine de $T$.
+
+On peut donc calculer la valeur de Grundy d'un arbre en calculant
+celle de ses sous-arbres enracinés aux différents nœuds, des feuilles
+vers la racine : dès qu'on a calculé la valeur de Grundy de tous les
+sous-arbres enracinés aux fils $y_1,\ldots,y_r$ d'un nœud $x$, on en
+déduit celle du sous-arbre enraciné en leur père $x$ comme la somme de
+nim des valeurs en question incrémentées de $1$.
+\end{corrige}
+
+\smallbreak
+
+(5) Quelle est la valeur de Grundy de la position représentée
+ci-dessous ?  (Il s'agit de la position utilisée en exemple plus
+haut.)  Quel coup préconiseriez-vous dans cette situation ?
+
+\begin{center}
+\begin{tikzpicture}[baseline=0]
+\fill [gray!50!white] (-1.5,0) rectangle (1.5,-0.2);
+\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}]
+\node (P0) at (0,0) {};
+\node (P1) at (0,1) {};
+\node (P2) at (-1.5,2) {};
+\node (P3) at (-2.0,3) {};
+\node (P4) at (-1.0,3) {};
+\node (P5) at (1.5,2) {};
+\node (P6) at (0.75,3) {};
+\node (P7) at (1.5,3) {};
+\node (P8) at (2.25,3) {};
+\node (P9) at (1.75,1) {};
+\end{scope}
+\begin{scope}[line width=1.5pt]
+\draw (P0) -- (P1);
+\draw (P1) -- (P2);
+\draw (P1) -- (P5);
+\draw (P2) -- (P3);
+\draw (P2) -- (P4);
+\draw (P5) -- (P6);
+\draw (P5) -- (P7);
+\draw (P5) -- (P8);
+\draw (P0) -- (P9);
+\end{scope}
+\end{tikzpicture}
+\end{center}
+
+\begin{corrige}
+On trouve les valeurs de Grundy suivantes en notant à côté de chaque
+nœud la valeur du sous-arbre enraciné en ce nœud :
+\begin{center}
+\begin{tikzpicture}[baseline=0]
+\fill [gray!50!white] (-1.5,0) rectangle (1.5,-0.2);
+\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}]
+\node (P0) at (0,0) {};
+\node (P1) at (0,1) {};
+\node (P2) at (-1.5,2) {};
+\node (P3) at (-2.0,3) {};
+\node (P4) at (-1.0,3) {};
+\node (P5) at (1.5,2) {};
+\node (P6) at (0.75,3) {};
+\node (P7) at (1.5,3) {};
+\node (P8) at (2.25,3) {};
+\node (P9) at (1.75,1) {};
+\end{scope}
+\begin{scope}[line width=1.5pt]
+\draw (P0) -- (P1);
+\draw (P1) -- (P2);
+\draw (P1) -- (P5);
+\draw (P2) -- (P3);
+\draw (P2) -- (P4);
+\draw (P5) -- (P6);
+\draw (P5) -- (P7);
+\draw (P5) -- (P8);
+\draw (P0) -- (P9);
+\end{scope}
+\node[anchor=east] at (P2) {$0$};
+\node[anchor=west] at (P5) {$1$};
+\node[anchor=east] at (P1) {$3$};
+\node[anchor=east] at (P0) {$5$};
+\end{tikzpicture}
+\end{center}
+
+La valeur de Grundy recherchée est donc $5$.  En étudiant les
+différentes possibilités, on trouve qu'un coup gagnant possible
+consiste à retirer n'importe laquelle des arêtes les plus en haut sur
+le dessin (dans tous les cas, le sommet étiqueté $3$ sur la figure
+ci-dessus passe à $0$ et la racine de même).
+\end{corrige}
+
+\smallbreak
+
+(La question qui suit est indépendante des questions précédentes et
+concerne les jeux combinatoires \emph{partisans}.)
+
+(6) On remarque que la construction $*{:}G$ définie avant la
+question (2) peut se définir de façon identique lorsque $G$ est un jeu
+partisan, en donnant à une arête $*{:}z\, \to \, *{:}z'$ la même
+couleur que $z\to z'$, et à une arête $*{:}z\, \to 0$ la couleur verte
+(ce qui signifie : à la fois bleue et rouge).  En décrivant une
+stratégie, montrer que si $G \geq H$ on a aussi $*{:}G \geq *{:}H$, et
+en déduire que si $G\doteq H$ alors $*{:}G \doteq *{:}H$ (où $\doteq$
+désigne l'égalité au sens de Conway des jeux partisans).
+
+\begin{corrige}
+Tout d'abord, observons que $-(*{:}G) = *{:}(-G)$ puisque la
+construction « $*{:}$ » est symétrique entre bleu et rouge.
+
+La condition $G\geq H$ signifie que le joueur bleu (Blaise) possède
+une stratégie gagnante au jeu $G-H = G+(-H)$ s'il joue en second.
+Montrons qu'il en possède encore une à $(*{:}G) - (*{:}H) = (*{:}G) +
+(*{:}(-H))$ en considérant comment il répond à un coup de son
+adversaire (Roxane).  Si Roxane joue un coup de « destruction totale »
+sur l'une des composantes $(*{:}G)$ ou $(*{:}(-H))$, Blaise réplique
+sur l'autre et gagne.  Si Roxane joue un coup dans une des deux
+composantes $G$ ou $-H$, Blaise répond selon la stratégie qu'il est
+supposé posséder.  Dans tous les cas, Blaise peut répondre à tout coup
+de Roxane, donc il gagne.  Ceci montre $*{:}G \geq *{:}H$.
+
+Comme $G\doteq H$ signifie $G\geq H$ et $G\leq H$, on a bien $*{:}G
+\geq *{:}H$ et $*{:}G \leq *{:}H$ d'après ce qu'on vient d evoir,
+c'est-à-dire $*{:}G \doteq *{:}H$.  (La valeur d'un jeu partisan
+$*{:}G$ est donc déterminée par la valeur de $G$.)
+\end{corrige}
+
 
 
 \setbox0=\vbox\bgroup