Add an English translation.

1 files changed, 276 insertions, 15 deletions

diff --git a/controle-20250626.tex b/controle-20250626.tex
index 6786bed..9406b12 100644
--- a/controle-20250626.tex
+++ b/controle-20250626.tex
@@ -92,6 +92,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 indicative suit l'énoncé en français.
+
 \medbreak
 
 L'usage de tous les documents (notes de cours manuscrites ou
@@ -101,7 +103,7 @@ L'usage des appareils électroniques est interdit.
 
 \medbreak
 
-Durée : 2h
+% Durée : 2h
 
 \ifcorrige
 Ce corrigé comporte \textcolor{red}{XXX} pages (page de garde incluse).
@@ -123,7 +125,7 @@ Git: \input{vcline.tex}
 %
 %
 
-\exercise
+\exercise\label{normal-form-games-exercise}
 
 \textbf{(1)} On considère le jeu en forme normale symétrique à somme
 nulle défini par la matrice de gains suivante :
@@ -288,14 +290,14 @@ meilleur possible ici.
 %
 %
 
-\exercise
+\exercise\label{modified-nim-exercise}
 
 On considère dans cet exercice le jeu suivant :
 
 Alice et Bob ont devant eux des piles de jetons, qui représentent
 l'état du jeu (= la position).  Chaque pile contient un certain nombre
 fini (entier naturel) de jetons.  Les piles sont numérotées par des
-entiers naturelles, mais il n'y en a qu'un nombre fini qui soient
+entiers naturels, mais il n'y en a qu'un nombre fini qui soient
 non-vides (i.e., qui aient $>0$ jetons).  Pour représenter la position
 mathématiquement, on utilisera la liste $(n_0, n_1, n_2, \ldots, n_k)$
 où $n_i$ est le nombre de jetons de la pile numérotée $i$, et où ceci
@@ -537,7 +539,7 @@ démonstration.
 %
 %
 
-\exercise
+\exercise\label{indeterminacy-exercise}
 
 On se propose dans cet exercice de montrer qu'il existe une partie $A
 \subseteq \{0,1\}^{\mathbb{N}}$ tel que le jeu de Gale-Stewart $G(A)
@@ -697,16 +699,16 @@ $(\tau_\xi)_{\xi<\mathfrak{c}}$ des stratégies de Bob.  On les
 définira après la question (9), mais on n'a pas besoin d'en savoir
 plus pour l'instant.
 
-\textbf{(7)} En supposant préalablement définis des éléments
-$(a_\xi)_{\xi<\alpha}$ et $(b_\xi)_{\xi<\alpha}$ de
-$\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$, déduire en une
-ligne des questions précédentes qu'il existe $b'$ qui soit de la forme
-$\sigma_\alpha \ast y$ (pour un certain $y \in \{0,1\}^{\mathbb{N}}$),
-mais différent de tous les $a_\xi$ pour $\xi<\alpha$.  Expliquer aussi
-pourquoi il existe $a'$ qui soit de la forme $z \ast \tau_\alpha$
-(pour un certain $z \in \{0,1\}^{\mathbb{N}}$), mais différent de tous
-les $b_\xi$ pour $\xi<\alpha$ et également différent du $b'$ qu'on
-vient de trouver.
+\textbf{(7)} En supposant donnés des éléments $(a_\xi)_{\xi<\alpha}$
+et $(b_\xi)_{\xi<\alpha}$ de $\{0,1\}^{\mathbb{N}}$, où $\alpha <
+\mathfrak{c}$, déduire en une ligne des questions précédentes qu'il
+existe $b'$ qui soit de la forme $\sigma_\alpha \ast y$ (pour un
+certain $y \in \{0,1\}^{\mathbb{N}}$), mais différent de tous les
+$a_\xi$ pour $\xi<\alpha$.  Expliquer aussi pourquoi il existe $a'$
+qui soit de la forme $z \ast \tau_\alpha$ (pour un certain $z \in
+\{0,1\}^{\mathbb{N}}$), mais différent de tous les $b_\xi$
+pour $\xi<\alpha$ et également différent du $b'$ qu'on vient de
+trouver.
 
 \begin{corrige}
 On pose $b' = \sigma_\alpha \ast y$, où l'existence de $y$ a été
@@ -814,6 +816,265 @@ plus généralemnt boréliennes de $\{0,1\}^{\mathbb{N}}$.  Ici on doit
 conclure que la partie $A$ n'est pas borélienne.
 \end{corrige}
 
+%
+%
+%
+
+\begin{otherlanguage}{english}
+
+\vskip1in\penalty-1000
+
+\centerline{\hbox to2truein{\hrulefill}}
+\centerline{\textbf{English translation}}
+
+\footnotesize
+
+(This translation is provided to help understand the French version,
+but the French remains the only official text and should be referred
+to in case of ambiguity or doubt, as this translation has not been
+checked carefully.)
+
+\medbreak
+
+\textbf{Exercise \ref{normal-form-games-exercise}.}
+
+\textbf{(1)} Consider the zero-sum symmetric normal form game defined
+by the following payoff matrix:
+\begin{center}
+\begin{tabular}{r|ccc}
+$\downarrow$Alice, Bob$\rightarrow$&Rock&Paper&Scissors\\\hline
+Rock&$0$&$-1$&$+1$\\
+Paper&$+1$&$0$&$-1$\\
+Scissors&$-1$&$+1$&$0$\\
+\end{tabular}
+\end{center}
+(Only Alice's payoff has been entered in each cell because the two
+players' payoffs are opposite.)
+
+What are all the Nash equilibria of this game?
+
+\textbf{(2)} We now want to add a new option “Foobar” to the above
+game, that is, we consider the game in normal form (still symmetric
+and zero-sum) defined by the payoff matrix:
+\begin{center}
+\begin{tabular}{r|cccc}
+$\downarrow$Alice, Bob$\rightarrow$&Rock&Paper&Scissors&Foobar\\\hline
+Rock&$0$&$-1$&$+1$&$-x$\\
+Paper&$+1$&$0$&$-1$&$-y$\\
+Scissors&$-1$&$+1$&$0$&$-z$\\
+Foobar&$x$&$y$&$z$&$0$\\
+\end{tabular}
+\end{center}
+(The following three sub-questions are independent.)
+
+\textbf{\hphantom{(2)} (a)} Under what (necessary and sufficient)
+condition on $x,y,z$ are the Nash equilibria found in (1) still Nash
+equilibria for this new game?\quad\textbf{(b)} Under what (necessary
+and sufficient) condition on $x,y,z$ is there a Nash equilibrium where
+both players play the Foobar option (with
+certainty)?\quad\textbf{(c)} Under what (necessary and sufficient)
+condition on $x,y,z$ is there a Nash equilibrium where both players
+play $\frac{1}{2}\text{Rock} + \frac{1}{2}\text{Foobar}$ (i.e., Rock
+or Foobar each with probability $\frac{1}{2}$)?
+
+\textbf{(3)} We change the game: we now use the payoff matrix written
+in (1), but this time the payoffs of the two players will be equal
+instead of opposite (so it is no longer a zero-sum game! the players
+are allies and no longer adversaries).  The table gives the value of
+the common payoff for both players.
+
+\textbf{\hphantom{(3)} (a)} Show that the Nash equilibria found in (1)
+are still Nash equilibria of this new game. \quad\textbf{(b)} Give at
+least one Nash equilibrium different from these.  Comment briefly on
+the possible difference in payoff between the Nash equilibria found in
+(a) and (b).
+
+\medbreak
+
+\textbf{Exercise \ref{modified-nim-exercise}.}
+
+In this exercise, we consider the following game:
+
+Alice and Bob have piles of tokens in front of them, which represent
+the state of the game (= the position).  Each pile contains a finite
+number (natural numbers) of tokens.  The piles are numbered by natural
+numbers, but only a finite number are non-empty (i.e., have $>0$
+tokens).  To represent the position mathematically, we will use the
+list $(n_0, n_1, n_2, \ldots, n_k)$ where $n_i$ is the number of
+tokens in pile numbered i, and this implicitly means that all piles
+$\geq k$ are empty.  A player's move consists of removing exactly one
+token from a given pile $i$ of their choice, and adding as many tokens
+as they wish (including zero) to each of the piles $j<i$, including
+adding different numbers to different piles.  For example, from
+position $(0,3,2)$ one can play to $(42,1000,1)$ or to $(0,2,2)$ or to
+$(696\,729\,600,2,2)$.
+
+As usual, the player who cannot play has lost, meaning the one who
+takes the last token has won.
+
+\medskip
+
+\textbf{(1)} Show that the game just defined necessarily ends in a
+finite number of moves, regardless of the initial position and
+regardless of the moves made by the players.  (Careful justification
+is required here.)
+
+\textbf{Definition:} Let us call a position “totally even” when the
+number $n_i$ of tokens in each pile is even, and “not totally even”
+when least one of the $n_i$ is odd.
+
+\textbf{(2)} Show that any move played from a totally even position
+necessarily leads to a not totally even position.
+
+\textbf{(3)} Show that from any not totally even position there is at
+least one move leading to a totally even position.
+
+\textbf{(4)} Deduce which positions in the game the first player has a
+winning strategy, and which ones the second player has one.  (Very
+careful justification is required.)
+
+\textbf{(5)} Calculate, as a function of $n$, the Grundy value of
+position $(n)$ (i.e., if there is only the pile numbered $0$, and
+if it contains $n$ tokens).
+
+\textbf{(6)} Deduce the Grundy value of the positions $(0,1)$ and
+$(1,1)$, then more generally of $(n,1)$ as a function of $n$.
+
+\textbf{(7)} Deduce the Grundy value of the positions $(0,2)$ and
+$(1,2)$, and more generally of $(n_0,n_1)$ as a function of $n_0,n_1$.
+
+\textbf{(8)} Deduce the Grundy value of the position $(0,0,1)$.
+
+\textbf{(9)} Conjecture a general formula for the Grundy value
+of any position $(n_0,n_1,\ldots,n_k)$.
+
+\textbf{(10)} Prove this formula.  (This question is more difficult,
+and it may be appropriate to save it for the end.  One can draw
+inspiration from the proof given in class of the calculation of the
+Grundy value for the game of nim.)
+
+\medbreak
+
+\textbf{Exercise \ref{indeterminacy-exercise}.}
+
+In this exercise, we aim to show that there exists a game $A \subseteq
+\{0,1\}^{\mathbb{N}}$ such that the Gale-Stewart game $G(A) :=
+G_{\{0,1\}}(A)$ is not determined (i.e., such that neither player has
+a winning strategy).
+
+(The proof has been divided into questions allowing short answers,
+sometimes as short as a single line.)
+
+\medskip
+
+\textbf{(1)} Show that there exists a bijection $h_{\mathrm{A}}$
+(resp. $h_{\mathrm{B}}$) between $\{0,1\}^{\mathbb{N}}$ and the set of
+Alice's (resp. Bob's) strategies in the game $G(A)$. (\emph{Hint:} one
+can quickly explain why there exists a bijection between $\mathbb{N}$
+and the set of positions where it is Alice's, or Bob's, turn to play.)
+
+\textbf{(2)} We \emph{admit} that there exists a well-ordering
+relation $\preceq$ on $\{0,1\}^{\mathbb{N}}$.  Deduce that there
+exists an ordinal $\gamma$ and a bijection $\xi \mapsto u_\xi$ between
+the set $\{\xi < \gamma\}$ of ordinals smaller than $\gamma$ and the
+set $\{0,1\}^{\mathbb{N}}$ (in other words, the $u_\xi$ are pairwise
+distinct and $\{u_\xi : \xi < \gamma\} = \{0,1\}^{\mathbb{N}}$).
+
+\textbf{(3)} Explain in one line why there exists a smallest
+ordinal $\gamma$ such that there exists a surjection $\xi \mapsto u_\xi$
+from the set $\{\xi < \gamma\}$ of ordinals smaller than $\gamma$
+to the set $\{0,1\}^{\mathbb{N}}$.
+
+\textbf{Definition:} We will denote $\mathfrak{c}$ the ordinal whose
+existence we just justified, i.e., the smallest $\gamma$ such that we
+can write $\{u_\xi : \xi < \gamma\} = \{0,1\}^{\mathbb{N}}$ for a
+certain function $\xi \mapsto u_\xi$, which we fix in the
+following.
+
+\textbf{(4)} \textbf{(a)} If $(v_\xi)_{\xi<\alpha}$ are any elements
+of $\{0,1\}^{\mathbb{N}}$, where $\alpha < \mathfrak{c}$, explain in
+one line why there exists an element $x$ of $\{0,1\}^{\mathbb{N}}$
+different from all the $v_\xi$.\quad\textbf{(b)} If $w$ is also an
+element of $\{0,1\}^{\mathbb{N}}$, explain why we can find $x$ that is
+different from $w$ (and still different from the $v_\xi$).
+
+\textbf{Definition:} If $\sigma$ is a strategy for Alice in the game
+$G(A)$ and $y \in \{0,1\}^{\mathbb{N}}$, we denote by $\sigma \ast y$
+the confrontation in which Alice plays according to $\sigma$ and Bob
+plays simply the successive terms of $y$ (independently of what Alice
+does; i.e.,\footnote{To remove any doubt: $\sigma \ast y$ is the
+sequence $(t_n)_{n\in\mathbb{N}}$ defined by induction by: $t_{2m} =
+\sigma((t_0,\ldots,t_{2m-1}))$ and $t_{2m+1} = y_m$.} $\sigma \ast y$
+is a binary sequence whose sequence of odd terms, those played by Bob,
+is given by $y$, while Alice plays the even terms according to the
+strategy $\sigma$).  Symmetrically, if $\tau$ is a strategy for Bob
+and $z \in \{0,1\}^{\mathbb{N}}$, we define $z \ast \tau$ as the
+confrontation in which Alice plays the terms of the sequence $z$ and
+Bob plays according to $\tau$.
+
+\textbf{(5)} If $\sigma$ is a strategy for Alice, explain in one line
+why the function $y \mapsto \sigma \ast y$ (from
+$\{0,1\}^{\mathbb{N}}$ to $\{0,1\}^{\mathbb{N}}$) is injective.
+
+\textbf{(6)} If $(a_\xi)_{\xi<\alpha}$ are any elements of
+$\{0,1\}^{\mathbb{N}}$, where $\alpha < \mathfrak{c}$, deduce from
+(4)(a) and (5) that there exists $y \in \{0,1\}^{\mathbb{N}}$ such
+that $\sigma \ast y$ is different from all $a_\xi$ for $\xi<\alpha$.
+
+\textbf{Assumption:} In questions (7) to (9), we assume that
+$(\sigma_\xi)_{\xi<\mathfrak{c}}$ are strategies for Alice and
+$(\tau_\xi)_{\xi<\mathfrak{c}}$ are strategies for Bob.  We will
+define them after question (9), but we don't need to know more about
+them for now.
+
+\textbf{(7)} Assuming we are given elements $(a_\xi)_{\xi<\alpha}$ and
+$(b_\xi)_{\xi<\alpha}$ of $\{0,1\}^{\mathbb{N}}$, where $\alpha <
+\mathfrak{c}$, deduce in one line from the previous questions that
+there exists $b'$ which is of the form $\sigma_\alpha \ast y$ (for
+some $y \in \{0,1\}^{\mathbb{N}}$), but different from all $a_\xi$ for
+$\xi<\alpha$.  Also explain why there exists $a'$ that is of the form
+$z \ast \tau_\alpha$ (for some $z \in \{0,1\}^{\mathbb{N}}$), but
+different from all $b_\xi$ for $\xi<\alpha$ and also different from
+the $b'$ that we have just found.
+
+We will admit that it poses no problem to \emph{choose} such $a'$ and
+$b'$ as a function of all the other parameters.
+
+\textbf{(8)} Deduce from all of the above that there exist $(a_\xi)_{\xi
+< \mathfrak{c}}$ and $(b_\xi)_{\xi < \mathfrak{c}}$ such that:
+\begin{itemize}
+\item none of the $a_\xi$ is equal to any of the $b_\zeta$ (i.e., for
+all $\xi<\mathfrak{c}$ and all $\zeta<\mathfrak{c}$, we have $a_\xi
+\neq b_\zeta$),
+\item for all $\xi < \mathfrak{c}$, there exists $y \in
+\{0,1\}^{\mathbb{N}}$ such that $b_\xi = \sigma_\xi \ast y$,
+\item for all $\xi < \mathfrak{c}$, there exists $z \in
+\{0,1\}^{\mathbb{N}}$ such that $a_\xi = z \ast \tau_\xi$.
+\end{itemize}
+(This is all we will need to know for the following questions.)
+
+\textbf{Definition:} Let us now call $A = \{a_\xi : \xi <
+\mathfrak{c}\}$ the set of the $a_\xi$ that we just constructed
+in (8).
+
+\textbf{(9)} Show that, for all $\xi$, the strategy $\tau_\xi$ is not
+a winning one for Bob in the game $G(A)$.  Show that the strategy
+$\sigma_\xi$ is not a winning one for Alice in this same game (note:
+this is not completely symmetric since $A$ is the set of $a_\alpha$).
+
+\textbf{Definition:} Now let $\sigma_\xi := h_{\mathrm{A}}(u_\xi)$
+where $h_{\mathrm{A}}$ was defined in (1) and $u_\xi$ in (3), and
+similarly $\tau_\xi := h_{\mathrm{B}}(u_\xi)$.
+
+\textbf{(10)} Show that neither Alice nor Bob have a winning strategy
+in the game $G(A)$.
+
+\textbf{(11)} Why doesn't this contradict the results seen in class?
+What can be said about the subset $A$?
+
+\end{otherlanguage}
+
+
 
 
 %