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

\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 \textcolor{red}{XXX} pages (page de garde incluse).
\else
Cet énoncé comporte \textcolor{red}{XXX} 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

\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 positif à chaque fois.  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}

\smallskip

\textbf{(2)} On souhaite maintenant ajouter une nouvelle option 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 profile $(\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}

\smallskip

\textbf{(3)} 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 ces équilibres de Nash.

\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

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.  Les piles sont numérotées $0$, $1$, $2$, etc.  Chaque
pile contient un certain nombre fini (entier naturel) de jetons.  Il
n'y a qu'un nombre fini de piles non vides (c'est-à-dire, ayant un
nombre non-nul de 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 plusieurs.  Par exemple, à partir de la position $(0,3,2)$ on
peut notamment jouer vers $(42,1000,1)$ ou bien vers $(0,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é.

\textbf{(1)} Montrer que le jeu qu'on vient de définir termine
forcément en temps fini, quelle que soit la position initiale.  (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}

\smallskip

Appelons « position totalement paire » une position dans laquelle le
nombre $n_i$ de jetons de chaque pile est pair.

\textbf{(2)} Montrer que tout coup joué depuis une position totalement
paire conduit nécessairement à une position qui n'est pas 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 qui n'est pas
totalement paire il existe au moins un coup conduisant à une position
totalement paire.

\begin{corrige}
Si $(n_0,\ldots,n_k)$ est une position qui n'est pas 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 qui n'est pas
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 qui n'est pas 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
qu'elle 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.)

\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)$ : donc forcément $b_i =
((n_i-1)\%2)$.  (On prendra 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 comparant insérant la formule $(n'_j\%2) = b_j$ 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), donc l'induction et l'ensemble de
la démonstration.
\end{corrige}



%
%
%

\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.  Aucune ne demande de raisonnement
très compliqué.)

\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$).

\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 aussi trouver $x$
différent de $w$.

\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).
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).
\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., $\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) pourquoi il existe $y \in \{0,1\}^{\mathbb{N}}$ tel que
$\sigma \ast y$ soit différent de tous les $a_\xi$.

\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$.)  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 préalablement définis des éléments
$(a_\xi)_{\xi<\alpha}$ et $(b_\xi)_{\xi<\alpha}$ de
$\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$, déduire en une
ligne des questions précédentes qu'il existe $b_\alpha$ qui soit de la
forme $\sigma_\alpha \ast y$ (pour un certain $y \in
\{0,1\}^{\mathbb{N}}$), mais qui soit différent de tous les $a_\xi$.
Expliquer pourquoi il existe $a_\alpha$ aussi 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$ mais aussi du
$b_\alpha$ qu'on vient de trouver.

\begin{corrige}
On pose $b_\alpha = \sigma_\alpha \ast y$, où l'existence de $y$ a été
prouvée en (6) (pour $\sigma = \sigma_\alpha$).

La construction de $a_\alpha$ 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
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_\alpha$ et $b_\alpha$ 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}$, on a $b_\xi = \sigma_\xi \ast y$
  pour un certain $y \in \{0,1\}^{\mathbb{N}}$,
\item pour tout $\xi < \mathfrak{c}$, on a $a_\xi = z \ast \tau_\xi$
  pour un certain $z \in \{0,1\}^{\mathbb{N}}$.
\end{itemize}
(C'est tout ce qu'on aura besoin de savoir pour la suite.)

\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, 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 exactement 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 ?

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



%
%
%
\end{document}