Add an English translation.

1 files changed, 228 insertions, 28 deletions

diff --git a/controle-20170419.tex b/controle-20170419.tex
index 8529436..b4a9f19 100644
--- a/controle-20170419.tex
+++ b/controle-20170419.tex
@@ -1,6 +1,6 @@
 %% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
 \documentclass[12pt,a4paper]{article}
-\usepackage[francais]{babel}
+\usepackage[english,francais]{babel}
 \usepackage[utf8]{inputenc}
 \usepackage[T1]{fontenc}
 %\usepackage{ucs}
@@ -96,6 +96,8 @@ Les exercices sont totalement indépendants.  Ils pourront être traités
 dans un ordre quelconque, mais on demande de faire apparaître de façon
 très visible dans les copies où commence chaque exercice.
 
+Une traduction anglaise suit l'énoncé en français.
+
 \medbreak
 
 L'usage de tous les documents (notes de cours manuscrites ou
@@ -107,6 +109,29 @@ L'usage des appareils électroniques est interdit.
 
 Durée : 1h30
 
+\vskip3ex
+
+\begin{otherlanguage}{english}
+{\footnotesize
+
+\noindent\textbf{Instructions.}
+
+The following exercises are independent.  They can be answered in any
+order, but the beginning and end of each exercise should be clearly
+marked.
+
+An English translation follows the questions in French.
+
+The use of all documents (handwritten or printed course notes,
+exercise sheets, books) is permitted.
+
+The use of electronic devices is forbidden.
+
+Duration: 1h30
+
+\par}
+\end{otherlanguage}
+
 \vfill
 {\noindent\tiny
 \immediate\write18{sh ./vc > vcline.tex}
@@ -121,7 +146,7 @@ Git: \input{vcline.tex}
 %
 %
 
-\exercice
+\exercice\label{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
@@ -189,12 +214,12 @@ devient
 
 (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$
+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)
+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$ ?
 
@@ -205,17 +230,17 @@ position $T$ ?
 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'$) dans $G$, soit appliquer un
-coup « destruction totale » $*{:}z\, \to 0$ qui fait terminer
+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.}).
@@ -230,14 +255,12 @@ alors $*{:}G$ a pour valeur de Grundy $1+\alpha$.
 
 (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$.
+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$ ?
+représenté par $T$.  Qu'en déduit-on sur la valeur de Grundy de la
+position $T'$ par rapport à celle de $T$ ?
 
 \smallbreak
 
@@ -298,7 +321,7 @@ désigne l'égalité au sens de Conway des jeux partisans).
 %
 %
 
-\exercice
+\exercice\label{normal-game-exercise}
 
 On considère le jeu en forme normale suivant : \emph{trois} joueurs
 (Alice, Bob et Charlie, par exemple) choisissent indépendamment les
@@ -345,7 +368,7 @@ c'est le cas si et seulement si $q + r = 1$.
 
 \smallbreak
 
-(4) Déduire de la question (3) que si un profil $(p,q,r)$ de
+(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$.
 
@@ -358,10 +381,187 @@ $q$ et $r$ ; la symétrie doit permettre de simplifier le travail).
 \smallbreak
 
 (6) Dans cette question, on modifie le jeu : plutôt que faire leurs
-choix indépendamment, les joueurs le font 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.
+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{otherlanguage}{english}
+
+\bigbreak
+
+\centerline{\hbox to2truein{\hrulefill}}
+\centerline{\textbf{English translation}}
+
+\footnotesize
+
+(This translation is provided to help understand the French version,
+but the latter remains the official text and should be referred to in
+case of ambiguity or doubt, as this translation has not been checked
+as carefully.)
+
+\medbreak
+
+\textbf{Exercise \ref{hackenbush-exercise}.}
+
+This exercise concerns the game of \emph{impartial tree Hackenbush},
+defined as follows.  The state of the game is represented by a
+(finite, rooted\footnote{Meaning that the root is part of the tree
+  datum, which the usual convention.}) tree.  Two players alternate,
+each in turn chooses an edge of the tree and removes it, which
+automatically causes the entire subtree from this edge to disappear
+(see figure in French version).  The game ends when no move is
+possible (meaning that the tree is reduced to its root), at which
+point, following the usual convention, the player who can no longer
+play loses.
+
+\smallbreak
+
+(1) Explain why a position in this game can be considered as a nim sum
+of different games of the same type.  More precisely, let $T$ be a
+tree with root $x$, let $y_1,\ldots,y_r$ be the children of $x$, let
+$T_1,\ldots,T_r$ be the subtrees having $y_1,\ldots,y_r$ as roots, and
+let $T'_1,\ldots,T'_r$ be the trees rooted at $x$ where $T'_i$
+consists of $x$ and $T_i$ (along with an edge between $x$ and $y_i$):
+explain why the position represented by the tree $T$ is the nim sum of
+those represented by $T'_1,\ldots,T'_r$.  What can we deduce about the
+Grundy value (=nim value) of the position $T$?
+
+\smallbreak
+
+\centerline{* * *}
+
+Independently of the above, we consider a new operation on games: if
+$G$ is an impartial combinatorial game, considered as a (well-founded)
+oriented graph, we define a new game noted $*{:}G$ defined by adding a
+unique new position $0$ to $G$ as follows.  For each position $z$
+of $G$, there is a position $*{:}z$ of $*{:}G$, and there is a unique
+extra position, written $0$, in $*{:}G$; for each edge $z \to z'$
+of $G$, there is an edge $*{:}z\, \to \, *{:}z'$ in $*{:}G$, and
+additionally there are edges $*{:}z\, \to 0$ in $*{:}G$ for each $z$
+(on the other hand, $0$ is a sink, meaning that it has no outgoing
+edge); the initial position of $*{:}G$ is $*{:}z_0$ where $z_0$ is
+that of $G$.  Informally, to play the game $*{:}G$, each player can
+either make a normal move ($*{:}z\, \to \, *{:}z'$) from $G$, or apply
+the ``total destruction'' move $*{:}z\, \to 0$ which terminates tha
+game immediately (and the one who plays it wins\footnote{Considered
+  alone, this game is therefore not very fun because there is always
+  this possibility of winning immediately.}).
+
+\smallbreak
+
+(2) Show by well-founded induction that if $G$ is a (well-founded)
+impartial combinatorial game with Grundy value $\alpha$, then $*{:}G$
+has Grundy value $1+\alpha$.
+
+\smallbreak
+
+(3) We now return to impartial tree Hackenbush.  Let $T$ be a tree
+with root $y$ and $T'$ the tree obtained by adding a new root $x$
+to $T$, meaning that the vertices of $T'$ are those of $T$ plus $x$,
+which is the root, with an edge between $x$ and $y$.  Explain why the
+Hackenbush game represented by $T'$ is obtained, by means of the
+``$*{:}$'' construction considered in (2), from that represented
+by $T$.  What can we deduce about the Grundy value of the
+position $T'$ with respect to that of $T$?
+
+\smallbreak
+
+(4) Use the previous questions to propose a method to compute the
+Grundy value of an arbitrary position of impartial tree Hackenbush.
+
+\smallbreak
+
+(5) What is the Grundy value of the position represented in the French
+version of the question?  (It is identical to the one used to show an
+example of a possible move.)  What move would you prescribe in this
+situation?
+
+\smallbreak
+
+(6) Note that the $*{:}G$ construction defined just before
+question (2) can be defined in an identical way when $G$ is a partizan
+game, by giving an edge $*{:}z\, \to \, *{:}z'$ the same color as
+$z\to z'$, and an edge $*{:}z\, \to 0$ the color green (which means:
+both blue and red).  By describing a strategy, show that if $G \geq H$
+then we also have $*{:}G \geq *{:}H$, and deduce that if $G\doteq H$
+then $*{:}G \doteq *{:}H$ (where $\doteq$ denotes equality in the
+sense of Conway of partizan games).
+
+\bigbreak
+
+\textbf{Exercise \ref{normal-game-exercise}.}
+
+We consider the following normal form game: \emph{three} players
+(Alice, Bob and Charlie, say) each choose, independently of one
+another, an element of the set $\{\mathtt{0},\mathtt{1}\}$:
+\begin{itemize}
+\item if they all choose the same option, they all receive a payoff
+  of $0$;
+\item whereas if one chooses an option different from the two others,
+  whoever chooses this option gets a payoff of $2$ and the two others
+  receive $-1$ each.
+\end{itemize}
+
+It is worth noting that the players have a completely symmetric rôle,
+and that the options are likewise symmetric.
+
+(Warning: even though the sum of the payoffs of the three players is
+always $0$, this is not a ``zero-sum game'' in the classical sense,
+because the latter are defined only for \emph{two} players.)
+
+\smallbreak
+
+(1) Write the payoff matrix for the game under consideration.  (Choose
+a reasonable way to present a table with three entries, for example as
+several two-entry tables put side by side.)
+
+\smallbreak
+
+If $p \in [0;1]$, we simply write $p$ for the mixed strategy for some
+player consisting of choosing option $\mathtt{1}$ with
+probability $p$, and option $\mathtt{0}$ with probability $1-p$.
+
+(2) Check that the expected payoff for Alice if she plays following
+the mixed strategy $p$ while Bob plays following the mixed
+strategy $q$ and Charlie following the mixed strategy $r$ is: $-2pq
+-2pr +4qr + 2p - q -r$.  (Here, $p,q,r$ are three real numbers between
+$0$ and $1$.)
+
+\smallbreak
+
+(3) We now ask ourselves under what condition on the mixed strategy
+$q$ used by Bob and the mixed strategy $r$ used by Charlie the two
+options $\mathtt{0}$ and $\mathtt{1}$ for Alice are indifferent to her
+(meaning that they provide her with the same expected payoff).  Show
+that this is the case if and only if $q + r = 1$.
+
+\smallbreak
+
+(4) Deduce from question (3) that if mixed strategy profile $(p,q,r)$
+is a Nash equilibrium and if $0<p<1$ then $q+r=1$.
+
+\smallbreak
+
+(5) Use the previous questions to find all Nash equilibria $(p,q,r)$
+in the game (one might discuss various cases according as $p=0$, $p=1$
+or $0<p<1$, and similarly for $q$ and $r$; one might use symmetry to
+simplify the task).
+
+\smallbreak
+
+(6) In this question, the game is altered: instead of making their
+choices independently, the players make them and declare them
+successively (Alice, then Bob, then Charlie).  (a) What will Bob do if
+Alice chooses $\mathtt{0}$?  (b) Explain informally who is favored or
+disfavored by this alteration of the rule.
+
+\end{otherlanguage}