path: root/controle-20250626.tex

%% 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}