1 files changed, 1083 insertions, 0 deletions

diff --git a/controle-20250626.tex b/controle-20250626.tex
new file mode 100644
index 0000000..36f8319
--- /dev/null
+++ b/controle-20250626.tex
@@ -0,0 +1,1083 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[a4paper,margin=2.5cm]{geometry}
+\usepackage[french]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+\usepackage{wasysym}
+\usepackage{url}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{matrix,calc}
+\usepackage{hyperref}
+%
+%\externaldocument{notes-mitro206}[notes-mitro206.pdf]
+%
+\theoremstyle{definition}
+\newtheorem{comcnt}{Whatever}
+\newcommand\thingy{%
+\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
+\newcommand\exercise{%
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
+\renewcommand{\qedsymbol}{\smiley}
+%
+\newcommand{\outnb}{\operatorname{outnb}}
+\newcommand{\downstr}{\operatorname{downstr}}
+\newcommand{\precs}{\operatorname{precs}}
+\newcommand{\mex}{\operatorname{mex}}
+\newcommand{\id}{\operatorname{id}}
+\newcommand{\limp}{\Longrightarrow}
+\newcommand{\gr}{\operatorname{gr}}
+\newcommand{\rk}{\operatorname{rk}}
+\newcommand{\dur}{\operatorname{dur}}
+\newcommand{\fuzzy}{\mathrel{\|}}
+%
+\newcommand{\dblunderline}[1]{\underline{\underline{#1}}}
+%
+\renewcommand{\thefootnote}{\fnsymbol{footnote}}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+%
+\DeclareFontFamily{U}{manual}{} 
+\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
+\newcommand{\manfntsymbol}[1]{%
+    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
+\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
+\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
+  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
+%
+\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
+\newif\ifcorrige
+\corrigetrue
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
+{{\hbox{}\nobreak\hfill\checkmark}%
+\ifcorrige\par\smallbreak\else\egroup\par\fi}
+%
+%
+%
+\begin{document}
+\ifcorrige
+\title{CSC-4MI06-TP / MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}}
+\else
+\title{CSC-4MI06-TP / MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}}
+\fi
+\author{}
+\date{2025-06-26}
+\maketitle
+
+\pretolerance=8000
+\tolerance=50000
+
+\vskip1truein\relax
+
+\noindent\textbf{Consignes.}
+
+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
+imprimées, feuilles d'exercices, livres) est autorisé.
+
+L'usage des appareils électroniques est interdit.
+
+\medbreak
+
+% Durée : 2h
+
+\ifcorrige
+Ce corrigé comporte 11 pages (page de garde incluse).
+\else
+Cet énoncé comporte 6 pages (page de garde incluse).
+\fi
+
+\vfill
+{\noindent\tiny
+\immediate\write18{sh ./vc > vcline.tex}
+Git: \input{vcline.tex}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+
+\pagebreak
+
+
+%
+%
+%
+
+\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 :
+\begin{center}
+\begin{tabular}{r|ccc}
+$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux\\\hline
+Pierre&$0$&$-1$&$+1$\\
+Papier&$+1$&$0$&$-1$\\
+Ciseaux&$-1$&$+1$&$0$\\
+\end{tabular}
+\end{center}
+(Seul le gain d'Alice a été inscrit dans chaque case car les gains des
+deux joueurs sont opposés.)
+
+Quels sont tous les équilibres de Nash de ce jeu ?
+
+\begin{corrige}
+On a vu en cours qu'une stratégie optimale pour l'un ou l'autre joueur
+est $\frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} +
+\frac{1}{3}\text{Ciseaux}$ : de fait, la valeur du jeu est nulle car
+il est à somme nulle et \emph{symétrique}, et cette stratégie mixte
+$\frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} +
+\frac{1}{3}\text{Ciseaux}$ réalise au moins la valeur du jeu contre
+n'importe quelle option de l'adversaire.
+
+Réciproquement, si $p\,\text{Pierre} + q\,\text{Papier} +
+r\,\text{Ciseaux}$ est une stratégie optimale d'un joueur (avec
+$p,q,r$ positifs de somme $1$), son gain contre les trois stratégies
+pures de l'adversaire (à savoir $q-r$ contre Pierre, $r-p$ contre
+Papier et $p-q$ contre Ciseaux) doit être au moins égal à la valeur du
+jeu (soit $0$).  On a donc $q \geq r$ et $r \geq p$ et $p \geq q$, ce
+qui impose $p=q=r$ donc ils valent $\frac{1}{3}$.  Ceci montre que
+$\frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} +
+\frac{1}{3}\text{Ciseaux}$ est la seule stratégie optimale à ce jeu
+(quel que soit le joueur).
+
+Enfin, les équilibres de Nash d'un jeu à somme nuls sont ceux où les
+deux joueurs jouent une stratégie optimale, donc il n'y a qu'un seul
+ici, c'est celui où Alice et Bob jouent chacun
+$\frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} +
+\frac{1}{3}\text{Ciseaux}$.
+\end{corrige}
+
+\medskip
+
+\textbf{(2)} On souhaite maintenant ajouter une nouvelle option
+« Foobar » au jeu ci-dessus, c'est-à-dire qu'on considère le jeu en
+forme normale (toujours symétrique et à somme nulle) défini par la
+matrice de gains :
+\begin{center}
+\begin{tabular}{r|cccc}
+$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux&Foobar\\\hline
+Pierre&$0$&$-1$&$+1$&$-x$\\
+Papier&$+1$&$0$&$-1$&$-y$\\
+Ciseaux&$-1$&$+1$&$0$&$-z$\\
+Foobar&$x$&$y$&$z$&$0$\\
+\end{tabular}
+\end{center}
+(Les trois sous-questions qui suivent sont indépendantes.)
+
+\textbf{\hphantom{(2)} (a)} À quelle condition (nécessaire et
+suffisante) sur $x,y,z$ les équilibres de Nash trouvés en (1) sont-ils
+encore des équilibres de Nash pour ce nouveau jeu ?\quad\textbf{(b)} À
+quelle condition (nécessaire et suffisante) sur $x,y,z$ y a-t-il un
+équilibre de Nash où les deux joueurs jouent l'option Foobar (de façon
+certaine) ?\quad\textbf{(c)} À quelle condition (nécessaire et
+suffisante) sur $x,y,z$ y a-t-il un équilibre de Nash où les deux
+joueurs jouent $\frac{1}{2}\text{Pierre} + \frac{1}{2}\text{Foobar}$
+(i.e., Pierre ou Foobar chacun avec probabilité $\frac{1}{2}$) ?
+
+\begin{corrige}
+\textbf{(a)} En ajoutant une ligne et une colonne pour la stratégie
+mixte $M := \frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} +
+\frac{1}{3}\text{Ciseaux}$, le tableau devient :
+\begin{center}
+\begin{tabular}{r|cccc|c}
+$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux&Foobar&$M$\\\hline
+Pierre&$0$&$-1$&$+1$&$-x$&$0$\\
+Papier&$+1$&$0$&$-1$&$-y$&$0$\\
+Ciseaux&$-1$&$+1$&$0$&$-z$&$0$\\
+Foobar&$x$&$y$&$z$&$0$&$\frac{1}{3}(x+y+z)$\\\hline
+$M$&$0$&$0$&$0$&$-\frac{1}{3}(x+y+z)$&$0$\\
+\end{tabular}
+\end{center}
+Le profil $(M,M)$ est un équilibre de Nash lorsque $0$ est le plus
+grand nombre de sa colonne et le plus petit de sa ligne, c'est-à-dire
+exactement lorsque $x+y+z \leq 0$.
+
+\textbf{(b)} Le profil $(\text{Foobar}, \text{Foobar})$ est un
+équilibre de Nash lorsque $0$ est le plus grand nombre de sa colonne
+et le plus petit de sa ligne, c'est-à-dire lorsque $x,y,z$ sont tous
+positifs.
+
+\textbf{(c)} En ajoutant une ligne et une colonne pour la stratégie
+mixte $N := \frac{1}{2}\text{Pierre} +
+\frac{1}{2}\text{Foobar}$, le tableau devient :
+\begin{center}
+\begin{tabular}{r|cccc|c}
+$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux&Foobar&$N$\\\hline
+Pierre&$0$&$-1$&$+1$&$-x$&$-\frac{x}{2}$\\[0.7ex]
+Papier&$+1$&$0$&$-1$&$-y$&$-\frac{y-1}{2}$\\[0.7ex]
+Ciseaux&$-1$&$+1$&$0$&$-z$&$-\frac{z+1}{2}$\\[0.7ex]
+Foobar&$x$&$y$&$z$&$0$&$\frac{x}{2}$\\[0.7ex]\hline
+$N$&$\frac{x}{2}$&$\frac{y-1}{2}$&$\frac{z+1}{2}$&$-\frac{x}{2}$&$0$\\
+\end{tabular}
+\end{center}
+Le profil $(N,N)$ est un équilibre de Nash lorsque $0$ est le plus
+grand nombre de sa colonne et le plus petit de sa ligne, c'est-à-dire
+exactement lorsque $x=0$ et $y\geq 1$ et $z\geq -1$.
+\end{corrige}
+
+\medskip
+
+\textbf{(3)} On change de jeu : on reprend maintenant la matrice de
+gains écrite en (1), mais cette fois les gains des deux joueurs seront
+\emph{égaux} au lieu d'être opposés (ce n'est donc plus un jeu à somme
+nulle ! les joueurs sont alliés et non plus adversaires).  Le tableau
+donne la valeur du gain commun aux deux joueurs.
+
+\textbf{\hphantom{(3)} (a)} Montrer que les équilibres de Nash trouvés
+en (1) sont encore des équilibres de Nash de ce nouveau
+jeu.\quad\textbf{(b)} Donner au moins un équilibre de Nash différent
+de ceux-ci.  Commenter brièvement quant à la différence de gain
+éventuelle entre les équilibres de Nash trouvés en (a) et (b).
+
+\begin{corrige}
+\textbf{(a)} En ajoutant une ligne et une colonne pour la stratégie
+mixte $M := \frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} +
+\frac{1}{3}\text{Ciseaux}$, le tableau devient :
+\begin{center}
+\begin{tabular}{r|ccc|c}
+$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux&$M$\\\hline
+Pierre&$0$&$-1$&$+1$&$0$\\
+Papier&$+1$&$0$&$-1$&$0$\\
+Ciseaux&$-1$&$+1$&$0$&$0$\\\hline
+$M$&$0$&$0$&$0$&$0$\\
+\end{tabular}
+\end{center}
+Le profil $(M,M)$ est bien un équilibre de Nash car $0$ est le plus
+grand nombre de sa colonne et le plus grand de sa ligne, ce qui est
+bien le cas ici.
+
+\textbf{(b)} Il y a des équilibres de Nash évidents en stratégies
+pures, à savoir tous les $+1$ du tableau : par exemple, si Alice joue
+Papier et Bob joue Pierre, ceci constitue bien un équilibre de Nash
+(car $+1$ est le plus grand nombre de sa colonne et le plus grand de
+sa ligne).
+
+L'équilibre de Nash trouvé en (a) correspond intuitivement à une
+situation où les joueurs ne sont pas synchronisés : ils jouent une
+stratégie équilibrée entre les trois options.  Dans ce jeu coopératif,
+ce n'est pas du tout optimal, le gain espéré étant $0$, mais aucun n'a
+d'intérêt à privilégier unilatéralement une des options tant que
+l'autre continue à jouer cette stratégie.  Dans le cas trouvé en (b),
+en revanche, les joueurs se sont synchronisés sur une stratégie qui
+les arrange tous les deux, réalisant le gain qui est visiblement le
+meilleur possible ici.
+\end{corrige}
+
+
+%
+%
+%
+
+\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 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
+signifie implicitement que toutes les piles $\geq k$ sont vides.
+
+Un coup d'un joueur consiste à retirer \emph{exactement un} jeton
+d'une certaine pile $i$, de son choix, et d'ajouter \emph{autant qu'il
+le souhaite} (y compris $0$) jetons à chacune des piles $j<i$, y
+compris ajouter des nombres différents à des piles différentes.  Par
+exemple, à partir de la position $(0,3,2)$ on peut notamment jouer
+vers $(42,1000,1)$ ou bien vers $(0,2,2)$ ou encore vers
+$(696\,729\,600,2,2)$.
+
+Comme d'habitude, le joueur qui ne peut pas jouer a perdu,
+c'est-à-dire que celui qui prend le dernier jeton a gagné.
+
+\medskip
+
+\textbf{(1)} Montrer que le jeu qu'on vient de définir termine
+forcément en temps fini, quelle que soit la position initiale et quels
+que soient les coups effectués par les joueurs.  (On justifiera
+soigneusement.)
+
+\begin{corrige}
+On associe à la position $(n_0,\ldots,n_k)$ l'ordinal $\omega^k\cdot
+n_k + \cdots + \omega\cdot n_1 + n_0$ (remarquons qu'il s'agit d'une
+écriture en forme normale de Cantor).  Un coup du jeu consiste à
+remplacer un certain $n_i$ par $n_i-1$ et tous les $n_j$ avec $j<i$
+par des $n'_j$ où $n'_j \geq n_j$.  Le tuple
+$(n'_0,\ldots,n'_{i-1},n_i-1,n_{i+1},\ldots,n_k)$ qui résulte du coup
+est lexicographiquement inférieur à $(n_0,\ldots,n_k)$ pour l'ordre
+lexicographique donnant le poids le plus fort aux $n_j$ avec $j$
+grand, ce qui signifie justement que l'ordinal qu'on vient de lui
+associer a diminué strictement.  Comme toute suite strictement
+décroissante d'ordinaux est finie, le jeu termine en temps fini,
+\end{corrige}
+
+\textbf{Définition :} Appelons « position totalement paire » une
+position dans laquelle le nombre $n_i$ de jetons de chaque pile est
+pair, et « position non totalement paire » une position dans laquelle
+au moins un des $n_i$ est impair.
+
+\textbf{(2)} Montrer que tout coup joué depuis une position totalement
+paire conduit nécessairement à une position non totalement paire.
+
+\begin{corrige}
+On a retiré un jeton d'une certaine pile $i$, donc si le nombre de
+jetons était pair avant le coup, il est devenu impair, et la position
+n'est plus totalement paire.
+\end{corrige}
+
+\textbf{(3)} Montrer que depuis toute position non totalement paire il
+existe au moins un coup conduisant à une position totalement paire.
+
+\begin{corrige}
+Si $(n_0,\ldots,n_k)$ est une position non totalement paire, il existe
+un $n_i$ impair : soit $i$ le plus grand possible tel que $n_i$ soit
+impair (tous les $n_j$ avec $j>i$ sont donc pairs).  Le coup
+consistant à retirer un jeton de la pile $i$ (qui passe donc à $n_i-1$
+jetons, lequel nombre est pair) et à en ajouter un à toutes les piles
+$j<i$ telles que $n_j$ soit impair (qui passent donc à $n_j+1$ jetons,
+lequel nombre est pair) est légal selon les règles du jeu, et conduit
+à une position totalement paire.
+\end{corrige}
+
+\textbf{(4)} En déduire quelles sont les positions du jeu dans
+lesquelles le premier joueur a une stratégie gagnante, et quelles sont
+celles dans lesquelles le second joueur en a une.  (On justifiera très
+soigneusement.)
+
+\begin{corrige}
+Considérons la stratégie $\sigma$ consistant à jouer vers une position
+totalement paire si on est dans une position qui ne l'est pas (c'est
+possible par la question (3)) et à retirer un jeton quelconque sinon
+(et bien sûr, à capituler s'il n'y a plus de jeton).  Le joueur qui
+applique cette stratégie $\sigma$ depuis une position non totalement
+paire va gagner : chacun de ces coups mènera à une position totalement
+paire et son adversaire va forcément en sortir au coup suivant, donc
+(par une récurrence immédiate) le joueur dont on parle sera toujours
+face à une position non totalement paire, et gagnera car le jeu ne
+peut pas durer indéfiniment longtemps (question (1)).  Ceci montre que
+les positions qui ne sont pas totalement paires sont gagnantes pour le
+premier joueur (ce sont des positions N) et que celles qui sont
+totalement paires sont gagnantes pour le second joueur (ce sont des
+positions P).
+
+Si on préfère, on peut aussi rédiger ainsi : on a vu au (1) que le
+graphe des positions du jeu est bien-fondé.  On peut donc montrer par
+induction bien-fondée sur la position $x$ que $x$ est une position P
+si et seulement si elle est totalement paire.  Si $x$ est totalement
+paire, aucun de ses voisins sortants n'est totalement pair
+d'après (2), donc ils sont tous N par l'hypothèse d'induction, donc
+$x$ est P ; et réciproquement, si $x$ est P, tous ses voisins sont N,
+donc par hypothèse d'induction aucun n'est totalement pair, donc $x$
+n'est pas totalement pair par (la contraposée de) la question (3).
+Ceci conclut l'induction.
+\end{corrige}
+
+\textbf{(5)} Calculer, en fonction de $n$, la valeur de Grundy de la
+position $(n)$ (c'est-à-dire s'il n'y a que la pile numérotée $0$, et
+que celle-ci comporte $n$ jetons).
+
+\begin{corrige}
+On a $\gr((0)) = 0$ car c'est un puits, et $\gr((1)) = \mex\{0\} = 1$
+puis $\gr((2)) = \mex\{1\} = 0$, et ainsi de suite.
+
+Pour simplifier la notation dans les réponses ultérieures, notons
+$(n\%2)$ l'entier valant $0$ si $n$ est pair et $1$ si $n$ est impair.
+
+Une récurrence sur $n$ permet de prouver que $\gr((n)) = (n\%2)$ : en
+effet, si $n$ est pair, $\gr((n)) = \mex(\{\gr((n-1))\}) = \mex\{1\} =
+0$, et si $n$ est impair, $\gr((n)) = \mex(\{\gr((n-1))\}) = \mex\{0\}
+= 1$.
+\end{corrige}
+
+\textbf{(6)} En déduire la valeur de Grundy des posititions $(0,1)$ et
+$(1,1)$, puis plus généralement de $(n,1)$ en fonction de $n$.
+
+\begin{corrige}
+On a $\gr((0,1)) = \mex\{\gr((n)) : n\in\mathbb{N}\} = \mex\{0,1\} =
+2$.  On en déduit que $\gr((1,1)) = \mex(\{\gr((n+1)) :
+n\in\mathbb{N}\} \cup \{\gr((0,1))\}) = \mex\{0,1,2\} = 3$.  On
+vérifie alors par récurrence sur $n$ que $\gr((n,1)) = 2$ si $n$ est
+pair et $\gr((n,1)) = 3$ si $n$ est impair (i.e., $2+(n\%2)$, si on
+veut) : en effet, si $n$ est pair, $\gr((n,1)) = \mex(\{\gr((m)) :
+m\geq n\} \cup \{\gr((n-1,1))\}) = \mex(\{0,1,3\}) = 2$, et si $n$ est
+impair, $\gr((n,1)) = \mex(\{\gr((m)) : m\geq n\} \cup
+\{\gr((n-1,1))\}) = \mex(\{0,1,2\}) = 3$.
+\end{corrige}
+
+\textbf{(7)} En déduire la valeur de Grundy des positions $(0,2)$ et
+$(1,2)$, plus plus généralement de $(n_0,n_1)$ en fonction
+de $n_0,n_1$.
+
+\begin{corrige}
+On a $\gr((0,2)) = \mex\{\gr((n,1)) : n\in\mathbb{N}\} = \mex\{2,3\} =
+0$ (ce qu'on peut aussi conclure du fait que $(0,2)$ est totalement
+paire).  On en déduit que $\gr((1,2)) = \mex(\{\gr((n+1,1)) :
+n\in\mathbb{N}\} \cup \{\gr((0,2))\}) = \mex\{2,3,0\} = 1$.
+
+On peut alors mener une récurrence sur $n_1$ et, pour chaque $n_1$,
+sur $n_0$ (ou, si on préfère, une induction transfinie sur l'ordinal
+$\omega\cdot n_1 + n_0$) pour montrer : $\gr((n_0,n_1)) = 2(n_1\%2) +
+(n_0\%2)$.  En effet,
+\begin{itemize}
+\item si $n_0$ et $n_1$ sont pairs, on a $\gr((n_0,n_1)) =
+  \mex(\{\gr((m,n_1-1)) : m\geq n_0\} \cup \{\gr((n_0-1,n_1))\}) =
+  \mex\{2,3,1\} = 0$ (ce qu'on peut aussi conclure du fait que
+  $(n_0,n_1)$ est totalement paire),
+\item si $n_0$ est impair et $n_1$ pair, on a $\gr((n_0,n_1)) =
+  \mex(\{\gr((m,n_1-1)) : m\geq n_0\} \cup \{\gr((n_0-1,n_1))\}) =
+  \mex\{2,3,0\} = 1$,
+\item si $n_0$ est pair et $n_1$ impair, on a $\gr((n_0,n_1)) =
+  \mex(\{\gr((m,n_1-1)) : m\geq n_0\} \cup \{\gr((n_0-1,n_1))\}) =
+  \mex\{0,1,3\} = 2$,
+\item si $n_0$ et $n_1$ sont impairs, on a $\gr((n_0,n_1)) =
+  \mex(\{\gr((m,n_1-1)) : m\geq n_0\} \cup \{\gr((n_0-1,n_1))\}) =
+  \mex\{0,1,2\} = 3$.
+\end{itemize}
+Ceci couvre tous les cas et conclut la récurrence.
+\end{corrige}
+
+\textbf{(8)} En déduire la valeur de Grundy de la position $(0,0,1)$.
+
+\begin{corrige}
+On a $\gr((0,0,1)) = \mex\{\gr((n_0,n_1)) : n_0,n_1\in\mathbb{N}\} =
+\mex\{0,1,2,3\} = 4$.
+\end{corrige}
+
+\textbf{(9)} Conjecturer une formule générale pour la valeur de Grundy
+d'une position $(n_0,n_1,\ldots,n_k)$ quelconque.
+
+\begin{corrige}
+Les résultats précédents suggèrent que $\gr((n_0,n_1,\ldots,n_k))$ ne
+dépend que de la parité de $n_0,\ldots,n_k$, c'est-à-dire de ce qu'on
+a noté $(n_i\%2)$.  Les valeurs calculées jusqu'à présent inspirent à
+penser que
+\[
+\gr((n_0,n_1,\ldots,n_k)) = 2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2)
+\]
+(C'est-à-dire qu'on lit les $(n_i\%2)$ comme un nombre en binaire et
+qu'il donne la valeur de Grundy.)
+\end{corrige}
+
+\textbf{(10)} Démontrer cette formule.  (Cette question est plus
+difficile, et il peut être opportun de la garder pour la fin.  On
+pourra s'inspirer de la démonstration faite en cours du calcul de la
+valeur de Grundy pour le jeu de nim.)
+
+\begin{corrige}
+On va montrer par induction transfinie sur l'ordinal $\omega^k\cdot
+n_k + \cdots + \omega\cdot n_1 + n_0$ associé à la position
+$(n_0,n_1,\ldots,n_k)$ (ou, ce qui revient essentiellement au même,
+par induction bien-fondée sur la position elle-même) que la formule
+ci-dessus est valable.
+
+Comme $\gr((n_0,n_1,\ldots,n_k))$ est le $\mex$ de l'ensemble $S$ des
+$\gr((n'_0,n'_1,\ldots,n'_k))$ où $(n'_0,n'_1,\ldots,n'_k)$ parcourt
+tous les voisins sortants de $(n_0,n_1,\ldots,n_k)$, pour montrer que
+$\gr((n_0,n_1,\ldots,n_k)) = 2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) +
+(n_0\%2)$, il s'agit de vérifier (A) que $2^k\,(n_k\%2) + \cdots +
+2\,(n_1\%2) + (n_0\%2)$ n'est pas dans $S$ et (B) que tout nombre $r <
+2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2)$ est dans $S$.  Or par
+hypothèse d'induction, les éléments de $S$ sont les $2^k\,(n'_k\%2) +
+\cdots + 2\,(n'_1\%2) + (n'_0\%2)$ avec $(n'_0,n'_1,\ldots,n'_k)$
+voisin sortant de $(n_0,n_1,\ldots,n_k)$.
+
+Montrons (A) : on sait qu'un des $n'_i$ vaut $n_i-1$.  Ceci assure que
+$(n'_i\%2) \neq (n_i\%2)$, donc par unicité des écritures binaires,
+que $2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2)$ est différent de
+$2^k\,(n'_k\%2) + \cdots + 2\,(n'_1\%2) + (n'_0\%2)$ (au moins un bit
+diffère).  Ceci conclut le (A).
+
+Montrons (B) : si $r < 2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) +
+(n_0\%2)$, appelons $r = 2^k\,b_k + \cdots + 2\,b_1 + b_0$ son
+écriture binaire, où $b_j \in \{0,1\}$.  Soit $i$ le plus grand
+possible tel que $b_i \neq (n_i\%2)$ : alors $b_i = ((n_i-1)\%2)$.
+(On prendra aussi note du fait que $b_j = (n_j\%2)$ si $j>i$ par
+maximalité de $i$.)  Définissons les $n'_j$ comme suit : on pose $n'_j
+= n_j$ si $j>i$, et $n'_i = n_i-1$, et enfin, pour $j<i$, on pose
+$n'_j = n_j + ((n_j+b_j)\%2)$.  Par construction (comme $n'_j = n_j$
+si $j>i$ et $n'_i = n_i$ et $n'_j \geq n_j$ si $j\leq i$), le
+$(n'_0,n'_1,\ldots,n'_k)$ qu'on vient de définir est bien un voisin
+sortant de $(n_0,n_1,\ldots,n_k)$.  Par ailleurs, $(n'_j\%2) = b_j$ :
+en effet, pour $j>i$ cela résulte de $b_j = (n_j\%2)$ et $n'_j =
+n_j$ ; pour $j=i$ cela résulte de $b_i = ((n_i-1)\%2)$ et $n'_i =
+n_i-1$ ; et pour $j<i$ cela résulte du fait que $n'_j = n_j +
+((n_j+b_j)\%2)$ est congru à $n_j + n_j + b_j$ donc à $b_j$
+modulo $2$.  En insérant la formule $b_j = (n'_j\%2)$ qu'on vient de
+montrer dans $r = 2^k\,b_k + \cdots + 2\,b_1 + b_0$, on voit que $r =
+2^k\,(n'_k\%2) + \cdots + 2\,(n'_1\%2) + (n'_0\%2)$. qui est donc
+dans $S$.  Ceci conclut le (B), l'induction, et l'ensemble de la
+démonstration.
+\end{corrige}
+
+
+
+%
+%
+%
+
+\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)
+:= G_{\{0,1\}}(A)$ ne soit pas déterminé (i.e., tel qu'aucun des deux
+joueurs n'ait de stratégie gagnante).
+
+(La démonstration a été découpées en questions admettant des réponses
+courtes, parfois d'une seule ligne.)
+
+\medskip
+
+\textbf{(1)} Montrer qu'il existe une bijection $h_{\mathrm{A}}$
+(resp. $h_{\mathrm{B}}$) entre $\{0,1\}^{\mathbb{N}}$ et l'ensemble
+des stratégies d'Alice (resp. de Bob) au jeu $G(A)$.
+(\emph{Indication :} on pourra expliquer rapidement pourquoi il existe
+une bijection entre $\mathbb{N}$ et l'ensemble des positions où c'est
+à Alice, resp. à Bob, de jouer.)
+
+\begin{corrige}
+L'ensemble $P_{\mathrm{A}}$ des positions où c'est à Alice de jouer
+sont les suites binaires finies de longueur paires : on peut les
+énumérer dans l'ordre de longueur et, pour chaque longueur, dans
+l'ordre lexicographique ($()$, $00$, $01$, $10$, $11$, $0000$, $0001$,
+$0010$, etc.).  Ceci fournit une bijection $g_{\mathrm{A}}\colon
+\mathbb{N} \to P_{\mathrm{A}}$ : on en déduit une bijection
+$h_{\mathrm{A}}\colon \{0,1\}^{P_{\mathrm{A}}} \to
+\{0,1\}^{\mathbb{N}}$ par $h_{\mathrm{A}}(u) = (n \mapsto
+u(g_{\mathrm{A}}(n)))$.  Or $\{0,1\}^{P_{\mathrm{A}}}$ est exactement
+l'ensemble des stratégies d'Alice (ce sont les fonctions qui à une
+position où c'est à Alice de jouer associent un coup d'Alice).
+
+Exactement le même raisonnement fournit le résultat pour
+$h_{\mathrm{B}}$ : il faut simplement considérer cette fois l'ensemble
+$P_{\mathrm{B}}$ des positions où c'est à Bob de jouer, qui sont les
+suites binaires finies de longueur paires ($0$, $1$, $000$, $001$,
+etc.).
+\end{corrige}
+
+\textbf{(2)} On \emph{admet}\footnote{Plus généralement, on peut
+montrer qu'il existe une relation de bon ordre sur n'importe quel
+ensemble (théorème du bon ordre).} qu'il existe une relation de bon
+ordre $\preceq$ sur $\{0,1\}^{\mathbb{N}}$.  En déduire qu'il existe
+un ordinal $\gamma$ et une bijection $\xi \mapsto u_\xi$ entre
+l'ensemble $\{\xi < \gamma\}$ des ordinaux plus petits que $\gamma$ et
+l'ensemble $\{0,1\}^{\mathbb{N}}$ (autrement dit, les $u_\xi$ sont
+deux à deux distincts et $\{u_\xi : \xi < \gamma\} =
+\{0,1\}^{\mathbb{N}}$).
+
+\begin{corrige}
+Soit $W$ l'ensemble $\{0,1\}^{\mathbb{N}}$ muni du bon ordre $\preceq$
+qu'on a supposé exister, et soit $\gamma = \#W$ son ordinal.  À tout
+élément $w$ de $W$ on associe un ordinal $\#w$ qui est l'ordinal de
+l'ensemble $\{x \in W : x \prec w\}$ des prédécesseurs stricts
+de $w$ : ceci constitue une bijection strictement croissante entre $W$
+et l'ensemble $\{\xi < \gamma\}$ des ordinaux $<\gamma$ ; on appelle
+alors $\xi \mapsto u_\xi$ la bijection réciproque.
+
+(Si on préfère : l'ordinal de $W$ est le même que l'ordinal de $\{\xi
+< \gamma\}$, à savoir $\gamma$, donc il y a une — unique — bijection
+croissante entre les deux, et on appelle $\xi \mapsto u_\xi$ sa
+réciproque.)
+\end{corrige}
+
+\textbf{(3)} Expliquer en une ligne, pourquoi il existe un plus petit
+ordinal $\gamma$ tel qu'il existe une surjection $\xi \mapsto u_\xi$
+de l'ensemble $\{\xi < \gamma\}$ des ordinaux plus petits que $\gamma$
+sur l'ensemble $\{0,1\}^{\mathbb{N}}$.
+
+\begin{corrige}
+En une ligne : on vient de montrer qu'un tel $\gamma$ existe, donc il
+y en a un plus petit.
+
+(En un tout petit peu plus détaillé : comme les ordinaux sont
+bien-ordonnés, dès qu'il existe un ordinal tel que (quelque chose),
+alos il y en a un plus petit ; or il existe un ordinal tel que $\{\xi
+< \gamma\}$ se surjecte sur $\{0,1\}^{\mathbb{N}}$ — on vient de voir
+l'existence d'une telle bijection —, donc il en existe un plus petit.)
+\end{corrige}
+
+\textbf{Définition :} On notera\footnote{Il s'agit ici d'un ‘c’
+gothique (cet ordinal s'appelle le « cardinal du continu ») ; si on ne
+veut pas écrire de ‘c’ gothique on pourra, par exemple, faire un ‘c’
+souligné.}  $\mathfrak{c}$ l'ordinal dont on vient de justifier
+l'existence, i.e., le plus petit $\gamma$ tel qu'on puisse écrire
+$\{u_\xi : \xi < \gamma\} = \{0,1\}^{\mathbb{N}}$ pour une certaine
+fonction $\xi \mapsto u_\xi$, qu'on fixe dans la suite.
+
+\textbf{(4)} \textbf{(a)} Si $(v_\xi)_{\xi<\alpha}$ sont des éléments
+quelconques de $\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$,
+expliquer en une ligne pourquoi il existe un élément $x$ de
+$\{0,1\}^{\mathbb{N}}$ différent de tous
+les $v_\xi$.\quad\textbf{(b)} Si $w$ est encore un élément de
+$\{0,1\}^{\mathbb{N}}$, expliquer pourquoi on peut trouver $x$ qui
+soit différent de $w$ (et toujours différent des $v_\xi$).
+
+\begin{corrige}
+\textbf{(a)} En une ligne : $\xi \mapsto v_\xi$ n'est pas surjective
+par minimalité de $\mathfrak{c}$.
+
+\textbf{(b)} Si $\alpha$ est fini, il est évident qu'on peut trouver
+$x$ différent de tous les $v_\xi$ et de $w$ (qui sont en nombre fini),
+parce que $\{0,1\}^{\mathbb{N}}$ est infini.  Si $\alpha$ est infini,
+alors $\alpha = 1 + \alpha$ donc on n'a qu'à poser $v'_0 = w$ et
+$v'_{1+\xi} = v_\xi$ pour tout $\xi < \alpha$, et appliquer (a), vu
+que $\{v'_\xi : \xi<\alpha\} = \{v_\xi : \xi<\alpha\} \cup \{w\}$.
+\end{corrige}
+
+\textbf{Définition :} Si $\sigma$ est une stratégie d'Alice au jeu
+$G(A)$ et $y \in \{0,1\}^{\mathbb{N}}$, on note $\sigma \ast y$ la
+confrontation dans laquelle Alice joue selon $\sigma$ et Bob joue
+simplement les termes successifs de $y$ (indépendamment de ce que fait
+Alice ; i.e.,\footnote{Pour enlever le moindre doute : $\sigma \ast y$
+est la suite $(t_n)_{n\in\mathbb{N}}$ définie par récurrence par :
+$t_{2m} = \sigma((t_0,\ldots,t_{2m-1}))$ et $t_{2m+1} = y_m$.} $\sigma
+\ast y$ est une suite binaire dont la suite des termes impairs, ceux
+joués par Bob, est donnée par $y$, tandis qu'Alice joue les termes
+pairs selon la stratégie $\sigma$).  Symétriquement, si $\tau$ est une
+stratégie de Bob et $z \in \{0,1\}^{\mathbb{N}}$, on définit $z \ast
+\tau$ comme la confrontation dans laquelle Alice joue les termes de la
+suite $z$ et Bob joue selon $\tau$.
+
+\textbf{(5)} Si $\sigma$ est une stratégie d'Alice, expliquer en une
+ligne pourquoi la fonction $y \mapsto \sigma \ast y$ (de
+$\{0,1\}^{\mathbb{N}}$ vers $\{0,1\}^{\mathbb{N}}$) est injective.
+
+\begin{corrige}
+En une ligne : si $\sigma \ast y = \sigma \ast y'$, ils ont les mêmes
+termes impairs, donc $y = y'$.
+
+(Si on préfère : $y$ se retrouve à partir de $\sigma \ast y$ comme la
+suite de ses termes impairs.)
+\end{corrige}
+
+\textbf{(6)} Si $(a_\xi)_{\xi<\alpha}$ sont des éléments quelconques
+de $\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$, déduire de
+(4)(a) et (5) qu'il existe $y \in \{0,1\}^{\mathbb{N}}$ tel que
+$\sigma \ast y$ soit différent de tous les $a_\xi$ pour $\xi<\alpha$.
+
+\begin{corrige}
+Pour chaque $\xi < \alpha$, si $a_\xi$ est de la forme $\sigma \ast
+v$, appelons $v_\xi$ le $v$ en question (qui est unique d'après (5)),
+et sinon, soit $v_\xi$ quelconque (par exemple la suite nulle).  (Ou,
+si on préfère, on peut appeler $v_\xi$ la suite des termes impairs
+de $a_\xi$ dans tous les cas.)
+
+D'après (4)(a), il existe $y \in \{0,1\}^{\mathbb{N}}$ qui est
+différent de tous les $v_\xi$ pour $\xi < \alpha$.  Alors $\sigma \ast
+y$ ne peut pas être égal à $a_\xi$, car si c'était le cas,
+c'est-à-dire $a_\xi = \sigma \ast y$, on aurait $\sigma \ast v_\xi =
+\sigma \ast y$, donc $v_\xi = y$ par (5), contredisant la définition
+de $y$.
+\end{corrige}
+
+\textbf{Supposition :} Dans les questions (7) à (9), on suppose que
+$(\sigma_\xi)_{\xi<\mathfrak{c}}$ sont des stratégies d'Alice et
+$(\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 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é
+prouvée en (6) (pour $\sigma = \sigma_\alpha$).
+
+La construction de $a'$ est symétrique, il n'y a qu'à remarquer que $z
+\mapsto z \ast \tau$ est injective, car si $z \ast \tau = z' \ast
+\tau$, ils ont les mêmes termes pairs, donc $z = z'$, tout le reste
+est presque pareil.  La seule chose qui diffère est qu'on a un élément
+de plus à éviter ($b_\alpha$), mais la question (4)(b) donne justement
+ce point
+\end{corrige}
+
+On \emph{admettra} qu'il ne pose pas de problème pour
+\emph{choisir}\footnote{Ceci constitue une utilisation de l'axiome du
+choix (qui a d'ailleurs déjà été utilisé dans ce qu'on a admis à la
+question (2)).}  de tels $a'$ et $b'$ en fonction de tous les autres
+paramètres.
+
+\textbf{(8)} Déduire de tout ce qui précède qu'il existe $(a_\xi)_{\xi
+  < \mathfrak{c}}$ et $(b_\xi)_{\xi < \mathfrak{c}}$ tels que :
+\begin{itemize}
+\item aucun des $a_\xi$ n'est égal à aucun des $b_\zeta$ (i.e., pour
+  tous $\xi<\mathfrak{c}$ et tout $\zeta<\mathfrak{c}$, on a $a_\xi
+  \neq b_\zeta$),
+\item pour tout $\xi < \mathfrak{c}$, il existe $y \in
+  \{0,1\}^{\mathbb{N}}$ tel que $b_\xi = \sigma_\xi \ast y$,
+\item pour tout $\xi < \mathfrak{c}$, il existe $z \in
+  \{0,1\}^{\mathbb{N}}$ tel que $a_\xi = z \ast \tau_\xi$.
+\end{itemize}
+(C'est tout ce qu'on aura besoin de savoir pour les questions
+suivantes.)
+
+\begin{corrige}
+On définit $(a_\xi)_{\xi < \mathfrak{c}}$ et $(b_\xi)_{\xi <
+  \mathfrak{c}}$ par induction transfinie sur $\xi$ : si $(a_\xi)_{\xi
+  < \alpha}$ et $(b_\xi)_{\xi < \alpha}$ ont déjà été définis, pour
+$\alpha < \mathfrak{c}$, alors on choisit $a_\alpha$ et $b_\alpha$
+comme l'existence a été montrée en (7).
+
+Pour vérifier le premier point, on distingue les cas $\xi < \zeta$ et
+$\zeta \leq \xi$.  Dans le premier cas, la définition même de
+$b_\zeta$ était d'être différent de tous les $a_\xi$ pour $\xi <
+\zeta$ ; dans le second cas, la définition même de $a_\xi$ était
+d'être différent de tous les $b_\zeta$ pour $\zeta < \xi$ et aussi de
+$b_\xi$.
+
+Les deux points suivants font partie de la définition des $b_\xi$ et
+des $a_\xi$, il n'y a rien de plus à dire.
+\end{corrige}
+
+\textbf{Définition :} Appelons maintenant $A = \{a_\xi : \xi <
+\mathfrak{c}\}$ l'ensemble des $a_\xi$ qu'on vient de construire
+en (8).
+
+\textbf{(9)} Montrer que, quel que soit $\xi$, la stratégie $\tau_\xi$
+n'est pas gagnante pour Bob au jeu $G(A)$.  Montrer que la stratégie
+$\sigma_\xi$ n'est pas gagnante pour Alice à ce même jeu (attention,
+ce n'est pas complètement symétrique vu que $A$ est l'ensemble
+des $a_\alpha$).
+
+\begin{corrige}
+Supposons par l'absurde que la stratégie $\tau_\xi$ soit gagnante pour
+Bob : mais on a vu que $a_\xi = z \ast \tau_\xi$ pour un certain $z$,
+donc $z \ast \tau_\xi$ est dans $A$, c'est-à-dire qu'Alice gagne la
+confrontation, ce qui contredit le fait que $\tau_\xi$ soit gagnante
+pour Bob.
+
+Supposons par l'absurde que la stratégie $\sigma_\xi$ soit gagnante
+pour Alice : mais on a vu que $b_\xi = \sigma_\xi \ast y$ pour un
+certain $y$ ; or $b_\xi$ ne peut pas être dans $A$ car il serait alors
+égal à l'un des $a_\zeta$ et on a vu que ce n'était pas le cas.
+C'est-à-die que Bob gagne la confrontation, ce qui contredit le fait
+que $\sigma_\xi$ soit gagnante pour Bob.
+\end{corrige}
+
+\textbf{Définition :} Posons maintenant $\sigma_\xi :=
+h_{\mathrm{A}}(u_\xi)$ où $h_{\mathrm{A}}$ a été définie en (1) et
+$u_\xi$ en (3), et de même $\tau_\xi := h_{\mathrm{B}}(u_\xi)$.
+
+\textbf{(10)} Montrer que ni Alice ni Bob n'ont de stratégie gagnante
+au jeu $G(A)$.
+
+\begin{corrige}
+La fonction $h_{\mathrm{A}}$ est surjective par définition,
+c'est-à-dire que n'importe quel stratégie d'Alice est de la forme
+$h_{\mathrm{A}}(u)$ pour un certain $u \in \{0,1\}^{\mathbb{N}}$ ;
+mais $\xi \mapsto u_\xi$ est surjective, c'est-à-dire que tout $u \in
+\{0,1\}^{\mathbb{N}}$ est de la forme $u_\xi$ pour un certain $\xi$.
+Autrement dit, n'importe quelle stratégie d'Alice est une des
+$\sigma_\xi$.  Symétriquement, n'importe quelle stratégie de Bob est
+une des $\tau_\xi$.
+
+On vient de voir que ni $\sigma_\xi$ ni $\tau_\xi$ ne peut être une
+stratégie gagnante pour le joueur concerné : donc il n'y a aucune
+stratégie gagnante à ce jeu.
+\end{corrige}
+
+\textbf{(11)} Pourquoi ceci ne contredit pas les résultats vu en
+cours ?  Que dire de la partie $A$ ?
+
+\begin{corrige}
+Les résultats du cours concernent les parties ouvertes, fermées, ou
+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}
+
+
+
+
+%
+%
+%
+\end{document}