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.

\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

Dans cet exercice, on fixe un ordinal $\varepsilon$ tel que
$\varepsilon = \omega^\varepsilon$.

\textbf{(1)} Montrer que $\varepsilon^\varepsilon =
\omega^{\varepsilon^2}$ et que $\varepsilon \cdot
\varepsilon^\varepsilon$ vaut la même chose.

\begin{corrige}
On a $\varepsilon^\varepsilon = (\omega^\varepsilon)^\varepsilon =
\omega^{\varepsilon\cdot\varepsilon} = \omega^{\varepsilon^2}$, ce qui
montre la première égalité.

Quant à la seconde, $\varepsilon \cdot \varepsilon^\varepsilon =
\varepsilon^1 \cdot \varepsilon^\varepsilon =
\varepsilon^{1+\varepsilon} = \varepsilon^\varepsilon$ car
$1+\varepsilon = \varepsilon$ (de façon générale, $1+\gamma = \gamma$
pour tout ordinal $\gamma\geq\omega$ comme il résulte par exemple du
fait qu'on peut écrire $\gamma = \omega+\gamma'$ donc $1+\gamma =
1+\omega+\gamma' = \omega+\gamma' = \gamma$ ; et le fait qu'ici
$\varepsilon\geq\omega$ résulte du fait que $\varepsilon\neq 0$ donc
$\varepsilon\geq 1$ donc $\varepsilon=\omega^\varepsilon\geq \omega^1
= \omega$).
\end{corrige}

\textbf{(2)} On suppose que $S$ et $T$ sont deux ensembles d'ordinaux
tels que $\forall \alpha\in S,\; \exists \beta\in
T,\;(\alpha\leq\beta)$ et que $\forall \beta\in T,\; \exists \alpha\in
S,\;(\beta\leq\alpha)$.  Montrer que $\sup S = \sup T$.

\begin{corrige}
Montrons que $\sup T \geq \sup S$.  Pour cela, par définition de $\sup
S$ (plus petit majorant de $S$), il suffit de montrer que $\sup T$
majore $S$, c'est-à-dire que $\sup T \geq \alpha$ si $\alpha\in S$.
Or la première hypothèse qu'on a faite assure $\beta \geq \alpha$ pour
un certain $\beta\in T$ : a fortiori, on a $\sup T \geq \beta \geq
\alpha$, comme on voulait.

De façon symétrique, on a $\sup S \geq \sup T$.  Donc ils sont égaux.
\end{corrige}

\textbf{(3)} On appelle $(\alpha_n)_{n\in\mathbb{N}}$ la suite
d'ordinaux définie par récurrence par $\alpha_0 = 1$ et $\alpha_{n+1}
= \varepsilon^{\alpha_n}$, et $(\beta_n)_{n\in\mathbb{N}}$ la suite
d'ordinaux définie par récurrence par $\beta_0 = \varepsilon+1$ et
$\beta_{n+1} = \omega^{\beta_n}$.  Autrement dit : $1, \varepsilon,
\varepsilon^{\varepsilon}, \varepsilon^{\varepsilon^\varepsilon},
\varepsilon^{\varepsilon^{\varepsilon^\varepsilon}}, \ldots$ d'une
part, et $\varepsilon+1, \omega^{\varepsilon+1},
\omega^{\omega^{\varepsilon+1}},
\omega^{\omega^{\omega^{\varepsilon+1}}}, \ldots$ de l'autre.  Montrer
que ces suites ont la même limite.

\begin{corrige}
Posons $S = \{\alpha_n : n\in\mathbb{N}\}$ et $T = \{\beta_n :
n\in\mathbb{N}\}$.  Comme ces suites sont croissantes, la limite $\lim
n\to\omega \alpha_n$ est définie comme $\sup S$ et la limite $\lim
n\to\omega \beta_n$ est définie comme $\sup T$.

En utilisant le résultat du (1), on a $\alpha_2 =
\varepsilon^\varepsilon = \omega^{\varepsilon^2} \geq
\omega^{\varepsilon+1} = \beta_1$.  Une récurrence sur $n$ permet
alors de conclure $\alpha_n \geq \beta_{n-1}$ pour tout $n\geq 2$ : en
effet $\alpha_{n+1} = \varepsilon^{\alpha_n} \geq \omega^{\alpha_n}
\geq \omega^{\beta_{n-1}} = \beta_n$.

Dans l'autre sens, remarquons d'abord que $1+\alpha_n = \alpha_n$ pour
tout $n\geq 1$, donc $\varepsilon\cdot\alpha_n =
\varepsilon\cdot\varepsilon^{\alpha_{n-1}} =
\varepsilon^{1+\alpha_{n-1}} = \varepsilon^{\alpha_{n-1}} = \alpha_n$
pour tout $n\geq 2$, donc $\varepsilon^{\alpha_n} =
\omega^{\varepsilon\cdot\alpha_n} = \omega^{\alpha_n}$ pour
tout $n\geq 2$.  Donc une fois constaté que $\alpha_2 \geq \beta_0$
(c'est-à-dire $\varepsilon+1 \leq \varepsilon^\varepsilon$), une
récurrence sur $n$ montre que $\alpha_n \geq \beta_{n-2}$ pour
tout $n\geq 2$ : en effet, $\alpha_{n+1} = \varepsilon^{\alpha_n} =
\omega^{\alpha_n} \geq \omega^{\beta_{n-2}} = \beta_{n-1}$.

On a donc montré que tout élément de $S$ est majoré par un élément de
$T$ et réciproquement : la conclusion du (3) s'applique pour conclure
que $\sup S = \sup T$ et les deux suites ont même limite.
\end{corrige}

\textbf{(4)} Montrer que la limite commune $\eta$ trouvée en (3)
vérifie $\eta = \omega^\eta$, et qu'elle est le plus petit ordinal
$\gamma>\epsilon$ tel que $\gamma = \omega^\gamma$.

\begin{corrige}
Si $\eta$ est l'ordinal trouvé en (3), on a $\omega^\eta =
\lim_{\xi\to\eta} \omega^\xi = \sup\{\omega^\xi : \xi<\eta\}$.
D'après (2), ceci vaut aussi $\sup\{\omega^{\beta_n} :
n\in\mathbb{N}\}$ (car tout $\xi<\eta$ est intérieur à un
certain $\beta_n$, et réciproquement tout $\beta_n$ est un
$\xi<\eta$).  Or celui-ci n'est autre que $\sup\{\beta_{n+1} :
n\in\mathbb{N}\}$, donc c'est bien $\eta$.

Par ailleurs, si $\gamma>\varepsilon$ vérifie $\gamma =
\omega^\gamma$, alors on a $\gamma \geq \varepsilon+1 = \beta_0$, et
par récurrence sur $n$ on montre $\gamma \geq \beta_n$ : en effet,
$\gamma = \omega^\gamma \geq \omega^{\beta_n} = \beta_{n+1}$.  Par
conséquent, $\gamma \geq \eta$ (vu que $\eta = \sup\{\beta_n\}$), et
comme on a montré ci-dessus que $\eta = \omega^\eta$, il est bien le
plus petit ordinal $\gamma>\epsilon$ tel que $\gamma = \omega^\gamma$.
\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
très courtes, parfois d'une seule ligne.  Aucune ne demande de
raisonnement 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.)

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

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

\textbf{Définition :} On notera $\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)} 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 de $\{0,1\}^{\mathbb{N}}$
différent de tous les $v_\xi$.

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

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

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

\textbf{Supposition :} Dans les questions (7) à (8), 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 (8), 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 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$ ; et, symétriquement,
qu'il existe $a_\alpha$ 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$.

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

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

\textbf{Définitions :} 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)$.

On pose enfin $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
$\sigma_\xi$ n'est pas gagnante pour Alice au jeu $G(A)$.  Montrer que
la stratégie $\tau_\xi$ n'est pas gagnante pour Bob à ce même jeu
(attention, ce n'est pas exactement symétrique vu que $A$ est
l'ensemble des $a_\alpha$).

\textbf{(10)} Déduire de tout ce qui précède que ni Alice ni Bob n'ont
de stratégie gagnante au jeu $G(A)$.

\textbf{(11)} Pourquoi ceci ne contredit pas les résultats vu en
cours ?



%
%
%
\end{document}