summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--controle-20220413.tex441
-rw-r--r--controle-20230417.tex793
-rw-r--r--controle-20240422.tex577
-rw-r--r--controle-20250626.tex1083
-rw-r--r--notes-mitro206.tex2
5 files changed, 2895 insertions, 1 deletions
diff --git a/controle-20220413.tex b/controle-20220413.tex
new file mode 100644
index 0000000..5c2448d
--- /dev/null
+++ b/controle-20220413.tex
@@ -0,0 +1,441 @@
+%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[francais]{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}{Tout}
+\newcommand\thingy{%
+\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\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{\fuzzy}{\mathrel{\|}}
+%
+\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{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}}
+\else
+\title{MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}}
+\fi
+\author{}
+\date{13 avril 2022}
+\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.
+
+La longueur du sujet ne doit pas effrayer : l'énoncé est long parce
+que des rappels ont été faits et que la rédaction des questions
+cherche à éviter toute ambiguïté. Les réponses attendues sont
+généralement beaucoup plus courtes que les questions elles-mêmes
+(notamment dans le dernier 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
+
+Barème \emph{indicatif} : $8+6+6$.
+
+\ifcorrige
+Ce corrigé comporte 10 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
+
+
+%
+%
+%
+
+\exercice
+
+Le but de cet exercice est de tenter une classification des jeux en
+forme normale, à deux joueurs, \emph{symétriques} (c'est-à-dire que
+les deux joueurs ont les mêmes options et les mêmes gains sous l'effet
+de la permutation qui les échange) et avec deux options.
+
+On considère donc le jeu dont la matrice de gains est la suivante, où
+$u,v,x,y$ sont des réels sur lesquels on va discuter (les options sont
+étiquetées $C$ et $D$ ; le gain d'Alice est listé en premier, celui de
+Bob en second) :
+
+\begin{center}
+\begin{tabular}{r|c|c|}
+$\downarrow$Alice, Bob$\rightarrow$&$C$&$D$\\\hline
+$C$&$u$, $u$&$v$, $x$\\\hline
+$D$&$x$, $v$&$y$, $y$\\\hline
+\end{tabular}
+\end{center}
+
+On se limitera à l'étude du cas où $u>v$, ce qu'on supposera
+désormais.
+
+(1) Expliquer brièvement pourquoi il ne change rien à l'analyse du jeu
+(p.ex., au calcul des équilibres de Nash) de remplacer tous les gains
+$t$ d'un joueur donné par $at+b$ où $a>0$ et $b$ est quelconque. En
+déduire qu'on peut supposer, dans le jeu ci-dessus, que $u=1$ et
+$v=0$, ce qu'on fera désormais :
+
+\begin{center}
+\begin{tabular}{r|c|c|}
+$\downarrow$Alice, Bob$\rightarrow$&$C$&$D$\\\hline
+$C$&$1$, $1$&$0$, $x$\\\hline
+$D$&$x$, $0$&$y$, $y$\\\hline
+\end{tabular}
+\end{center}
+
+(2) À quelle condition le profil $(C,C)$ (c'est-à-dire : Alice
+joue $C$ et Bob joue $C$) est-il un équilibre de Nash ? À quelle
+condition $(D,D)$ est-il un équilibre de Nash ? À quelle condition
+$(C,D)$ est-il un équilibre de Nash ? Qu'en est-il de $(D,C)$ ? (À
+chaque fois, on demande des conditions sous forme d'inégalités portant
+sur $x$ et $y$.)
+
+On suppose dans la suite (pour écarter des cas limites pénibles) que
+$x$ n'est pas exactement égal à $1$ et que $y$ n'est pas exactement
+égal à $0$.
+
+(3) Expliquer pourquoi il n'y a pas d'équilibre de Nash dans lequel un
+joueur joue une stratégie pure (i.e., soit $C$ soit $D$) et l'autre
+une stratégie strictement mixte (i.e., $pC + (1-p)D$ avec $0<p<1$).
+
+(4) Analyser la possibilité que $(pC + (1-p)D, \; qC + (1-q)D)$, où
+$0<p<1$ et $0<q<1$ soit un équilibre de Nash : que doivent valoir
+$p$ et $q$ si c'est le cas ? et à quelle condition nécessaire et
+suffisante obtient-on effectivement un équilibre de Nash de cette
+forme ? (On pourra tracer un graphique, par ailleurs demandé à la
+question suivante, pour visualiser le signe de $1-x+y$.)
+
+(5) Dans le plan de coordonnées $(x,y)$, représenter graphiquement les
+domaines des paramètres dans lesquels existent les différents
+équilibres de Nash trouvés dans l'analyse. (On rappelle qu'il doit
+toujours y en avoir au moins un, ce qui peut permettre de détecter
+d'éventuelles erreurs.) Dans quelle partie du diagramme se situent le
+dilemme du prisonnier et le dilemme du trouillard respectivement ?
+
+(La question (6) peut être traitée indépendamment des questions
+précédentes.)
+
+(6) On introduit le nouveau concept suivant : pour un jeu symétrique,
+une \textbf{stratégie rationnelle commun} est une stratégie mixte,
+donc ici, $rC + (1-r)D$ pour $0\leq 1\leq r$, qui quand elle est jouée
+par l'ensemble des joueurs, conduit au gain (forcément le même pour
+tous) le plus élevé sous cette contrainte\footnote{Autrement dit, une
+ stratégie rationnelle commune est une stratégie mixte $s$ telle que
+ si tous les joueurs jouent $s$, leur espérance de gain commune sera
+ supérieure ou égale à celle s'ils jouent tous $s'$, quelle que
+ soit $s'$.}. Dans le jeu considéré ici, calculer l'espérance de
+gain commune des joueurs s'ils jouent tous $rC + (1-r)D$ , et en
+déduire pour quelle(s) valeur(s) de $r$ cette fonction est maximale,
+en discutant éventuellement selon les valeurs de $x,y$. Tracer un
+nouveau graphique pour représenter, dans le plan de coordonnés
+$(x,y)$, les domaines de paramètres dans lequels existent les
+différentes stratégies rationnelles communes (on distinguera : $C$,
+$D$ et $rC + (1-r)D$ avec $0<r<1$).
+
+
+%
+%
+%
+
+\exercice
+
+On s'intéresse ici à la variation suivante du jeu de nim (fini) :
+après avoir retiré des bâtonnets d'une ligne, un joueur peut en outre,
+s'il le souhaite, \emph{couper} la ligne en deux, ce qui crée deux
+lignes au lieu d'une, en répartissant comme il le veut les bâtonnets
+de la ligne initiale (après en avoir retiré au moins un) entre ces
+deux lignes.
+
+De façon plus formelle, l'état du jeu est donné par la liste des
+nombres $n_1,\ldots,n_r \in \mathbb{N}$ de bâtonnets des différentes
+lignes du jeu (on peut ignorer ceux pour lesquels $n_i=0$) ; et un
+coup du jeu consiste à choisir un $1\leq i\leq r$ et à remplacer $n_i$
+dans la liste soit par un entier neturels $n' < n_i$, soit par
+\emph{deux} entiers naturels $n',n''$ tels que $n' + n'' < n_i$ (on
+peut d'ailleurs ne considérer que ce deuxième type de coup puisque
+prendre $n''=0$ revient à n'avoir que $n'$). Comme d'habitude, le
+joueur qui ne peut pas jouer a perdu (i.e., le gagnant est celui qui
+retire le dernier bâtonnet) ; et la disposition des lignes ou des
+bâtonnets au sein d'une ligne n'a pas d'importance, seul compte leur
+nombre (et tout est fini).
+
+(1) Expliquer pourquoi la valeur de Grundy de la position
+$(n_1,\ldots,n_r)$ du jeu est la somme de nim $f(n_1) \oplus \cdots
+\oplus f(n_r)$ des valeurs de Grundy $f(n_i)$ des positions ayant une
+seule ligne avec $n_i$ bâtonnets (où $f$ est une fonction qui reste à
+calculer, avec évidemment $f(0)=0$).
+
+(2) Expliquer pourquoi $f(n) = \mex\{f(n') \oplus f(n'') \; | \;
+n'+n'' < n\}$ est le plus petit entier naturel qui n'est pas de la
+forme $f(n') \oplus f(n'')$ où $n',n''$ parcourent les couples
+d'entiers naturels tels que $n'+n'' < n$ (et comme d'habitude, $\mex
+S$ est le plus petit entier naturel qui n'est pas dans $S$).
+
+(3) Indépendamment de ce qui précède, expliquer pourquoi $k \oplus
+\ell \leq k + \ell$ quels que soient $k,\ell \in \mathbb{N}$.
+
+(4) Montrer que $f(n) = n$ pour tout $n$.
+
+(5) Que conclure quant à la stratégie gagnante à la variante proposée
+ici du jeu de nim par rapport au jeu de nim standard ?
+
+
+%
+%
+%
+
+\exercice
+
+On s'intéresse dans cet exercice au jeu de \emph{Hackenbush bicolore
+ en arbre}, défini comme suit. L'état du jeu est représenté par un
+arbre (fini, enraciné\footnote{C'est-à-dire que la racine fait partie
+ de la donnée de l'arbre, ce qui est la convention la plus
+ courante.}) dont chaque arête est soit coloriée \emph{bleue} soit
+\emph{rouge}, mais jamais les deux à la fois (il y a exactement deux
+types d'arêtes). Deux joueurs, Blaise et Roxane, alternent et chacun
+à son tour choisit une arête de l'arbre, bleue pour Blaise ou rouge
+pour Roxane, et l'efface, ce qui fait automatiquement disparaître du
+même coup tout le sous-arbre qui descendait de cette arête (voir
+figure). L'arête choisie doit avoir la couleur associée au joueur,
+c'est-à-dire bleue pour Blaise ou rouge pour Roxane, mais toutes les
+arêtes qui en descendent sont effacées quelle que soit leur couleur.
+Le jeu se termine lorsque plus aucun coup n'est possible (c'est-à-dire
+que le joueur qui doit jouer n'a plus d'arête de sa couleur), auquel
+cas, selon la convention habituelle, le joueur qui ne peut plus jouer
+a perdu.
+
+À titre d'exemple, ceci illustre un coup possible de Roxane
+(effacement d'une arête rouge et de tout le sous-arbre qui en
+descend) :
+\begin{center}
+\begin{tikzpicture}[baseline=0]
+\fill [gray!50!white] (-3.0,0) rectangle (2.0,-0.2);
+\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}]
+\node (P0) at (0,0) {};
+\node (P1) at (-0.75,1) {};
+\node (P2) at (-2.25,2) {};
+\node (P3) at (-2.75,3) {};
+\node (P4) at (-1.75,3) {};
+\node (P5) at (0.75,2) {};
+\node (P6) at (0.00,3) {};
+\node (P7) at (0.75,3) {};
+\node (P8) at (1.50,3) {};
+\node (P9) at (1.75,1) {};
+\node (P10) at (1.75,2) {};
+\end{scope}
+\begin{scope}[line width=1.5pt]
+\draw[blue] (P0) -- (P1);
+\draw[red] (P1) -- (P2);
+\draw[red] (P1) -- (P5);
+\draw[blue] (P2) -- (P3);
+\draw[blue] (P2) -- (P4);
+\draw[blue] (P5) -- (P6);
+\draw[blue] (P5) -- (P7);
+\draw[red] (P5) -- (P8);
+\draw[red] (P0) -- (P9);
+\draw[blue] (P9) -- (P10);
+\end{scope}
+\begin{scope}[line width=3pt,gray!50!black]
+\draw ($0.5*(P1) + 0.5*(P5) + (-0.2,-0.2)$) -- ($0.5*(P1) + 0.5*(P5) + (0.2,0.2)$);
+\draw ($0.5*(P1) + 0.5*(P5) + (-0.2,0.2)$) -- ($0.5*(P1) + 0.5*(P5) + (0.2,-0.2)$);
+\end{scope}
+\end{tikzpicture}
+~devient~
+\begin{tikzpicture}[baseline=0]
+\fill [gray!50!white] (-3.0,0) rectangle (2.0,-0.2);
+\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}]
+\node (P0) at (0,0) {};
+\node (P1) at (-0.75,1) {};
+\node (P2) at (-2.25,2) {};
+\node (P3) at (-2.75,3) {};
+\node (P4) at (-1.75,3) {};
+\node (P9) at (1.75,1) {};
+\node (P10) at (1.75,2) {};
+\end{scope}
+\begin{scope}[line width=1.5pt]
+\draw[blue] (P0) -- (P1);
+\draw[red] (P1) -- (P2);
+\draw[blue] (P2) -- (P3);
+\draw[blue] (P2) -- (P4);
+\draw[red] (P0) -- (P9);
+\draw[blue] (P9) -- (P10);
+\end{scope}
+\end{tikzpicture}
+\end{center}
+
+(1) Expliquer brièvement pourquoi une position de ce jeu peut être
+considérée comme une somme disjonctive de différents jeux du même
+type. Plus exactement, soit $T$ un arbre bicolore de racine $x$,
+soient $y_1,\ldots,y_r$ les fils de $x$, soient $T_1,\ldots,T_r$ les
+sous-arbres ayant pour racines $y_1,\ldots,y_r$ et soient
+$T'_1,\ldots,T'_r$ les arbres de racine $x$ où $T'_i$ est formé de $x$
+et de $T_i$ (y comprise l'arête entre $x$ et $y_i$) : expliquer
+brièvement pourquoi la position représentée par l'arbre $T$ est la
+somme disjonctive de celles représentées par $T'_1,\ldots,T'_r$.
+
+\smallskip
+
+Si $T$ est un arbre de Hackenbush bicolore, notons $1{:}T$ l'arbre
+$T'$ correspondant à placer $T$ au sommet d'une unique arête bleue
+reliée à la racine (autrement dit, $T'$ est formé en ajoutant un
+nouveau sommet, qui sera la racine, et en ajoutant une arête bleue
+entre cette nouvelle racine et l'ancienne racine de $T$).
+
+On \underline{admet} les résultats suivants : à tout arbre de
+Hackenbush bicolore $T$ on peut associer un nombre réel $v(T)$ (sa
+\emph{valeur}), de façon que :
+\begin{itemize}
+\item[(a)] Si $T$ et $T'_1, \ldots, T'_r$ sont comme dans l'énoncé de
+ la question (1) alors $v(T) = v(T'_1) + \cdots + v(T'_r)$.
+\item[(b)] On a $v(-T) = -v(T)$ où $-T$ est l'arbre obtenu en échangeant
+ les couleurs rouge et bleue dans $T$.
+\item[(c)] On a $v(1{:}T) = \varphi_+(v(T))$ où $\varphi_+$ est la
+ fonction définie par\footnote{Les cas dans la définition de
+ $\varphi_+$ se chevauchent un peu, et c'est normal : les
+ définitions sont compatibles aux chevauchements.}
+\[
+\varphi_+(v) = \left\{
+\begin{array}{ll}
+v+1&\hbox{~si $v\geq 0$}\\
+2^{-n}\,(v+n+1)&\hbox{~si $-n\leq v \leq -n+1$ où $n\in\mathbb{N}$}\\
+\end{array}
+\right.
+\]
+\item[(d)] On a $v(T) \geq 0$ si et seulement si Blaise possède une
+ stratégie gagnante en jouant en second à partir de la position $T$,
+ et $v(T) \leq 0$ lorsque Roxane en possède une.
+\end{itemize}
+
+(2) Utiliser ces règles admises pour calculer la valeur de l'arbre
+tracé à gauche dans la figure ci-dessus (avant effacement). Pour
+éviter de se tromper, on recommande de reproduire l'arbre et
+d'indiquer à côté de chaque sommet la valeur du sous-arbre qui en
+descend, et à côté de chaque arête la valeur du sous-arbre avec
+l'arête en question. En déduire qui a une stratégie gagnante dans
+cette position selon le joueur qui commence.
+
+\smallbreak
+
+\centerline{* * *}
+
+Indépendamment de ce qui précède, on va considérer une opération sur
+les jeux partisans : si $G$ est un jeu combinatoire partisan, vu comme
+un graphe orienté (bien-fondé), on définit un jeu noté $1{:}G$ en
+ajoutant une unique position $0$ à $G$ comme on va l'expliquer. Pour
+chaque position $z$ de $G$ il y a une position notée $1{:}z$ de
+$1{:}G$, et il y a une unique autre position, notée $0$,
+dans $1{:}G$ ; pour chaque arête $z \to z'$ de $G$, il y a une arête
+$1{:}z\, \to \, 1{:}z'$ dans $1{:}G$, coloriée de la même manière que
+dans $G$, et il y a de plus une arête $1{:}z\, \to 0$ dans $1{:}G$
+pour chaque $z$, coloriée en bleu (en revanche, $0$ est un puits,
+c'est-à-dire qu'aucune arête n'en part) ; la position initiale de
+$1{:}G$ est $1{:}z_0$ où $z_0$ est celle de $G$. De façon plus
+informelle, pour jouer au jeu $1{:}G$, chaque joueur peut faire un
+coup normal ($1{:}z\, \to \, 1{:}z'$) de $G$, mais par ailleurs,
+Blaise peut à tout moment appliquer un coup « destruction totale »
+$1{:}z\, \to 0$ qui fait terminer immédiatement le jeu (et il a alors
+gagné\footnote{Ce jeu considéré tout seul n'est donc pas très amusant
+ puisque Blaise a toujours la possibilité de gagner
+ instantanément.}).
+
+(3) Montrer que si $G \geq H$ on a $1{:}G \geq 1{:}H$. (On rappelle
+que $G \geq H$ signifie : « Blaise a une stratégie gagnante s'il joue
+en second au jeu $G - H$ défini comme la somme disjonctive du jeu $G$
+et du jeu $-H$ obtenu en échangeant les deux joueurs au jeu $H$ ».
+Pour cela, on expliquera comment Blaise peut gagner à $(1{:}G) -
+(1{:}H)$ en jouant en second, en supposant qu'il sait gagner à $G - H$
+en jouant en second.) En déduire que si $G \doteq H$ alors $1{:}G
+\doteq 1{:}H$.
+
+{\footnotesize\textit{Remarque.} Ceci justifie partiellement
+ l'affirmation (c) des règles admises ci-dessus en ce sens que cela
+ explique que $v(1{:}G)$ ne dépende que de $v(G)$ et pas du détail
+ de $G$, et aussi que la fonction $\varphi_+$ est croissante.\par}
+
+
+
+
+
+%
+%
+%
+\end{document}
diff --git a/controle-20230417.tex b/controle-20230417.tex
new file mode 100644
index 0000000..fce95a1
--- /dev/null
+++ b/controle-20230417.tex
@@ -0,0 +1,793 @@
+%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[a4paper,margin=2.5cm]{geometry}
+\usepackage[francais]{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}{Tout}
+\newcommand\thingy{%
+\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\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}}}
+%
+\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{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}}
+\else
+\title{MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}}
+\fi
+\author{}
+\date{17 avril 2023}
+\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.
+
+La longueur du sujet ne doit pas effrayer : l'énoncé est long parce
+que des rappels ont été faits et que la rédaction des questions
+cherche à éviter toute ambiguïté. De plus, il ne sera pas nécessaire
+de traiter la totalité pour avoir la note maximale.
+
+\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
+
+Barème \emph{indicatif} : $5+5+5+7$ (sur $20$)
+
+\ifcorrige
+Ce corrigé comporte 8 pages (page de garde incluse).
+\else
+Cet énoncé comporte 4 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
+
+
+%
+%
+%
+
+\exercice
+
+On considère le jeu de nim éventuellement transfini. (On rappelle
+qu'il est défini de la manière suivante : une position du jeu est un
+tuple $(\alpha_1,\ldots,\alpha_r)$ d'ordinaux, on dit qu'il y a
+« $\alpha_i$ bâtonnets sur la ligne $i$ », et un coup consiste à
+décroître strictement \emph{un et un seul} des $\alpha_i$, autrement
+dit il existe un coup de $(\alpha_1,\ldots,\alpha_r)$ vers
+$(\alpha_1,\ldots,\beta,\ldots,\alpha_r)$ où $\beta<\alpha_i$ est mis
+à la place de $\alpha_i$.)
+
+Pour chacune des positions suivantes, dire si c'est une position P
+(c'est-à-dire gagnante pour le joueur qui vient de jouer) ou N
+(c'est-à-dire gagnante pour le joueur qui doit jouer), et, dans ce
+dernier cas, donner un coup gagnant possible pour le joueur en
+question.
+
+(a) $(1,2,3)$ (autrement dit, une ligne avec $1$ bâtonnet, une ligne
+avec $2$, et une ligne avec $3$)
+
+\begin{corrige}
+On a $1 = 2^0$ et $2 = 2^1$ et $3 = 2^1 + 2^0 = 2^1 \oplus 2^0$ si
+bien que $1 \oplus 2 \oplus 3 = 0$ : la valeur de Grundy de la
+position est $0$, et c'est donc une position P.
+\end{corrige}
+
+(b) $(3,6,9)$
+
+\begin{corrige}
+On a $3 = 2^1 + 2^0 = 2^1 \oplus 2^0$ et $6 = 2^2 + 2^1 = 2^2 \oplus
+2^1$ et $9 = 2^3 + 2^0 = 2^3 \oplus 2^0$ si bien que $3 \oplus 6
+\oplus 9 = 2^3 \oplus 2^2 = 2^3 + 2^2 = 12$ : la valeur de Grundy de
+la position est $12$, et c'est donc une position N.
+
+Pour trouver un coup gagnant, c'est-à-dire un coup vers une
+position P, on cherche à annuler la valeur de Grundy : autrement dit,
+on cherche à remplacer le nombre $n$ de bâtonnets d'une ligne par $n
+\oplus 12$, et il s'agit donc de trouver une ligne telle que $n \oplus
+12 < n$. On vérifie facilement que la seule possibilité est de
+réduire la ligne ayant $9$ bâtonnets à $9 \oplus 12 = 2^2 + 2^0 = 5$
+bâtonnets. Bref, le seul coup gagnant est $(3,6,9) \to (3,6,5)$.
+\end{corrige}
+
+(c) $(\omega,\omega2,\omega3)$
+
+\begin{corrige}
+En se rappelant que $\omega = 2^{\omega}$, on a $\omega2 =
+2^{\omega+1}$ et $\omega3 = 2^{\omega+1} + 2^{\omega}$ en binaire : on
+a donc $\omega \oplus (\omega2) \oplus (\omega3) = 0$ : la valeur de
+Grundy de la position est $0$, et c'est donc une position P.
+\end{corrige}
+
+(d) $(\omega,\omega^2,\omega^3)$
+
+\begin{corrige}
+En se rappelant de nouveau que $\omega = 2^{\omega}$, on a $\omega^2 =
+2^{\omega2}$ et $\omega^3 = 2^{\omega3}$ en binaire : on a donc
+$\omega \oplus \omega^2 \oplus \omega^3 = 2^{\omega3} + 2^{\omega2} +
+2^\omega = \omega^3 + \omega^2 + \omega =: \gamma$ : la valeur de
+Grundy de la position est $\gamma \neq 0$, et c'est cdonc une
+position N.
+
+Comme dans la question (b), on cherche à annuler la valeur de Grundy,
+autrement dit remplacer le nombre $\alpha$ de bâtonnets d'une ligne
+par $\alpha \oplus \gamma$ (où $\gamma = \omega^3 + \omega^2 +
+\omega$, qu'il vaut mieux penser comme $2^{\omega3} \oplus 2^{\omega2}
+\oplus 2^\omega$) d'une manière à ce que le résultat soit plus petit.
+On vérifie facilement que la seule possibilité est de réduire la ligne
+ayant $\omega^3$ bâtonnets à $\omega^3 \oplus \gamma = \omega^2 +
+\omega$ bâtonnets. Bref, le seul coup gagnant est
+$(\omega,\omega^2,\omega^3) \to (\omega,\omega^2,\omega^2+\omega)$.
+\end{corrige}
+
+(e) $(\omega,\omega^\omega,\omega^{\omega^\omega})$
+
+\begin{corrige}
+En se rappelant une fois de plus que $\omega = 2^{\omega}$, on a
+$\omega^\omega = (2^\omega)^\omega = 2^{\omega\times\omega} =
+2^{\omega^2}$, et $\omega^{\omega^\omega} = (2^\omega)^{\omega^\omega}
+= 2^{\omega\times \omega^{\omega}} = 2^{\omega^{1+\omega}} =
+2^{\omega^\omega}$. Le raisonnement est alors exactement analogue à
+la question (d) (car la seule chose qui importe dans cette question
+ait qu'on ait affaire à trois puissances de $2$ distinctes) : la
+valeur de Grundy de la position est $\gamma := 2^{\omega^\omega} +
+2^{\omega^2} + 2^\omega = \omega^{\omega^\omega} + \omega^\omega +
+\omega \neq 0$ donc c'est une position N, et le seul coup gagnant est
+$(\omega,\omega^\omega,\omega^{\omega^\omega}) \to
+(\omega,\omega^\omega,\omega^\omega + \omega)$.
+\end{corrige}
+
+(f) $(\varepsilon_1, \varepsilon_2, \varepsilon_3)$ où $\varepsilon_0
+< \varepsilon_1 < \varepsilon_2 < \varepsilon_3$ sont les quatre
+premiers ordinaux\footnote{On peut définir $\varepsilon_{n+1}$ comme
+ la limite, c'est-à-dire la borne supérieure, de la suite
+ $(u_k)_{k<\omega}$ strictement croissante définie par $u_0 =
+ (\varepsilon_n) + 1$ et $u_{k+1} = \omega^{u_k}$, c'est-à-dire $u_1
+ = \omega^{(\varepsilon_n) + 1}$ et $u_2 =
+ \omega^{\omega^{(\varepsilon_n) + 1}}$, etc., mais on n'aura pas
+ besoin de ce fait.} vérifiant $\varepsilon = \omega^\varepsilon$.
+
+\begin{corrige}
+Pour $i \in \{1,2,3\}$ (ou n'importe quel ordinal, en fait), on a
+$\varepsilon_i = \omega^{\varepsilon_i} = (2^\omega)^{\varepsilon_i} =
+2^{\omega\cdot\varepsilon_i} = 2^{\omega\cdot\omega^{\varepsilon_i}} =
+2^{\omega^{1+\varepsilon_i}} = 2^{\omega^{\varepsilon_i}} =
+2^{\varepsilon_i}$ (en utilisant au passage le fait, facilement
+vérifié, que $1 + \rho = \rho$ quel que soit l'ordinal infini $\rho$).
+Le raisonnement est alors exactement analogue aux questions (d) et (e)
+(car la seule chose qui importe dans ces questions ait qu'on ait
+affaire à trois puissances de $2$ distinctes) : la valeur de Grundy de
+la position est $\gamma := 2^{\varepsilon_3} + 2^{\varepsilon_2} +
+2^{\varepsilon_1} = \varepsilon_3 + \varepsilon_2 + \varepsilon_1 \neq
+0$ donc c'est une position N, et le seul coup gagnant est
+$(\varepsilon_1, \varepsilon_2, \varepsilon_3) \to (\varepsilon_1,
+\varepsilon_2, \varepsilon_2 + \varepsilon_1)$.
+\end{corrige}
+
+(g) Donner un exemple de position N du jeu de nim (de préférence fini)
+avec un nombre distinct de bâtonnets sur chaque ligne (i.e., les
+$\alpha_i$ sont deux à deux distincts), où il existe strictement plus
+qu'un coup gagnant pour le joueur qui doit jouer. (Pour indication,
+ceci est possible à partir de trois lignes de bâtonnets.)
+
+\begin{corrige}
+On cherche donc une position $(n_1,n_2,n_3)$ avec trois lignes de
+bâtonnets, de valeur de Grundy $g := n_1 \oplus n_2 \oplus n_3$, telle
+qu'au moins deux des trois quantités $n_i \oplus g$ soit strictement
+inférieure au $n_i$ correspondant (le raisonnement étant expliqué à la
+question (b)), en prenant note du fait que $n_1 \oplus g = n_2 \oplus
+n_3$ et de façon analogue pour les trois autres. On cherche donc, par
+exemple, à avoir $n_1 \oplus n_3 < n_2$ et $n_1 \oplus n_2 < n_3$.
+Ceci n'est pas difficile en prenant par exemple pour $n_1$ une
+puissance de $2$ qui existe dans l'écriture binaire de $n_2$ et
+de $n_3$ mais telle qu'en l'enlevant on obtienne des nombres
+strictement plus petits. Par exemple, la position $(2,6,7)$ (de
+valeur de Grundy $2\oplus 6\oplus 7 = 3 =: g$) admet des coups
+gagnants vers $(2,5,7)$ ou $(2,6,4)$ ou même $(1,6,7)$.
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice
+
+Si $G$ est un graphe orienté bien-fondé (qu'on peut considérer comme
+l'ensemble des positions d'un jeu combinatoire auquel il ne manque que
+l'information, sans pertinence ici, de la position initiale), on
+rappelle qu'on a défini la fonction rang
+\[
+\rk(x) := \sup\nolimits^+\{\rk(y) : y\in\outnb(x)\} = \sup\,\{\rk(y)+1 :
+y\in\outnb(x)\}
+\]
+(en notant $\sup^+ S$ le plus petit ordinal strictement supérieur à
+tous les ordinaux de $S$ et $\sup S$ le plus petit ordinal supérieur
+ou égal à tous les ordinaux de $S$, et $\outnb(x)$ l'ensemble des
+voisins sortants de $x$), et la fonction de Grundy
+\[
+\gr(x) := \mex\,\{\gr(y) : y\in\outnb(x)\}
+\]
+(où $\mex S$ désigne le plus petit ordinal qui n'est pas dans $S$),
+— ces définitions ayant bien un sens par induction bien-fondée. La
+première mesure en quelque sorte la durée du jeu si les deux joueurs
+coopèrent pour le faire durer aussi longtemps que possible, et la
+seconde nous donne notamment l'information de quel joueur a une
+stratégie gagnante.
+
+On va maintenant définir une fonction qui mesure en quelque sorte la
+durée du jeu si le joueur perdant cherche à perdre aussi lentement que
+possible tandis que le joueur gagnant cherche à gagner aussi vite que
+possible. Précisément, on pose
+\[
+\left\{
+\begin{array}{ll}
+\dur(x) := \sup\,\{\dur(y)+1 : y\in\outnb(x)\}
+&\;\;\text{si $\gr(x) = 0$}\\
+\dur(x) := \min\,\{\dur(y)+1 : y\in\outnb(x)\text{~et~}\gr(y)=0\}
+&\;\;\text{si $\gr(x) \neq 0$}\\
+\end{array}
+\right.
+\]
+(où $\min S$ désigne le plus petit ordinal de $S$, si $S$ est un
+ensemble non-vide d'ordinaux).
+
+(1) Expliquer pourquoi cette définition a bien un sens (on
+prendra garde au fait que $\min\varnothing$ n'est pas défini).
+
+\begin{corrige}
+Lorsque $\gr(x) \neq 0$, il existe au moins un voisin sortant $y \in
+\outnb(x)$ tel que $\gr(y) = 0$ (car le $\mex$ est la plus petite
+valeur exclue: si un tel $y$ n'existait pas, le $\mex$ serait $0$) :
+ceci assure que le $\min$ dans la deuxième ligne de la définition
+porte toujours sur un ensemble non-vide.
+
+En-dehors de ce fait, la définition ne pose pas de problème : le
+$\sup$ d'un ensemble d'ordinaux existe toujours, et la récursivité de
+la définition est légitime par induction bien-fondée, c'est-à-dire que
+$\dur(x)$ peut faire appel aux valeurs de $\dur(y)$ pour des voisins
+sortants $y$ de $x$. (Le fait de faire appel à $\gr(y)$ n'est pas un
+problème car on sait que $\gr$ est bien défini, et la distinction en
+cas est légitime de toute manière.)
+\end{corrige}
+
+(2) Expliquer rapidement et informellement pourquoi $\dur(x)$
+correspond bien à l'explication intuitive qu'on a donnée.
+
+\begin{corrige}
+Quand $x$ est une position avec $\gr(x) = 0$, c'est-à-dire une
+position P, le joueur qui doit jouer est le joueur perdant (n'ayant
+pas de stratégie gagnante) : il joue donc vers une position $y$ le
+faisant perdre le plus lentement possible, c'est-à-dire avec $\dur(y)$
+aussi grand que possible, d'où la définition $\dur(x) =
+\sup\,\{\dur(y)+1 : y\in\outnb(x)\}$ dans ce cas (le $+1$ sert à
+compter le coup joué par ce joueur).
+
+Au contraire, lorsque $\gr(x) \neq 0$, c'est-à-dire que $x$ est une
+position N, le joueur qui doit jouer est le joueur gagnant : il joue
+donc vers une position $y$ le faisant gagner le plus rapidement
+possible, c'est-à-dire avec $\dur(y)$ aussi petit que possible parmi
+les coups $x\to y$ gagnants, autrement dit ceux pour lesquels $\gr(y)
+= 0$, d'où la définition $\dur(x) = \min\,\{\dur(y)+1 :
+y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\}$ dans ce cas (le $+1$ sert à
+compter le coup joué par ce joueur).
+\end{corrige}
+
+(3) Sur le graphe $G$ représenté ci-dessous, calculer chacune des
+fonctions $\rk$, $\gr$ et $\dur$ (les lettres servent simplement à
+étiqueter les sommets) :
+
+\begin{center}\footnotesize
+\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
+\node (nA) at (0bp,0bp) [draw,circle] {A};
+\node (nB) at (0bp,-40bp) [draw,circle] {B};
+\node (nC) at (40bp,0bp) [draw,circle] {C};
+\node (nD) at (40bp,-40bp) [draw,circle] {D};
+\node (nE) at (80bp,0bp) [draw,circle] {E};
+\node (nF) at (80bp,-40bp) [draw,circle] {F};
+\node (nG) at (120bp,-40bp) [draw,circle] {G};
+\draw[->] (nA) -- (nB);
+\draw[->] (nA) -- (nC);
+\draw[->] (nB) -- (nD);
+\draw[->] (nB) to[out=315,in=225] (nG);
+\draw[->] (nC) -- (nD);
+\draw[->] (nC) -- (nE);
+\draw[->] (nD) -- (nF);
+\draw[->] (nE) -- (nF);
+\draw[->] (nF) -- (nG);
+\draw[->] (nE) to[out=0,in=90] (nG);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip
+Si on joue à partir du sommet A comme position initiale et que, comme
+suggéré dans la définition de $\dur$, le joueur perdant cherche à
+perdre aussi lentement que possible tandis que le joueur gagnant
+cherche à gagner aussi vite que possible, quelle sera le déroulement
+du jeu ?
+
+\begin{corrige}
+Les sommets ont été fort sympathiquement étiquetés dans un ordre
+compatible avec le rang (tri topologique), c'est-à-dire que chaque
+arête pointe vers un sommet situé strictement après dans l'ordre
+alphabétique. On effectue donc les calculs dans l'ordre alphabétique
+inversé. On trouve, pour le rang :
+
+\begin{center}\footnotesize
+\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
+\node (nA) at (0bp,0bp) [draw,circle] {$4$};
+\node (nB) at (0bp,-40bp) [draw,circle] {$3$};
+\node (nC) at (40bp,0bp) [draw,circle] {$3$};
+\node (nD) at (40bp,-40bp) [draw,circle] {$2$};
+\node (nE) at (80bp,0bp) [draw,circle] {$2$};
+\node (nF) at (80bp,-40bp) [draw,circle] {$1$};
+\node (nG) at (120bp,-40bp) [draw,circle] {$0$};
+\draw[->] (nA) -- (nB);
+\draw[->] (nA) -- (nC);
+\draw[->] (nB) -- (nD);
+\draw[->] (nB) to[out=315,in=225] (nG);
+\draw[->] (nC) -- (nD);
+\draw[->] (nC) -- (nE);
+\draw[->] (nD) -- (nF);
+\draw[->] (nE) -- (nF);
+\draw[->] (nF) -- (nG);
+\draw[->] (nE) to[out=0,in=90] (nG);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip
+
+Pour la valeur de Grundy :
+
+\begin{center}\footnotesize
+\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
+\node (nA) at (0bp,0bp) [draw,circle] {$0$};
+\node (nB) at (0bp,-40bp) [draw,circle] {$1$};
+\node (nC) at (40bp,0bp) [draw,circle] {$1$};
+\node (nD) at (40bp,-40bp) [draw,circle] {$0$};
+\node (nE) at (80bp,0bp) [draw,circle] {$2$};
+\node (nF) at (80bp,-40bp) [draw,circle] {$1$};
+\node (nG) at (120bp,-40bp) [draw,circle] {$0$};
+\draw[->] (nA) -- (nB);
+\draw[->] (nA) -- (nC);
+\draw[->] (nB) -- (nD);
+\draw[->] (nB) to[out=315,in=225] (nG);
+\draw[->] (nC) -- (nD);
+\draw[->] (nC) -- (nE);
+\draw[->] (nD) -- (nF);
+\draw[->] (nE) -- (nF);
+\draw[->] (nF) -- (nG);
+\draw[->] (nE) to[out=0,in=90] (nG);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip
+
+Et pour la fonction $\dur$ (afin de rendre le calcul plus facile à
+suivre, on a entouré en double les sommets de valeur de Grundy $0$) :
+
+\begin{center}\footnotesize
+\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
+\node (nA) at (0bp,0bp) [draw,double,circle] {$4$};
+\node (nB) at (0bp,-40bp) [draw,circle] {$1$};
+\node (nC) at (40bp,0bp) [draw,circle] {$3$};
+\node (nD) at (40bp,-40bp) [draw,double,circle] {$2$};
+\node (nE) at (80bp,0bp) [draw,circle] {$1$};
+\node (nF) at (80bp,-40bp) [draw,circle] {$1$};
+\node (nG) at (120bp,-40bp) [draw,double,circle] {$0$};
+\draw[->] (nA) -- (nB);
+\draw[->] (nA) -- (nC);
+\draw[->] (nB) -- (nD);
+\draw[->] (nB) to[out=315,in=225] (nG);
+\draw[->] (nC) -- (nD);
+\draw[->] (nC) -- (nE);
+\draw[->] (nD) -- (nF);
+\draw[->] (nE) -- (nF);
+\draw[->] (nF) -- (nG);
+\draw[->] (nE) to[out=0,in=90] (nG);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip
+
+Si on joue à partir de la position A, le premier joueur, appelons-la
+Alice, est en position perdante car la valeur de Grundy est nulle, et
+va jouer vers C car c'est ce qui maximise la fonction $\dur$ ; son
+adversaire, appelons-le Bob, joue alors vers D car c'est le seul coup
+gagnant, après quoi Alice joue vers F (seul coup possible) et Bob joue
+vers G.
+\end{corrige}
+
+(4) Montrer que, dans n'importe quel graphe $G$ bien-fondé, et pour
+n'importe quel sommet $x$ de $G$, on a $\dur(x) \leq \rk(x)$.
+
+\begin{corrige}
+On montre par induction bien-fondée que $\dur(x) \leq \rk(x)$. On
+peut donc faire l'hypothèse qu'on sait que $\dur(y) \leq \rk(y)$ pour
+tout voisin sortant $y \in \outnb(x)$ (hypothèse d'induction). Dans
+le cas où $\gr(x) = 0$, on a $\dur(x) = \sup\,\{\dur(y)+1 :
+y\in\outnb(x)\}$, qui est $\leq \sup\,\{\rk(y)+1 : y\in\outnb(x)\}$
+par hypothèse d'induction (il est clair qu'augmenter au sens large
+tous les éléments d'un ensemble d'ordinaux augmente son $\sup$ au sens
+large), et ceci vaut $\rk(x)$ par définition. Dans le cas où $\gr(x)
+\neq 0$, on a $\dur(x) = \min\,\{\dur(y)+1 :
+y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\} \leq \sup\,\{\dur(y)+1 :
+y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\} \leq \sup\,\{\dur(y)+1 :
+y\in\outnb(x)\}$ de façon évidente ($\min S \leq \sup S$ est clair),
+et pour la même raison que précédemment, ceci est $\leq
+\sup\,\{\rk(y)+1 : y\in\outnb(x)\} = \rk(x)$.
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice
+
+Soit $G$ un graphe orienté dont l'ensemble des sommets est (au plus)
+dénombrable, et soit $x_0$ un sommet de $G$. (Il n'y a pas d'autre
+hypothèse sur $G$, par exemple on ne suppose pas que $G$ est
+bien-fondé.)
+
+On considère le jeu suivant. Deux joueurs s'affrontent, qu'on
+appellera \emph{le Fugueur} et \emph{le Borneur}. Le Fugueur
+commence, après quoi ils jouent tour à tour. En partant de $x_0$,
+chaque joueur, quand vient son tour, choisit un voisin sortant de la
+position actuelle $x$ \emph{ou bien} choisit de conserver $x$ ;
+autrement dit, il choisit un élément de $\outnb(x) \cup \{x\}$. (Pour
+être parfaitement clair : au premier tour, le Fugueur choisit $x_1 \in
+\outnb(x_0) \cup \{x_0\}$, puis le Borneur choisit $x_2 \in
+\outnb(x_1) \cup \{x_1\}$, et ainsi de suite.) Le jeu dure infiniment
+longtemps (manifestement, les règles permettent toujours à chaque
+joueur de faire un coup). Au bout d'un nombre infini de coups, on
+considère la suite $(x_n)_{n\in\mathbb{N}}$ de toutes les positions
+traversées :
+\begin{itemize}
+\item si cette suite est d'image finie (c'est-à-dire que l'ensemble
+ $\{x_n : n\in\mathbb{N}\}$ de toutes les positions traversées est
+ fini), alors le Borneur a gagné ;
+\item sinon, le Fugueur a gagné.
+\end{itemize}
+
+(1) Montrer, en appliquant un des résultats du cours, que l'un des
+joueurs a nécessairement une stratégie gagnante (on ne demande pas de
+préciser lequel). On pourra préalablement montrer que pour toute
+partie $F \subseteq G$, la partie $F^{\mathbb{N}} \subseteq
+G^{\mathbb{N}}$ est \emph{fermée} (pour la topologie sur
+$G^{\mathbb{N}}$ produit de la topologie
+discrète\footnote{C'est-à-dire celle qui a été étudiée en cours.}), et
+en déduire une propriété de l'ensemble
+$\bigcup_{F\text{~fini~}\subseteq G} F^{\mathbb{N}}$ réunion des
+$F^{\mathbb{N}}$ où $F$ parcourt toutes les parties \emph{finies}
+de $G$.
+
+\begin{corrige}
+Pour commencer, montrons que si $F$ est une partie de $G$ alors
+$F^{\mathbb{N}} \subseteq G^{\mathbb{N}}$ est fermée. Ceci revient à
+montrer que son complémentaire est ouvert, autrement dit, que si
+$\dblunderline{x} \in G^{\mathbb{N}}$ n'est pas dans $F^{\mathbb{N}}$,
+alors il existe un voisinage fondamental de $\dblunderline{x}$ qui ne
+rencontre pas $F^{\mathbb{N}}$. Or si $\dblunderline{x} \in
+G^{\mathbb{N}}$ n'est pas dans $F^{\mathbb{N}}$, c'est qu'elle a une
+valeur $x_\ell$ qui n'est pas dans $F$, et toute suite commençant par
+$x_0,\ldots,x_\ell$ n'est pas dans $F^{\mathbb{N}}$, c'est-à-dire que
+le voisinage fondamental $V_{\ell+1}(\dblunderline{x})$ est inclus
+dans le complémentaire de $F^{\mathbb{N}}$. Ceci achève de montrer
+que $F^{\mathbb{N}} \subseteq G^{\mathbb{N}}$ est fermée.
+
+Maintenant, l'ensemble $\mathscr{F}$ des parties finies d'un ensemble
+(au plus) dénombrable, en l'occurrence, $G$, est (au plus)
+dénombrable. Ce fait peut être tenu pour acquis, mais rappelons
+pourquoi il est vrai : en effet, si $G = \{g_i : i\in\mathbb{N}\}$,
+alors on peut par exemple énumérer $\mathscr{F}$ à travers les
+écritures binaires, ou plus précisément, $\mathscr{F} = \{F_n :
+n\in\mathbb{N}\}$ où $F_n$ désigne la partie finie
+$\{g_{i_0},\ldots,g_{i_r}\}$ lorsque $n = 2^{i_0} + \cdots + 2^{i_r}$
+avec $i_0,\ldots,i_r$ entiers naturels distincts (autrement dit, $F_0
+= \varnothing$, $F_1 = \{g_0\}$, $F_2 = \{g_1\}$, $F_3 = \{g_0,g_1\}$,
+etc.). Peu importe le fait qu'il y ait des répétitions dans
+l'énumération $F_n$ (un ensemble surjecté par $\mathbb{N}$ est encore
+dénombrable).
+
+Ceci nous permet de dire que $\bigcup_{F\text{~fini~}\subseteq G}
+F^{\mathbb{N}}$, autrement dit $\bigcup_{F \in \mathscr{F}}
+F^{\mathbb{N}}$, est une réunion dénombrable de fermés
+dans $G^{\mathbb{N}}$. Comme un fermé est borélien, c'est une réunion
+dénombrable de boréliens, donc c'est encore un borélien.
+
+Enfin, remarquons que dire que l'ensemble $\{x_n : n\in\mathbb{N}\}$
+est fini revient à dire qu'il est inclus un ensemble fini $F$,
+autrement dit, que la suite $\dblunderline{x} = (x_n)$ appartient à
+$F^{\mathbb{N}}$ pour un certain ensemble fini $F$, ou, ce qui revient
+au même, qu'elle appartient à $\bigcup_{F \in \mathscr{F}}
+F^{\mathbb{N}}$.
+
+On a donc affaire à un jeu de Gale-Stewart défini par l'ensemble de
+suites $B := \bigcup_{F \in \mathscr{F}} F^{\mathbb{N}}$ borélien (ou
+par son complémentaire $A := G^{\mathbb{N}} \setminus B$ si on prend
+le point de vue du Fugueur). Le théorème de détermination borélienne
+de Martin assure que l'un des joueurs a forcément une stratégie
+gagnante.
+\end{corrige}
+
+(2) Indépendamment de la question précédente, donner un exemple de
+couple $(G,x_0)$ pour lequel le Borneur possède une stratégie gagnante
+à ce jeu. Donner un exemple pour lequel le Fugueur en possède une.
+(On cherchera à donner des exemples aussi simples que possibles.)
+
+\begin{corrige}
+Si $G$ est le graphe formé du seul sommet $x_0$, alors le Borneur
+gagne trivialement (la suite sera la suite constante).
+
+Si $G$ est le graphe formé des entiers naturels avec une arête $i \to
+j$ lorsque $i<j$ (autrement dit des petits entiers naturels vers les
+grands), ou même seulement $i \to i+1$, alors le Fugueur a une
+stratégie gagnante consistant à jouer de $i$ vers $i+1$, ce qui assure
+que la suite $(x_{2i+1})$ des positions choisies par le Fugueur est
+strictement croissante quoi que fasse le Borneur (il ne peut pas
+revenir en arrière), et notamment, elle n'est pas d'image finie.
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice
+
+On considère une variante \emph{à somme (possiblement) non-nulle} de
+Pierre-Papier-Ciseaux, à savoir le jeu en forme normale défini par la
+matrice de gain suivante :
+\begin{center}
+\begin{tabular}{r|ccc}
+$\downarrow$Alice, Bob$\rightarrow$&$U$&$V$&$W$\\\hline
+$U$&$x,x$&$-1,+1$&$+1,-1$\\
+$V$&$+1,-1$&$x,x$&$-1,+1$\\
+$W$&$-1,+1$&$+1,-1$&$x,x$\\
+\end{tabular}
+\end{center}
+où $x$ est un réel et, pour plus de commodité, on a écrit $U$ pour
+« Pierre », $V$ pour « Papier » et $W$ pour « Ciseaux ». (La ligne
+correspond à l'option choisie par Alice, la colonne à l'option de Bob,
+et chaque case indique le gain d'Alice suivi du gain de Bob.)
+
+Le but de l'exercice est d'étudier les équilibres de Nash de ce jeu.
+
+(On prendra bien note, pour simplifier les raisonnements en cas, du
+fait que les options ont une symétrie cyclique\footnote{C'est-à-dire
+ que remplacer $U$ par $V$ et $V$ par $W$ et $W$ par $U$ ne change
+ rien au jeu.}, et que les joueurs ont eux aussi des rôles
+symétriques.)
+
+(1) Considérons le profil de stratégies mixtes dans lequel les deux
+joueurs choisissent chacun chaque option avec probabilité
+$\frac{1}{3}$ (c'est-à-dire la stratégie qui est optimale dans le cas
+à somme nulle). Pour quelle(s) valeur(s) de $x$ ce profil est-il un
+équilibre de Nash ?
+
+\begin{corrige}
+Pour des raisons de symétrie, si l'un des joueurs joue cette stratégie
+mixte $\frac{1}{3}U + \frac{1}{3}V + \frac{1}{3}W$, le gain espéré de
+chacun des deux joueurs est le même quelle que soit la stratégie pure,
+donc aussi mixte, de l'autre joueur. Cette valeur se calcule
+d'ailleurs aisément (comme somme des trois colonnes, ou des trois
+lignes, de la matrice de gains, affectées des
+coefficients $\frac{1}{3}$) : c'est $\frac{1}{3}x$ ; mais la seule
+chose qui importe est que l'adversaire ait le même gain espéré quelle
+que soit la stratégie pure, donc aussi mixte, qu'il choisit : il n'a
+donc pas intérêt à changer unilatéralement sa stratégie. Il s'agit
+donc \emph{toujours} d'un équilibre de Nash, quelle que soit la valeur
+de $x$.
+\end{corrige}
+
+\emph{On suppose dorénavant que $x<-1$.}
+
+(2) Existe-t-il un équilibre de Nash dans lequel Alice joue purement
+$U$ ? (On raisonnera les options pouvant être dans le support de la
+stratégie de Bob en réponse.) En déduire tous les équilibres de Nash
+dans lesquels au moins un joueur joue une stratégie pure.
+
+\begin{corrige}
+Si Alice joue purement $U$, les gains de Bob pour les différentes
+stratégies pures de sa réponse sont $x$ pour $U$, $+1$ pour $V$ et
+$-1$ pour $W$ d'après la matrice de gains. Comme $+1 > -1 > x$, la
+seule option qui peut faire partie du support d'une meilleure réponse
+de Bob est $V$, autrement dit, si Alice joue purement $U$ dans un
+équilibre de Nash, Bob répond forcément purement $V$. Mais par le
+même raisonnement (compte tenu de la symétrie cyclique des options et
+de la symétrie des joueurs), si Bob joue purement $V$, Alice joue $W$
+(et pas $U$ comme supposé). Il ne peut donc pas y avoir d'équilibre
+de Nash dans lequel Alice joue purement $U$. Et de nouveau par
+symétrie cyclique des options et symétrie des joueurs, il ne peut y
+avoir aucun équilibre de Nash dans lequel un joueur jouerait une
+stratégie pure.
+\end{corrige}
+
+(3) Dans cette question et la suivante, envisageons un équilibre de
+Nash dans lequel Alice joue la stratégie mixte $pU + (1-p)V$ avec
+$0<p<1$. Supposons dans cette question que Bob réponde avec un une
+stratégie mixte ayant elle aussi $\{U,V\}$ comme support. Montrer que
+$p = \frac{x+1}{2x}$ et que le gain de Bob est $\frac{x^2+1}{2x}$. En
+utilisant le fait que $\frac{x^2+1}{2x} < -\frac{1}{x}$ lorsque $x<-1$
+(qu'on admettra pour ne pas perdre son temps en calculs inutiles), en
+déduire qu'un tel équilibre de Nash n'existe pas.
+
+\begin{corrige}
+Si Alice joue $pU + (1-p)V$, les gains espérés de Bob pour les
+différences stratégies pures de sa réponse sont $px-(1-p) =
+-1+(x+1)p$ pour $U$, $p + (1-p)x = x-(x-1)p$ pour $V$ et $-p + (1-p) =
+1-2p$ pour $W$. Si une meilleure réponse de Bob a $\{U,V\}$ comme
+support, ces deux options doivent apporter le même gain espéré,
+c'est-à-dire qu'on doit avoir $-1+(x+1)p = x-(x-1)p$, ce qui équivaut
+à $p = \frac{x+1}{2x}$, et le gain en question est $\frac{x^2+1}{2x}$,
+tandis que le gain espéré pour $W$ est alors $1-2p = -\frac{1}{x}$.
+D'après l'inégalité $\frac{x^2+1}{2x} < -\frac{1}{x}$, l'option $W$
+fournit un meilleur gain espéré pour Bob, donc $\{U,V\}$ ne peut pas
+être le support d'une meilleure réponse de Bob à $pU + (1-p)V$
+d'Alice.
+\end{corrige}
+
+(4) On considère toujours un équilibre de Nash dans lequel Alice joue
+la stratégie mixte $pU + (1-p)V$ avec $0<p<1$. Supposons maintenant
+que Bob réponde avec une stratégie mixte ayant (au moins) $U$ et $W$
+dans son support support. Montrer que $p = \frac{2}{x+3}$ (et
+que $x\neq -3$) ; en utilisant le fait que $\frac{2}{x+3} > 1$ lorsque
+$-3<x<-1$ et que $\frac{2}{x+3} < 0$ lorsque $x < -3$ (de nouveau, on
+admettra ces faits pour ne pas perdre de temps en calculs), en déduire
+qu'un tel équilibre de Nash n'existe pas.
+
+\begin{corrige}
+On a dit dans la question (3) que si Alice joue $pU + (1-p)V$, les
+gains espérés de Bob pour les différences stratégies pures de sa
+réponse sont $px-(1-p) = -1+(x+1)p$ pour $U$, $p + (1-p)x =
+x-(x-1)p$ pour $V$ et $-p + (1-p) = 1-2p$ pour $W$. Si une meilleure
+réponse de Bob a $U$ et $W$ dans son support, ces deux options doivent
+apporter le même gain espéré, c'est-à-dire qu'on doit avoir $-1+(x+1)p
+= 1-2p$, ce qui équivaut à $(x+3)p = 3$, donc $x\neq 3$ et $p =
+\frac{2}{x+3}$. D'après les inégalités admises, $p$, qui devrait être
+entre $0$ et $1$, ne l'est jamais si $x<-1$, donc un tel équilibre de
+Nash n'existe pas.
+\end{corrige}
+
+(5) Expliquer soigneusement pourquoi les questions (2) à (4) montrent
+que dans tout équilibre de Nash du jeu considéré, les deux joueurs
+jouent une stratégie mixte ayant $\{U,V,W\}$ comme support (i.e.,
+aucun ensemble strictement plus petit n'est possible).
+
+\begin{corrige}
+On a vu en (2) qu'il n'existe aucun équilibre de Nash dans lequel un
+joueur joue une stratégie pure. Supposons maintenant un équilibre de
+Nash dans lequel un joueur a deux options dans son support. Par
+symétrie, sans perte de généralité, on peut supposer que c'est Alice
+et que ces deux options sont $U$ et $V$. Comme les stratégies pures
+sont exclues, les supports possibles de la réponse de Bob sont :
+$\{U,V\}$, $\{U,W\}$, $\{V,W\}$ et $\{U,V,W\}$. Dans la question (3)
+on a exclu $\{U,V\}$ ; dans la question (4), on a exclu $\{U,W\}$ et
+$\{U,V,W\}$. Reste le cas où le support de la stratégie de Bob est
+$\{V,W\}$ (tandis que celui d'Alice est, on le rappelle, $\{U,V\}$).
+Mais quitte à effectuer une symétrie cyclique des options ($U\to W\to
+V\to U$) et échanger les joueurs, cela revient au cas où le support de
+la stratégie d'Alice est $\{U,V\}$ et celui de Bob est $\{U,W\}$ : or
+on a déjà exclu ce cas. Il ne reste donc aucune possibilité.
+\end{corrige}
+
+(6) Envisageons maintenant un équilibre de Nash dans lequel Alice joue
+une stratégie mixte $pU + p'V + (1-p-p')W$ avec $p>0$, $p'>0$ et
+$1-p-p'>0$ et Bob répond par une stratégie ayant elle aussi
+$\{U,V,W\}$ comme support. Écrire un système de deux équations
+linéaires vérifié par $p,p'$, justifier que ce système est
+non-dégénéré et conclure. Quels sont tous les équilibres de Nash du
+jeu ?
+
+\begin{corrige}
+Si Alice joue $pU + p'V + (1-p-p')W$, les gains espérés de Bob pour
+les différences stratégies pures de sa réponse sont $px - p' +
+(1-p-p') = 1 + (x-1)p - 2p'$ pour $U$, $p + p' x - (1-p-p') = -1 + 2p
++ (x+1)p'$ pour $V$ et $-p + p' + (1-p-p')x = x -(x+1)p -
+(x-1)p'$ pour $W$. Si une meilleure réponse de Bob a $\{U,V,W\}$
+comme support, ces trois options doivent apporter le même gain espéré,
+c'est-à-dire que $1 + (x-1)p - 2p' = -1 + 2p + (x+1)p' = x -(x+1)p -
+(x-1)p'$, ou (en soustrayant, disons, le premier membre aux deux
+autres) :
+\[
+\begin{aligned}
+-(x-3)p + (x+3)p' &= 2\\
+- 2xp - (x-3)p' &= -(x-1)
+\end{aligned}
+\]
+Le déterminant de ce système est $(x-3)^2 + 2x(x+3) = 3(x^2+3)$ qui
+est non nul quel que soit $x$, donc le système est non-dégénéré : la
+solution $p=p'=\frac{1}{3}$ trouvée en (1) est donc la seule solution.
+
+Bref, on a montré que le seul équilibre de Nash dans lequel les
+supports des stratégies d'Alice et Bob sont $\{U,V,W\}$ est celui
+décrit en (1) ; comme on a vu en (5) que ceci est la seule possibilité
+de support, il s'agit du seul équilibre de Nash du jeu.
+\end{corrige}
+
+
+
+
+
+%
+%
+%
+\end{document}
diff --git a/controle-20240422.tex b/controle-20240422.tex
new file mode 100644
index 0000000..9350f2a
--- /dev/null
+++ b/controle-20240422.tex
@@ -0,0 +1,577 @@
+%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[a4paper,margin=2.5cm]{geometry}
+\usepackage[francais]{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}{Tout}
+\newcommand\thingy{%
+\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\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}}}
+%
+\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{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}}
+\else
+\title{MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}}
+\fi
+\author{}
+\date{22 avril 2024}
+\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 6 pages (page de garde incluse).
+\else
+Cet énoncé comporte 3 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
+
+
+%
+%
+%
+
+\exercice
+
+\textbf{(1)} On considère le jeu en forme normale défini par la
+matrice de gain suivante :
+\begin{center}
+\begin{tabular}{r|cc}
+$\downarrow$Alice, Bob$\rightarrow$&$X$&$Y$\\\hline
+$X$&$1$&$0$\\
+$Y$&$0$&$2$\\
+\end{tabular}
+\end{center}
+Un seul nombre a été inscrit dans chaque case car les gains des deux
+joueurs sont \emph{égaux}, et c'est ce nombre-là qui est écrit
+(attention, il ne s'agit pas d'un jeu à somme nulle, au contraire : au
+lieu d'être opposés, les intérêts des deux joueurs sont parfaitement
+identiques).
+
+Étudier et déterminer tous les équilibres de Nash de ce jeu : on
+commencera par considérer ceux en stratégies pures, puis par
+considérer les cas où un joueur, ou l'autre, ou les deux, joue une
+stratégie strictement mixte (i.e., ayant pour support $\{X,Y\}$).
+
+\begin{corrige}
+Si Alice joue (purement) $X$, les options de Bob apportent les gains
+$1$ pour $X$ et $0$ pour $Y$, dont la seule meilleure réponse de Bob
+est de jouer purement $X$. De même, si Alice joue (purement) $Y$, les
+options de Bob apportent les gains $0$ pour $X$ et $2$ pour $Y$, dont
+la seule meilleure réponse de Bob est de jouer purement $Y$. Le rôle
+des deux joueurs étant symétrique, ceci prouve que, dans un équilibre
+de Nash, si l'un joue purement une des deux options, l'autre doit
+jouer la même, et ceci donne bien deux équilibres de Nash, $(X,X)$
+(avec gain $1$) et $(Y,Y)$ (avec gain $2$).
+
+Si Alice joue une stratégie strictement mixte dans un équilibre de
+Nash, on vient de voir que Bob joue $pX + (1-p)Y$, l'espérance de gain
+d'Alice doit être la même pour les deux options du support de sa
+stratégie, c'est-à-dire que $p = 2(1-p)$, donc $p = \frac{2}{3}$. Par
+symétrie, Bob joue aussi cette stratégie, et on vérifie que ceci donne
+bien un équilibre de Nash, $(\frac{2}{3}X + \frac{1}{3}Y, \;
+\frac{2}{3}X + \frac{1}{3}Y)$.
+\end{corrige}
+
+\textbf{(2)} Plus généralement, on considère un jeu de la forme
+suivante : les deux joueurs ont le même ensemble d'options, notons-le
+$\{X_1,\ldots,X_N\}$, et ils ont le même gain $u_A(a,b) = u_B(a,b)$
+pour $a,b\in \{X_1,\ldots,X_N\}$, et de plus ce gain vaut $0$ lorsque
+$b\neq a$ et il vaut $g_i$ lorsque $a = b = X_i$, où tous les $g_i$
+sont des réels strictement positifs ($g_i > 0$). Pour résumer :
+\begin{center}
+\begin{tabular}{r|ccc}
+$\downarrow$Alice, Bob$\rightarrow$&$X_1$&$\cdots$&$X_N$\\\hline
+$X_1$&$g_1$&$\cdots$&$0$\\
+$\vdots$&$\vdots$&$\ddots$&$\vdots$\\
+$X_N$&$0$&$\cdots$&$g_N$\\
+\end{tabular}
+\end{center}
+
+\textbf{(a)} Montrer que, dans un équilibre de Nash d'un jeu comme on
+vient de le dire, si $I \subseteq \{X_1,\ldots,X_N\}$ est le
+support\footnote{On rappelle que le support d'une stratégie mixte est
+l'ensemble des options qu'elle choisit avec une probabilité $>0$.} de
+la stratégie d'Alice, le support $J$ de la stratégie de Bob est inclus
+dans $I$. (\emph{Indication :} toute option hors de $I$ apporte un
+gain espéré nul, donc strictement moins bon que n'importe quelle
+combinaison convexe d'options dans $I$.) En déduire par symétrie
+que $I=J$.
+
+\begin{corrige}
+Si $X_j \not\in I$, alors l'option $X_j$ apporte un gain nul à Bob,
+tandis que toute option $X_i \in I$ apporte un gain strictement
+positif (puisque $g_i$ est pondéré avec un coefficient strictement
+positif, tout le reste étant nul). Il s'ensuit qu'une meilleure
+réponse possible de Bob ne peut pas inclure $X_j$ : elle ne peut donc
+inclure que des options dans $I$. Donc $J \subseteq I$. Et par
+symétrie des deux joueurs, $I \subseteq J$. Donc finalement $I = J$.
+\end{corrige}
+
+\textbf{(b)} Toujours en considérant un équilibre de Nash d'un tel
+jeu, en notant $p_1 X_1 + \cdots + p_N X_N$ la stratégie (mixte)
+d'Alice, montrer que les $g_i p_i$ tels que $p_i > 0$ (c'est-à-dire
+$X_i \in I$) sont tous égaux entre eux. En déduire par symétrie le
+résultat analogue pour la stratégie de Bob, donc qu'elles sont égales.
+En déduire qu'il existe au plus $2^N - 1$ équilibres de Nash, un pour
+chaque partie non vide $I$ de $\{X_1,\ldots,X_N\}$.
+
+\begin{corrige}
+En notant $p_1 X_1 + \cdots + p_N X_N$ la stratégie d'Alice, pour
+toute option $X_i \in J = I$ de Bob, le gain espéré de $X_i$ doit être
+toujours le même. Or ce gain est $g_i p_i$. Donc tous les $g_i p_i$
+pour $X_i \in I$ sont égaux. C'est-à-dire que les $p_i$ sont
+proportionnels aux $\frac{1}{g_i}$ pour $X_i \in I$ (les autres étant
+nuls). Ceci détermine la stratégie d'Alice, et par symétrie c'est
+aussi celle de Bob. On a donc trouvé $2^N - 1$ équilibres de Nash
+potentiels : pour toute partie non vide $I$ de $\{X_1,\ldots,X_N\}$ on
+pose calcule $p_i$ comme le quotient de $\frac{1}{g_i}$ par la somme
+des $\frac{1}{g_j}$ pour $X_j \in I$ si $X_i \in I$ (et $0$ sinon), et
+Alice et Bob jouent chacun $p_1 X_1 + \cdots + p_N X_N$.
+\end{corrige}
+
+\textbf{(c)} Vérifier que les stratégies mixtes trouvées en (b) sont
+bien des équilibres de Nash du jeu, et conclure qu'il a exactement
+$2^N - 1$ équilibres de Nash, qu'on décrira explicitement.
+
+\begin{corrige}
+Pour chaque partie non vide $I$ de $\{X_1,\ldots,X_N\}$ on a bien
+décrit une stratégie mixte pour chacun des deux joueurs (c'est la
+même) : on a bien affaire à des réels $p_i$ positifs de somme $1$. Le
+gain espéré de $X_j$ contre $p_1 X_1 + \cdots + p_N X_N$ est $0$ si
+$X_j \not\in I$ et $g_j p_j$ (qui ne dépend pas de $j$) si $X_j \in
+I$ : on ne peut pas faire mieux (avec une stratégie pure, donc a
+fortiori avec une stratégie mixte), donc cette stratégie est bien une
+meilleure réponse possible contre elle-même, et on a bien affaire à un
+équilibre de Nash.
+
+Pour résumer : tous les équilibres de Nash sont décrits de la façon
+suivante : pour une certaine partie non vide $I$ de
+$\{X_1,\ldots,X_N\}$, on pose
+\[
+\left\{
+\begin{array}{ll}
+p_i = \frac{\textstyle 1/g_i}{\textstyle \sum_{X_j\in I}(1/g_j)}&\text{si $p_i\in I$}\\
+p_i = 0&\text{sinon}
+\end{array}
+\right.
+\]
+et les deux joueurs jouent $p_1 X_1 + \cdots + p_N X_N$ : ceci est
+bien un équilibre de Nash et tous sont de cette forme (et $I$ est bien
+déterminé par l'équilibre puisque c'est le support commun des
+stratégies des deux joueurs, donc tous les équilibres qu'on vient de
+décrire sont distincts). Il y en a donc exactement $2^N - 1$.
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice
+
+On considère un jeu de la forme suivante. Soit $A \subseteq
+\mathbb{R}$ un ensemble de réels, soit $X \subseteq \mathbb{R}$ un
+ensemble \emph{fini} de réels, et soit enfin $b>1$ un réel. (Toutes
+ces données sont fixées à l'avance et sont des paramètres définissant
+le jeu. Ils sont supposés connus des deux joueurs.)
+
+Chaque joueur quand vient son tour choisit un élément $x_i \in X$ :
+plus exactement, Alice choisit $x_0$, puis Bob choisit $x_1$, puis
+Alice choisit $x_2$, et ainsi de suite. Il n'y a aucune contrainte
+sur le choix du $x_i$ et chacun a connaissance de tous les coups
+antérieurs.
+
+Au bout d'un nombre infini de tours, on considère le réel
+\[
+u = x_0 + \frac{x_1}{b} + \frac{x_2}{b^2} + \frac{x_3}{b^3} + \cdots
+\]
+c'est-à-dire la somme de la série
+$\sum_{i=0}^{+\infty}\frac{x_i}{b^i}$. Cette série converge car elle
+converge absolument\footnote{\label{footnote-series-converges}Preuve :
+$\sum_{i=0}^{+\infty}\left|\frac{x_i}{b^i}\right| \leq
+\sum_{i=0}^{+\infty}\frac{M}{b^i} = \frac{M}{1-b}$ où $M$ est un
+majorant des $|x|$ pour $x\in X$, qui existe car $X$ est fini.}. Si
+$u\in A$ alors Alice a gagné ; sinon, Bob a gagné.
+
+(Un cas particulier qu'on peut garder à l'esprit est celui où $X =
+\{0,1\}$ et $b = 2$, auquel cas Alice et Bob construisent un nombre
+binaire entre $0$ et $2$ en choisissant alternativement ses chiffres :
+$u = x_0.x_1 x_2 x_3\cdots$ en binaire.)
+
+On cherche à montrer que sous certaines conditions sur $A$, l'un des
+joueurs a une stratégie gagnante.
+
+\textbf{(1)} On considère l'application $\psi\colon X^{\mathbb{N}} \to
+\mathbb{R}$ qui à une suite $\dblunderline{x} = (x_i)_{i\in\mathbb{N}}
+\in X^{\mathbb{N}}$ associe $\sum_{i=0}^{+\infty}\frac{x_i}{b^i}$.
+Montrer que si $\psi(\dblunderline{x}) = u$ et $\varepsilon > 0$,
+alors il existe $\ell \in \mathbb{N}$ tel que toute suite
+$\dblunderline{y}$ commençant par $x_0,\ldots,x_{\ell-1}$ vérifie
+$|\psi(\dblunderline{y})-u| < \varepsilon$. Autrement dit, il existe
+$\ell$ tel que l'image du $\ell$-ième voisinage
+fondamental\footnote{Rappel : $V_\ell(\dblunderline{x})$ est
+l'ensemble des suites commençant par les $\ell$ termes
+$x_0,\ldots,x_{\ell-1}$.} $V_\ell(\dblunderline{x})$ de
+$\dblunderline{x}$ par $\psi$ soit incluse dans la boule ouverte
+$B_\varepsilon(u) :=
+\mathopen]u-\varepsilon,u+\varepsilon\mathclose[$.
+ (\emph{Indication :} s'inspirer de la
+ note \ref{footnote-series-converges}.)
+
+\begin{corrige}
+Si $\dblunderline{x}$ et $\dblunderline{y}$ coïncident sur les
+termes $i<\ell$, alors $|\psi(\dblunderline{y})-u| =
+|\psi(\dblunderline{y})-\psi(\dblunderline{x})| =
+\left|\sum_{i=\ell}^{+\infty} \frac{y_i - x_i}{b^i}\right| \leq
+\sum_{i=\ell}^{+\infty} (\left|\frac{x_i}{b^i}\right| +
+\left|\frac{y_i}{b^i}\right|) \leq \sum_{i=\ell}^{+\infty}
+\frac{2M}{b^i} = \frac{2Mb^\ell}{1-b}$. Cette quantité tend vers $0$
+quand $\ell\to+\infty$, donc il existe $\ell$ tel qu'elle
+soit $<\varepsilon$. Ceci montre bien que si $\dblunderline{y} \in
+V_\ell(\dblunderline{x})$ on a $|\psi(\dblunderline{y})-u| <
+\varepsilon$.
+\end{corrige}
+
+\textbf{(2)} En déduire que si $U \subseteq \mathbb{R}$ est ouvert (au
+sens de la topologie usuelle des réels\footnote{Rappel : $U \subseteq
+\mathbb{R}$ est ouvert lorsque pour tout $u\in U$ il existe
+$\varepsilon>0$ tel que $B_\varepsilon(u) \subseteq U$.}), alors
+l'image réciproque $\psi^{-1}(U) \subseteq X^{\mathbb{N}}$ est ouverte
+(au sens de la topologie produit de la topologie discrète sur
+$X^{\mathbb{N}}$, qu'on a considérée en cours).
+
+\begin{corrige}
+Supposons que $U$ soit ouvert. Si $\dblunderline{x} \in
+\psi^{-1}(U)$, c'est-à-dire $\psi(\dblunderline{x}) =: u \in U$, comme
+$U$ est ouvert, il existe $\varepsilon>0$ tel que $B_\varepsilon(u)
+\subseteq U$, et d'après la question (1), il existe $\ell$ tel que
+$\psi(V_\ell(\dblunderline{x})) \subseteq B_\varepsilon(u) \subseteq
+U$, ce qui signifie $V_\ell(\dblunderline{x}) \subseteq \psi^{-1}(U)$.
+On vient de montrer que tout $\dblunderline{x} \in \psi^{-1}(U)$ a un
+voisinage fondamental $V_\ell(\dblunderline{x})$ inclus dans
+$\psi^{-1}(U)$, c'est-à-dire que $\psi^{-1}(U)$ est ouvert.
+
+(Note : on a évité dans ce corrigé d'utiliser le mot « continu » car
+il n'a pas été défini en cours dans le contexte d'une application de
+$X^{\mathbb{N}}$ vers $\mathbb{R}$. Mais bien sûr, il est correct de
+dire que $\psi$ est continue en tant qu'application entre espaces
+topologiques.)
+\end{corrige}
+
+\textbf{(3)} En déduire que si $A$ est ouvert, ou bien fermé,
+dans $\mathbb{R}$, alors l'un des deux joueurs possède une stratégie
+gagnante au jeu qu'on a décrit.
+
+\begin{corrige}
+Le jeu qu'on a décrit est exactement le jeu de Gale-Stewart défini par
+la partie $\psi^{-1}(A)$. Si $A$ est ouvert, alors la question (2)
+montre que $\psi^{-1}(A)$ est ouvert, donc le jeu est déterminé
+d'après le théorème de détermination des jeux ouverts. Si $A$ est
+fermé, alors son complémentaire $\mathbb{R}\setminus A$ est ouvert,
+donc la question (2) montre que $\psi^{-1}(\mathbb{R}\setminus A) =
+X^{\mathbb{N}} \setminus \psi^{-1}(A)$ est ouvert, c'est-à-dire que
+$\psi^{-1}(A)$ est fermé, donc le jeu est déterminé d'après le
+théorème de détermination des jeux fermés.
+\end{corrige}
+
+\textbf{(4)} Montrer aussi ce résultat lorsque $A = \mathbb{Q}$
+(autrement dit, Alice gagne si la somme $u$ de la série est
+rationnelle\footnote{Merci d'avance de ne pas prétendre que
+$\mathbb{Q}$ est ouvert, ni qu'il est fermé.}). Plus généralement,
+montrer ce résultat lorsque $A$ est borélien.
+
+\begin{corrige}
+L'ensemble $\mathbb{Q}$ est la réunion dénombrable des fermés $\{r\}$
+pour $r\in\mathbb{Q}$ : il est donc borélien (dans $\mathbb{R}$) ;
+l'image réciproque $\psi^{-1}(\mathbb{Q})$ est donc la réunion
+dénombrable des fermés $\psi^{-1}(\{r\})$ : il est donc borélien (dans
+$X^{\mathbb{N}}$). D'après le théorème de détermination des jeux
+boréliens, le jeu est déterminé.
+
+Plus généralement, l'ensemble des $B$ tels que $\psi^{-1}(B)$ soit
+borélien dans $X^{\mathbb{N}}$ est une tribu (puisque $\psi^{-1}$
+préserve les réunions et intersections quelconques, ainsi que le
+complémentaire) et elle contient les ouverts (puisqu'on a vu que
+$\psi^{-1}(U)$ est ouvert pour $U$ ouvert). Elle contient donc les
+boréliens de $\mathbb{R}$. C'est-à-dire que si $B$ est borélien
+dans $\mathbb{R}$ alors $\psi^{-1}(B)$ est borélien dans
+$X^{\mathbb{N}}$. D'après le théorème de détermination des jeux
+boréliens, le jeu est déterminé dès que $A$ est borélien.
+\end{corrige}
+
+
+%
+%
+%
+
+\exercice
+
+On va développer dans cet exercice un algorithme pour calculer la
+somme et le produit d'ordinaux écrits en forme normale de Cantor
+(itérée).
+
+\textbf{(1)} On rappelle que $1 + \omega = \omega$. En déduire que si
+un ordinal $\alpha$ vérifie $\alpha \geq \omega$, alors on a $1 +
+\alpha = \alpha$ (\emph{indication :} justifier qu'on peut écrire
+$\alpha = \omega + \beta$). En déduire que $1 + \omega^\gamma =
+\omega^\gamma$ lorsque $\gamma > 0$, puis que $\omega^{\gamma_1} +
+\omega^{\gamma_2} = \omega^{\gamma_2}$ lorsque $\gamma_1 < \gamma_2$,
+et enfin que $\omega^{\gamma_1} n_1 + \omega^{\gamma_2} n_2 =
+\omega^{\gamma_2} n_2$ si $n_1,n_2$ sont deux entiers naturels non
+nuls (et toujours avec $\gamma_1 < \gamma_2$).
+
+\begin{corrige}
+On a vu que lorsque $\alpha_0 \leq \alpha$, il existe un unique
+$\beta$ tel que $\alpha = \alpha_0 + \beta$ : en particulier, si
+$\alpha \geq \omega$, on peut écrire $\alpha = \omega + \beta$, et on
+en déduit que $1 + \alpha = 1 + \omega + \beta = \omega + \beta =
+\alpha$.
+
+Or si $\gamma > 0$, c'est-à-dire $\gamma \geq 1$, on a $\omega^\gamma
+\geq \omega$, et on vient de voir que ceci implique $1 + \omega^\gamma
+= \omega^\gamma$.
+
+Si $\gamma_1 < \gamma_2$, on peut écrire $\gamma_2 = \gamma_1 +
+\gamma$ (cf. deux paragraphes plus haut), donc $\omega^{\gamma_1} +
+\omega^{\gamma_2} = \omega^{\gamma_1} + \omega^{\gamma_1 + \gamma} =
+\omega^{\gamma_1} + \omega^{\gamma_1} \, \omega^{\gamma} =
+\omega^{\gamma_1} (1 + \omega^\gamma) = \omega^{\gamma_1} \,
+\omega^\gamma = \omega^{\gamma_1+\gamma} = \omega^{\gamma_2}$.
+
+Une fois acquis que $\omega^{\gamma_1} + \omega^{\gamma_2} =
+\omega^{\gamma_2}$, on a $\omega^{\gamma_1} n_1 + \omega^{\gamma_2}
+n_2 = \omega^{\gamma_1} + \cdots + \omega^{\gamma_1} +
+\omega^{\gamma_2} + \cdots + \omega^{\gamma_2}$ (avec $n_1$ termes
+$\omega^{\gamma_1}$ et $n_2$ termes $\omega^{\gamma_2}$), et en
+utilisant de façon répétée l'égalité qu'on vient de dire, ceci vaut
+$\omega^{\gamma_2} + \cdots + \omega^{\gamma_2} = \omega^{\gamma_2}
+n_2$, comme annoncé.
+\end{corrige}
+
+\textbf{(2)} Si $\alpha = \omega^{\gamma_s} n_s + \cdots +
+\omega^{\gamma_1} n_1$ (avec $\gamma_s > \cdots > \gamma_1$ et
+$n_1,\ldots,n_s$ des entiers naturels non nuls) et $\alpha' =
+\omega^{\gamma'_{s'}} n'_{s'} + \cdots + \omega^{\gamma'_1} n'_1$
+(idem) sont deux ordinaux écrits en forme normale de Cantor, en
+utilisant les résultats de la question précédente, expliquer comment
+calculer $\alpha + \alpha'$, en supposant qu'on sache
+algorithmiquement comparer les $\gamma_i$ et les $\gamma'_j$.
+
+\begin{corrige}
+On écrit $\alpha + \alpha' = \omega^{\gamma_s} n_s + \cdots +
+\omega^{\gamma_1} n_1 + \omega^{\gamma'_{s'}} n'_{s'} + \cdots +
+\omega^{\gamma'_1} n'_1$ et, d'après ce qu'on vient de voir, dès que
+deux termes ne sont pas dans le bon ordre (i.e., si un
+$\omega^{\gamma_i} n_i$ précède $\omega^{\gamma_j} n_j$ avec $\gamma_i
+< \gamma_j$), alors le premier disparaît purement et simplement ; et
+bien sûr, si $\gamma_i = \gamma_j$, les termes fusionnent en
+$\omega^{\gamma_i} (n_i+n_j)$ par distributivité à droite. On se
+retrouve donc avec l'écriture en forme normale de Cantor de $\alpha +
+\alpha'$.
+\end{corrige}
+
+\textbf{(3)} Application : si $\alpha = \omega^3\cdot 2 + \omega\cdot
+3 + 5$ et $\alpha' = \omega^2 + \omega\cdot 4$, calculer $\alpha +
+\alpha'$ et $\alpha' + \alpha$.
+
+\begin{corrige}
+Dans le sens $\alpha + \alpha'$, on a $(\omega^3\cdot 2 + \omega\cdot
+3 + 5) + (\omega^2 + \omega\cdot 4) = \omega^3\cdot 2 + \omega^2 +
+\omega\cdot 4$.
+
+Dans le sens $\alpha' + \alpha$, on a $(\omega^2 + \omega\cdot 4) +
+(\omega^3\cdot 2 + \omega\cdot 3 + 5) = \omega^3\cdot 2 + \omega\cdot
+3 + 5$.
+\end{corrige}
+
+\textbf{(4)} Déduire de la question (2) que si $\alpha =
+\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ en forme
+normale de Cantor et $k \geq 1$ est un entier naturel, alors
+$\alpha\cdot k = \omega^{\gamma_s} n_sk + \omega^{\gamma_{s-1}}
+n_{s-1} + \cdots + \omega^{\gamma_1} n_1$ (c'est-à-dire que seul le
+coefficient $n_s$ de la plus haute puissance de $\omega$ est multiplié
+par $k$ ; \emph{indication} : on a $\alpha\cdot k = \alpha + \cdots +
+\alpha$ avec $k$ termes identiques).
+
+\begin{corrige}
+En écrivant $\alpha\cdot k = \alpha + \cdots + \alpha$ (qui résulte de
+la distributivité à droite) et en appliquant les règles expliquées
+en (2), on voit que tous les termes autres que le plus haut de tous
+les termes autres que le dernier de la terme disparaissent purement et
+simplement (ils sont absorbés par le terme le plus haut du $\alpha$
+suivant), donc seul subsistent $k-1$ copies de $\omega^{\gamma_s} n_s$
+plus le dernier $\alpha$, ce qui donne bien $\alpha\cdot k =
+\omega^{\gamma_s} n_sk + \omega^{\gamma_{s-1}} n_{s-1} + \cdots +
+\omega^{\gamma_1} n_1$ comme annoncé.
+\end{corrige}
+
+\textbf{(5)} En déduire que, toujours pour $\alpha = \omega^{\gamma_s}
+n_s + \cdots + \omega^{\gamma_1} n_1$, on a $\alpha\cdot\omega =
+\omega^{\gamma_s+1}$ (\emph{indication} : on pourra calculer
+$\lim_{k\to\omega} \alpha \cdot k$), et plus généralement $\alpha\cdot
+\omega^{\gamma'} = \omega^{\gamma_s+\gamma'}$ si $\gamma'\geq 1$
+(\emph{indication} : on pourra écrire $\gamma' = 1+\gamma''$).
+
+\begin{corrige}
+On cherche à calculer $\alpha\cdot\omega = \lim_{k\to\omega} \alpha \cdot
+k$ (rappelons que cette limite est juste une borne supérieure). Par
+comparaison des formes normales de Cantor, $\omega^{\gamma_s+1}$ est
+plus grand que tous les $\alpha\cdot k = \omega^{\gamma_s} n_sk +
+\omega^{\gamma_{s-1}} n_{s-1} + \cdots + \omega^{\gamma_1} n_1$, donc
+$\omega^{\gamma_s+1} \geq \lim_{k\to\omega} \alpha \cdot k$. Mais
+inversement, la forme normale de Cantor de tout ordinal
+$<\omega^{\gamma_s+1}$ commence par un terme $\leq\omega^{\gamma_s}
+N$, donc majoré par $\alpha\cdot k$ pour $k$ assez grand (certainement
+pour $k\geq N$) : donc $\lim_{k\to\omega} \alpha \cdot k$ ne peut pas
+être $<\omega^{\gamma_s+1}$. Donc c'est exactement
+$\omega^{\gamma_s+1}$, et on a prouvé $\alpha\cdot\omega =
+\omega^{\gamma_s+1}$.
+
+Plus généralement, si $\gamma'\geq 1$, on peut écrire $\gamma' =
+1+\gamma''$ comme on l'a déjà rappelé plus haut, et
+$\alpha\cdot\omega^{\gamma'} = \alpha\cdot\omega^{1+\gamma''} =
+\alpha\cdot\omega\omega^{\gamma''} =
+\omega^{\gamma_s+1}\omega^{\gamma''} = \omega^{\gamma_s+1+\gamma''} =
+\omega^{\gamma_s+\gamma'}$.
+\end{corrige}
+
+\textbf{(6)} Si $\alpha = \omega^{\gamma_s} n_s + \cdots +
+\omega^{\gamma_1} n_1$ et $\alpha' = \omega^{\gamma'_{s'}} n'_{s'} +
+\cdots + \omega^{\gamma'_1} n'_1$ sont deux ordinaux écrits en forme
+normale de Cantor, en utilisant les résultats de la question
+précédente, expliquer comment calculer $\alpha \cdot \alpha'$, en
+supposant qu'on sache algorithmiquement comparer et ajouter les
+$\gamma_i$ et les $\gamma'_j$.
+
+\begin{corrige}
+Par distributivité à droite et comme on sait déjà calculer des sommes,
+on peut se ramener au cas où $\alpha'$ est un seul terme
+$\omega^{\gamma'} n'$. Par associativité, il suffit de savoir
+calculer le produit par $\omega^{\gamma'}$ à droite, et par $n'$. Le
+produit par $\omega^{\gamma'}$ est trivial si $\gamma'=0$ et est réglé
+par la question (5) si $\gamma'>0$. Et le produit par $n'$ est réglé
+par la question (4).
+
+Un peu plus concrètement, pour chaque terme de $\alpha'$ pour lequel
+$\gamma'_j > 0$, on a $\alpha\cdot \omega^{\gamma'_j} n'_j =
+\omega^{\gamma_s + \gamma'_j} n_s n_j$, et le terme fini, s'il existe
+(c'est-à-dire si $\gamma'_1 = 0$) vaut $\alpha\cdot n'_1 =
+\omega^{\gamma_s} n_s n'_1 + \omega^{\gamma_{s-1}} n_{s-1} + \cdots +
+\omega^{\gamma_1} n_1$. Il n'y a plus qu'à ajouter tous ces termes
+dans l'ordre (qui est déjà le bon, et qui donne déjà une forme normale
+de Cantor, puisque $\gamma_s + \gamma'_s > \cdots + \gamma_s +
+\gamma'_2 > \gamma_s > \cdots > \gamma_1$).
+\end{corrige}
+
+\textbf{(7)} Application : si $\alpha = \omega^3\cdot 2 + \omega\cdot
+3 + 5$ et $\alpha' = \omega^2 + \omega\cdot 4$, calculer $\alpha \cdot
+\alpha'$ et $\alpha' \cdot \alpha$.
+
+\begin{corrige}
+Dans le sens $\alpha\alpha'$ on trouve $(\omega^3\cdot 2 + \omega\cdot
+3 + 5) (\omega^2 + \omega\cdot 4) = \omega^5 + \omega^4\cdot 4$ (il
+n'y a pas de terme fini à la fin de $\alpha'$ donc seul le premier
+terme de $\alpha$ survit).
+
+Dans le sens $\alpha'\alpha$ on trouve $(\omega^2 + \omega\cdot 4)
+(\omega^3\cdot 2 + \omega\cdot 3 + 5) = \omega^5\cdot 2 +
+\omega^3\cdot 3 + \omega^2\cdot 5 + \omega\cdot 4$.
+\end{corrige}
+
+
+
+%
+%
+%
+\end{document}
diff --git a/controle-20250626.tex b/controle-20250626.tex
new file mode 100644
index 0000000..36f8319
--- /dev/null
+++ b/controle-20250626.tex
@@ -0,0 +1,1083 @@
+%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[a4paper,margin=2.5cm]{geometry}
+\usepackage[french]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+\usepackage{wasysym}
+\usepackage{url}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{matrix,calc}
+\usepackage{hyperref}
+%
+%\externaldocument{notes-mitro206}[notes-mitro206.pdf]
+%
+\theoremstyle{definition}
+\newtheorem{comcnt}{Whatever}
+\newcommand\thingy{%
+\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
+\newcommand\exercise{%
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
+\renewcommand{\qedsymbol}{\smiley}
+%
+\newcommand{\outnb}{\operatorname{outnb}}
+\newcommand{\downstr}{\operatorname{downstr}}
+\newcommand{\precs}{\operatorname{precs}}
+\newcommand{\mex}{\operatorname{mex}}
+\newcommand{\id}{\operatorname{id}}
+\newcommand{\limp}{\Longrightarrow}
+\newcommand{\gr}{\operatorname{gr}}
+\newcommand{\rk}{\operatorname{rk}}
+\newcommand{\dur}{\operatorname{dur}}
+\newcommand{\fuzzy}{\mathrel{\|}}
+%
+\newcommand{\dblunderline}[1]{\underline{\underline{#1}}}
+%
+\renewcommand{\thefootnote}{\fnsymbol{footnote}}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+%
+\DeclareFontFamily{U}{manual}{}
+\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{}
+\newcommand{\manfntsymbol}[1]{%
+ {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
+\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
+\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
+ \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
+%
+\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
+\newif\ifcorrige
+\corrigetrue
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
+{{\hbox{}\nobreak\hfill\checkmark}%
+\ifcorrige\par\smallbreak\else\egroup\par\fi}
+%
+%
+%
+\begin{document}
+\ifcorrige
+\title{CSC-4MI06-TP / MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}}
+\else
+\title{CSC-4MI06-TP / MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}}
+\fi
+\author{}
+\date{2025-06-26}
+\maketitle
+
+\pretolerance=8000
+\tolerance=50000
+
+\vskip1truein\relax
+
+\noindent\textbf{Consignes.}
+
+Les exercices sont totalement indépendants. Ils pourront être traités
+dans un ordre quelconque, mais on demande de faire apparaître de façon
+très visible dans les copies où commence chaque exercice.
+
+Une traduction anglaise indicative suit l'énoncé en français.
+
+\medbreak
+
+L'usage de tous les documents (notes de cours manuscrites ou
+imprimées, feuilles d'exercices, livres) est autorisé.
+
+L'usage des appareils électroniques est interdit.
+
+\medbreak
+
+% Durée : 2h
+
+\ifcorrige
+Ce corrigé comporte 11 pages (page de garde incluse).
+\else
+Cet énoncé comporte 6 pages (page de garde incluse).
+\fi
+
+\vfill
+{\noindent\tiny
+\immediate\write18{sh ./vc > vcline.tex}
+Git: \input{vcline.tex}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+
+\pagebreak
+
+
+%
+%
+%
+
+\exercise\label{normal-form-games-exercise}
+
+\textbf{(1)} On considère le jeu en forme normale symétrique à somme
+nulle défini par la matrice de gains suivante :
+\begin{center}
+\begin{tabular}{r|ccc}
+$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux\\\hline
+Pierre&$0$&$-1$&$+1$\\
+Papier&$+1$&$0$&$-1$\\
+Ciseaux&$-1$&$+1$&$0$\\
+\end{tabular}
+\end{center}
+(Seul le gain d'Alice a été inscrit dans chaque case car les gains des
+deux joueurs sont opposés.)
+
+Quels sont tous les équilibres de Nash de ce jeu ?
+
+\begin{corrige}
+On a vu en cours qu'une stratégie optimale pour l'un ou l'autre joueur
+est $\frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} +
+\frac{1}{3}\text{Ciseaux}$ : de fait, la valeur du jeu est nulle car
+il est à somme nulle et \emph{symétrique}, et cette stratégie mixte
+$\frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} +
+\frac{1}{3}\text{Ciseaux}$ réalise au moins la valeur du jeu contre
+n'importe quelle option de l'adversaire.
+
+Réciproquement, si $p\,\text{Pierre} + q\,\text{Papier} +
+r\,\text{Ciseaux}$ est une stratégie optimale d'un joueur (avec
+$p,q,r$ positifs de somme $1$), son gain contre les trois stratégies
+pures de l'adversaire (à savoir $q-r$ contre Pierre, $r-p$ contre
+Papier et $p-q$ contre Ciseaux) doit être au moins égal à la valeur du
+jeu (soit $0$). On a donc $q \geq r$ et $r \geq p$ et $p \geq q$, ce
+qui impose $p=q=r$ donc ils valent $\frac{1}{3}$. Ceci montre que
+$\frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} +
+\frac{1}{3}\text{Ciseaux}$ est la seule stratégie optimale à ce jeu
+(quel que soit le joueur).
+
+Enfin, les équilibres de Nash d'un jeu à somme nuls sont ceux où les
+deux joueurs jouent une stratégie optimale, donc il n'y a qu'un seul
+ici, c'est celui où Alice et Bob jouent chacun
+$\frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} +
+\frac{1}{3}\text{Ciseaux}$.
+\end{corrige}
+
+\medskip
+
+\textbf{(2)} On souhaite maintenant ajouter une nouvelle option
+« Foobar » au jeu ci-dessus, c'est-à-dire qu'on considère le jeu en
+forme normale (toujours symétrique et à somme nulle) défini par la
+matrice de gains :
+\begin{center}
+\begin{tabular}{r|cccc}
+$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux&Foobar\\\hline
+Pierre&$0$&$-1$&$+1$&$-x$\\
+Papier&$+1$&$0$&$-1$&$-y$\\
+Ciseaux&$-1$&$+1$&$0$&$-z$\\
+Foobar&$x$&$y$&$z$&$0$\\
+\end{tabular}
+\end{center}
+(Les trois sous-questions qui suivent sont indépendantes.)
+
+\textbf{\hphantom{(2)} (a)} À quelle condition (nécessaire et
+suffisante) sur $x,y,z$ les équilibres de Nash trouvés en (1) sont-ils
+encore des équilibres de Nash pour ce nouveau jeu ?\quad\textbf{(b)} À
+quelle condition (nécessaire et suffisante) sur $x,y,z$ y a-t-il un
+équilibre de Nash où les deux joueurs jouent l'option Foobar (de façon
+certaine) ?\quad\textbf{(c)} À quelle condition (nécessaire et
+suffisante) sur $x,y,z$ y a-t-il un équilibre de Nash où les deux
+joueurs jouent $\frac{1}{2}\text{Pierre} + \frac{1}{2}\text{Foobar}$
+(i.e., Pierre ou Foobar chacun avec probabilité $\frac{1}{2}$) ?
+
+\begin{corrige}
+\textbf{(a)} En ajoutant une ligne et une colonne pour la stratégie
+mixte $M := \frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} +
+\frac{1}{3}\text{Ciseaux}$, le tableau devient :
+\begin{center}
+\begin{tabular}{r|cccc|c}
+$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux&Foobar&$M$\\\hline
+Pierre&$0$&$-1$&$+1$&$-x$&$0$\\
+Papier&$+1$&$0$&$-1$&$-y$&$0$\\
+Ciseaux&$-1$&$+1$&$0$&$-z$&$0$\\
+Foobar&$x$&$y$&$z$&$0$&$\frac{1}{3}(x+y+z)$\\\hline
+$M$&$0$&$0$&$0$&$-\frac{1}{3}(x+y+z)$&$0$\\
+\end{tabular}
+\end{center}
+Le profil $(M,M)$ est un équilibre de Nash lorsque $0$ est le plus
+grand nombre de sa colonne et le plus petit de sa ligne, c'est-à-dire
+exactement lorsque $x+y+z \leq 0$.
+
+\textbf{(b)} Le profil $(\text{Foobar}, \text{Foobar})$ est un
+équilibre de Nash lorsque $0$ est le plus grand nombre de sa colonne
+et le plus petit de sa ligne, c'est-à-dire lorsque $x,y,z$ sont tous
+positifs.
+
+\textbf{(c)} En ajoutant une ligne et une colonne pour la stratégie
+mixte $N := \frac{1}{2}\text{Pierre} +
+\frac{1}{2}\text{Foobar}$, le tableau devient :
+\begin{center}
+\begin{tabular}{r|cccc|c}
+$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux&Foobar&$N$\\\hline
+Pierre&$0$&$-1$&$+1$&$-x$&$-\frac{x}{2}$\\[0.7ex]
+Papier&$+1$&$0$&$-1$&$-y$&$-\frac{y-1}{2}$\\[0.7ex]
+Ciseaux&$-1$&$+1$&$0$&$-z$&$-\frac{z+1}{2}$\\[0.7ex]
+Foobar&$x$&$y$&$z$&$0$&$\frac{x}{2}$\\[0.7ex]\hline
+$N$&$\frac{x}{2}$&$\frac{y-1}{2}$&$\frac{z+1}{2}$&$-\frac{x}{2}$&$0$\\
+\end{tabular}
+\end{center}
+Le profil $(N,N)$ est un équilibre de Nash lorsque $0$ est le plus
+grand nombre de sa colonne et le plus petit de sa ligne, c'est-à-dire
+exactement lorsque $x=0$ et $y\geq 1$ et $z\geq -1$.
+\end{corrige}
+
+\medskip
+
+\textbf{(3)} On change de jeu : on reprend maintenant la matrice de
+gains écrite en (1), mais cette fois les gains des deux joueurs seront
+\emph{égaux} au lieu d'être opposés (ce n'est donc plus un jeu à somme
+nulle ! les joueurs sont alliés et non plus adversaires). Le tableau
+donne la valeur du gain commun aux deux joueurs.
+
+\textbf{\hphantom{(3)} (a)} Montrer que les équilibres de Nash trouvés
+en (1) sont encore des équilibres de Nash de ce nouveau
+jeu.\quad\textbf{(b)} Donner au moins un équilibre de Nash différent
+de ceux-ci. Commenter brièvement quant à la différence de gain
+éventuelle entre les équilibres de Nash trouvés en (a) et (b).
+
+\begin{corrige}
+\textbf{(a)} En ajoutant une ligne et une colonne pour la stratégie
+mixte $M := \frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} +
+\frac{1}{3}\text{Ciseaux}$, le tableau devient :
+\begin{center}
+\begin{tabular}{r|ccc|c}
+$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux&$M$\\\hline
+Pierre&$0$&$-1$&$+1$&$0$\\
+Papier&$+1$&$0$&$-1$&$0$\\
+Ciseaux&$-1$&$+1$&$0$&$0$\\\hline
+$M$&$0$&$0$&$0$&$0$\\
+\end{tabular}
+\end{center}
+Le profil $(M,M)$ est bien un équilibre de Nash car $0$ est le plus
+grand nombre de sa colonne et le plus grand de sa ligne, ce qui est
+bien le cas ici.
+
+\textbf{(b)} Il y a des équilibres de Nash évidents en stratégies
+pures, à savoir tous les $+1$ du tableau : par exemple, si Alice joue
+Papier et Bob joue Pierre, ceci constitue bien un équilibre de Nash
+(car $+1$ est le plus grand nombre de sa colonne et le plus grand de
+sa ligne).
+
+L'équilibre de Nash trouvé en (a) correspond intuitivement à une
+situation où les joueurs ne sont pas synchronisés : ils jouent une
+stratégie équilibrée entre les trois options. Dans ce jeu coopératif,
+ce n'est pas du tout optimal, le gain espéré étant $0$, mais aucun n'a
+d'intérêt à privilégier unilatéralement une des options tant que
+l'autre continue à jouer cette stratégie. Dans le cas trouvé en (b),
+en revanche, les joueurs se sont synchronisés sur une stratégie qui
+les arrange tous les deux, réalisant le gain qui est visiblement le
+meilleur possible ici.
+\end{corrige}
+
+
+%
+%
+%
+
+\exercise\label{modified-nim-exercise}
+
+On considère dans cet exercice le jeu suivant :
+
+Alice et Bob ont devant eux des piles de jetons, qui représentent
+l'état du jeu (= la position). Chaque pile contient un certain nombre
+fini (entier naturel) de jetons. Les piles sont numérotées par des
+entiers naturels, mais il n'y en a qu'un nombre fini qui soient
+non-vides (i.e., qui aient $>0$ jetons). Pour représenter la position
+mathématiquement, on utilisera la liste $(n_0, n_1, n_2, \ldots, n_k)$
+où $n_i$ est le nombre de jetons de la pile numérotée $i$, et où ceci
+signifie implicitement que toutes les piles $\geq k$ sont vides.
+
+Un coup d'un joueur consiste à retirer \emph{exactement un} jeton
+d'une certaine pile $i$, de son choix, et d'ajouter \emph{autant qu'il
+le souhaite} (y compris $0$) jetons à chacune des piles $j<i$, y
+compris ajouter des nombres différents à des piles différentes. Par
+exemple, à partir de la position $(0,3,2)$ on peut notamment jouer
+vers $(42,1000,1)$ ou bien vers $(0,2,2)$ ou encore vers
+$(696\,729\,600,2,2)$.
+
+Comme d'habitude, le joueur qui ne peut pas jouer a perdu,
+c'est-à-dire que celui qui prend le dernier jeton a gagné.
+
+\medskip
+
+\textbf{(1)} Montrer que le jeu qu'on vient de définir termine
+forcément en temps fini, quelle que soit la position initiale et quels
+que soient les coups effectués par les joueurs. (On justifiera
+soigneusement.)
+
+\begin{corrige}
+On associe à la position $(n_0,\ldots,n_k)$ l'ordinal $\omega^k\cdot
+n_k + \cdots + \omega\cdot n_1 + n_0$ (remarquons qu'il s'agit d'une
+écriture en forme normale de Cantor). Un coup du jeu consiste à
+remplacer un certain $n_i$ par $n_i-1$ et tous les $n_j$ avec $j<i$
+par des $n'_j$ où $n'_j \geq n_j$. Le tuple
+$(n'_0,\ldots,n'_{i-1},n_i-1,n_{i+1},\ldots,n_k)$ qui résulte du coup
+est lexicographiquement inférieur à $(n_0,\ldots,n_k)$ pour l'ordre
+lexicographique donnant le poids le plus fort aux $n_j$ avec $j$
+grand, ce qui signifie justement que l'ordinal qu'on vient de lui
+associer a diminué strictement. Comme toute suite strictement
+décroissante d'ordinaux est finie, le jeu termine en temps fini,
+\end{corrige}
+
+\textbf{Définition :} Appelons « position totalement paire » une
+position dans laquelle le nombre $n_i$ de jetons de chaque pile est
+pair, et « position non totalement paire » une position dans laquelle
+au moins un des $n_i$ est impair.
+
+\textbf{(2)} Montrer que tout coup joué depuis une position totalement
+paire conduit nécessairement à une position non totalement paire.
+
+\begin{corrige}
+On a retiré un jeton d'une certaine pile $i$, donc si le nombre de
+jetons était pair avant le coup, il est devenu impair, et la position
+n'est plus totalement paire.
+\end{corrige}
+
+\textbf{(3)} Montrer que depuis toute position non totalement paire il
+existe au moins un coup conduisant à une position totalement paire.
+
+\begin{corrige}
+Si $(n_0,\ldots,n_k)$ est une position non totalement paire, il existe
+un $n_i$ impair : soit $i$ le plus grand possible tel que $n_i$ soit
+impair (tous les $n_j$ avec $j>i$ sont donc pairs). Le coup
+consistant à retirer un jeton de la pile $i$ (qui passe donc à $n_i-1$
+jetons, lequel nombre est pair) et à en ajouter un à toutes les piles
+$j<i$ telles que $n_j$ soit impair (qui passent donc à $n_j+1$ jetons,
+lequel nombre est pair) est légal selon les règles du jeu, et conduit
+à une position totalement paire.
+\end{corrige}
+
+\textbf{(4)} En déduire quelles sont les positions du jeu dans
+lesquelles le premier joueur a une stratégie gagnante, et quelles sont
+celles dans lesquelles le second joueur en a une. (On justifiera très
+soigneusement.)
+
+\begin{corrige}
+Considérons la stratégie $\sigma$ consistant à jouer vers une position
+totalement paire si on est dans une position qui ne l'est pas (c'est
+possible par la question (3)) et à retirer un jeton quelconque sinon
+(et bien sûr, à capituler s'il n'y a plus de jeton). Le joueur qui
+applique cette stratégie $\sigma$ depuis une position non totalement
+paire va gagner : chacun de ces coups mènera à une position totalement
+paire et son adversaire va forcément en sortir au coup suivant, donc
+(par une récurrence immédiate) le joueur dont on parle sera toujours
+face à une position non totalement paire, et gagnera car le jeu ne
+peut pas durer indéfiniment longtemps (question (1)). Ceci montre que
+les positions qui ne sont pas totalement paires sont gagnantes pour le
+premier joueur (ce sont des positions N) et que celles qui sont
+totalement paires sont gagnantes pour le second joueur (ce sont des
+positions P).
+
+Si on préfère, on peut aussi rédiger ainsi : on a vu au (1) que le
+graphe des positions du jeu est bien-fondé. On peut donc montrer par
+induction bien-fondée sur la position $x$ que $x$ est une position P
+si et seulement si elle est totalement paire. Si $x$ est totalement
+paire, aucun de ses voisins sortants n'est totalement pair
+d'après (2), donc ils sont tous N par l'hypothèse d'induction, donc
+$x$ est P ; et réciproquement, si $x$ est P, tous ses voisins sont N,
+donc par hypothèse d'induction aucun n'est totalement pair, donc $x$
+n'est pas totalement pair par (la contraposée de) la question (3).
+Ceci conclut l'induction.
+\end{corrige}
+
+\textbf{(5)} Calculer, en fonction de $n$, la valeur de Grundy de la
+position $(n)$ (c'est-à-dire s'il n'y a que la pile numérotée $0$, et
+que celle-ci comporte $n$ jetons).
+
+\begin{corrige}
+On a $\gr((0)) = 0$ car c'est un puits, et $\gr((1)) = \mex\{0\} = 1$
+puis $\gr((2)) = \mex\{1\} = 0$, et ainsi de suite.
+
+Pour simplifier la notation dans les réponses ultérieures, notons
+$(n\%2)$ l'entier valant $0$ si $n$ est pair et $1$ si $n$ est impair.
+
+Une récurrence sur $n$ permet de prouver que $\gr((n)) = (n\%2)$ : en
+effet, si $n$ est pair, $\gr((n)) = \mex(\{\gr((n-1))\}) = \mex\{1\} =
+0$, et si $n$ est impair, $\gr((n)) = \mex(\{\gr((n-1))\}) = \mex\{0\}
+= 1$.
+\end{corrige}
+
+\textbf{(6)} En déduire la valeur de Grundy des posititions $(0,1)$ et
+$(1,1)$, puis plus généralement de $(n,1)$ en fonction de $n$.
+
+\begin{corrige}
+On a $\gr((0,1)) = \mex\{\gr((n)) : n\in\mathbb{N}\} = \mex\{0,1\} =
+2$. On en déduit que $\gr((1,1)) = \mex(\{\gr((n+1)) :
+n\in\mathbb{N}\} \cup \{\gr((0,1))\}) = \mex\{0,1,2\} = 3$. On
+vérifie alors par récurrence sur $n$ que $\gr((n,1)) = 2$ si $n$ est
+pair et $\gr((n,1)) = 3$ si $n$ est impair (i.e., $2+(n\%2)$, si on
+veut) : en effet, si $n$ est pair, $\gr((n,1)) = \mex(\{\gr((m)) :
+m\geq n\} \cup \{\gr((n-1,1))\}) = \mex(\{0,1,3\}) = 2$, et si $n$ est
+impair, $\gr((n,1)) = \mex(\{\gr((m)) : m\geq n\} \cup
+\{\gr((n-1,1))\}) = \mex(\{0,1,2\}) = 3$.
+\end{corrige}
+
+\textbf{(7)} En déduire la valeur de Grundy des positions $(0,2)$ et
+$(1,2)$, plus plus généralement de $(n_0,n_1)$ en fonction
+de $n_0,n_1$.
+
+\begin{corrige}
+On a $\gr((0,2)) = \mex\{\gr((n,1)) : n\in\mathbb{N}\} = \mex\{2,3\} =
+0$ (ce qu'on peut aussi conclure du fait que $(0,2)$ est totalement
+paire). On en déduit que $\gr((1,2)) = \mex(\{\gr((n+1,1)) :
+n\in\mathbb{N}\} \cup \{\gr((0,2))\}) = \mex\{2,3,0\} = 1$.
+
+On peut alors mener une récurrence sur $n_1$ et, pour chaque $n_1$,
+sur $n_0$ (ou, si on préfère, une induction transfinie sur l'ordinal
+$\omega\cdot n_1 + n_0$) pour montrer : $\gr((n_0,n_1)) = 2(n_1\%2) +
+(n_0\%2)$. En effet,
+\begin{itemize}
+\item si $n_0$ et $n_1$ sont pairs, on a $\gr((n_0,n_1)) =
+ \mex(\{\gr((m,n_1-1)) : m\geq n_0\} \cup \{\gr((n_0-1,n_1))\}) =
+ \mex\{2,3,1\} = 0$ (ce qu'on peut aussi conclure du fait que
+ $(n_0,n_1)$ est totalement paire),
+\item si $n_0$ est impair et $n_1$ pair, on a $\gr((n_0,n_1)) =
+ \mex(\{\gr((m,n_1-1)) : m\geq n_0\} \cup \{\gr((n_0-1,n_1))\}) =
+ \mex\{2,3,0\} = 1$,
+\item si $n_0$ est pair et $n_1$ impair, on a $\gr((n_0,n_1)) =
+ \mex(\{\gr((m,n_1-1)) : m\geq n_0\} \cup \{\gr((n_0-1,n_1))\}) =
+ \mex\{0,1,3\} = 2$,
+\item si $n_0$ et $n_1$ sont impairs, on a $\gr((n_0,n_1)) =
+ \mex(\{\gr((m,n_1-1)) : m\geq n_0\} \cup \{\gr((n_0-1,n_1))\}) =
+ \mex\{0,1,2\} = 3$.
+\end{itemize}
+Ceci couvre tous les cas et conclut la récurrence.
+\end{corrige}
+
+\textbf{(8)} En déduire la valeur de Grundy de la position $(0,0,1)$.
+
+\begin{corrige}
+On a $\gr((0,0,1)) = \mex\{\gr((n_0,n_1)) : n_0,n_1\in\mathbb{N}\} =
+\mex\{0,1,2,3\} = 4$.
+\end{corrige}
+
+\textbf{(9)} Conjecturer une formule générale pour la valeur de Grundy
+d'une position $(n_0,n_1,\ldots,n_k)$ quelconque.
+
+\begin{corrige}
+Les résultats précédents suggèrent que $\gr((n_0,n_1,\ldots,n_k))$ ne
+dépend que de la parité de $n_0,\ldots,n_k$, c'est-à-dire de ce qu'on
+a noté $(n_i\%2)$. Les valeurs calculées jusqu'à présent inspirent à
+penser que
+\[
+\gr((n_0,n_1,\ldots,n_k)) = 2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2)
+\]
+(C'est-à-dire qu'on lit les $(n_i\%2)$ comme un nombre en binaire et
+qu'il donne la valeur de Grundy.)
+\end{corrige}
+
+\textbf{(10)} Démontrer cette formule. (Cette question est plus
+difficile, et il peut être opportun de la garder pour la fin. On
+pourra s'inspirer de la démonstration faite en cours du calcul de la
+valeur de Grundy pour le jeu de nim.)
+
+\begin{corrige}
+On va montrer par induction transfinie sur l'ordinal $\omega^k\cdot
+n_k + \cdots + \omega\cdot n_1 + n_0$ associé à la position
+$(n_0,n_1,\ldots,n_k)$ (ou, ce qui revient essentiellement au même,
+par induction bien-fondée sur la position elle-même) que la formule
+ci-dessus est valable.
+
+Comme $\gr((n_0,n_1,\ldots,n_k))$ est le $\mex$ de l'ensemble $S$ des
+$\gr((n'_0,n'_1,\ldots,n'_k))$ où $(n'_0,n'_1,\ldots,n'_k)$ parcourt
+tous les voisins sortants de $(n_0,n_1,\ldots,n_k)$, pour montrer que
+$\gr((n_0,n_1,\ldots,n_k)) = 2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) +
+(n_0\%2)$, il s'agit de vérifier (A) que $2^k\,(n_k\%2) + \cdots +
+2\,(n_1\%2) + (n_0\%2)$ n'est pas dans $S$ et (B) que tout nombre $r <
+2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2)$ est dans $S$. Or par
+hypothèse d'induction, les éléments de $S$ sont les $2^k\,(n'_k\%2) +
+\cdots + 2\,(n'_1\%2) + (n'_0\%2)$ avec $(n'_0,n'_1,\ldots,n'_k)$
+voisin sortant de $(n_0,n_1,\ldots,n_k)$.
+
+Montrons (A) : on sait qu'un des $n'_i$ vaut $n_i-1$. Ceci assure que
+$(n'_i\%2) \neq (n_i\%2)$, donc par unicité des écritures binaires,
+que $2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2)$ est différent de
+$2^k\,(n'_k\%2) + \cdots + 2\,(n'_1\%2) + (n'_0\%2)$ (au moins un bit
+diffère). Ceci conclut le (A).
+
+Montrons (B) : si $r < 2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) +
+(n_0\%2)$, appelons $r = 2^k\,b_k + \cdots + 2\,b_1 + b_0$ son
+écriture binaire, où $b_j \in \{0,1\}$. Soit $i$ le plus grand
+possible tel que $b_i \neq (n_i\%2)$ : alors $b_i = ((n_i-1)\%2)$.
+(On prendra aussi note du fait que $b_j = (n_j\%2)$ si $j>i$ par
+maximalité de $i$.) Définissons les $n'_j$ comme suit : on pose $n'_j
+= n_j$ si $j>i$, et $n'_i = n_i-1$, et enfin, pour $j<i$, on pose
+$n'_j = n_j + ((n_j+b_j)\%2)$. Par construction (comme $n'_j = n_j$
+si $j>i$ et $n'_i = n_i$ et $n'_j \geq n_j$ si $j\leq i$), le
+$(n'_0,n'_1,\ldots,n'_k)$ qu'on vient de définir est bien un voisin
+sortant de $(n_0,n_1,\ldots,n_k)$. Par ailleurs, $(n'_j\%2) = b_j$ :
+en effet, pour $j>i$ cela résulte de $b_j = (n_j\%2)$ et $n'_j =
+n_j$ ; pour $j=i$ cela résulte de $b_i = ((n_i-1)\%2)$ et $n'_i =
+n_i-1$ ; et pour $j<i$ cela résulte du fait que $n'_j = n_j +
+((n_j+b_j)\%2)$ est congru à $n_j + n_j + b_j$ donc à $b_j$
+modulo $2$. En insérant la formule $b_j = (n'_j\%2)$ qu'on vient de
+montrer dans $r = 2^k\,b_k + \cdots + 2\,b_1 + b_0$, on voit que $r =
+2^k\,(n'_k\%2) + \cdots + 2\,(n'_1\%2) + (n'_0\%2)$. qui est donc
+dans $S$. Ceci conclut le (B), l'induction, et l'ensemble de la
+démonstration.
+\end{corrige}
+
+
+
+%
+%
+%
+
+\exercise\label{indeterminacy-exercise}
+
+On se propose dans cet exercice de montrer qu'il existe une partie $A
+\subseteq \{0,1\}^{\mathbb{N}}$ tel que le jeu de Gale-Stewart $G(A)
+:= G_{\{0,1\}}(A)$ ne soit pas déterminé (i.e., tel qu'aucun des deux
+joueurs n'ait de stratégie gagnante).
+
+(La démonstration a été découpées en questions admettant des réponses
+courtes, parfois d'une seule ligne.)
+
+\medskip
+
+\textbf{(1)} Montrer qu'il existe une bijection $h_{\mathrm{A}}$
+(resp. $h_{\mathrm{B}}$) entre $\{0,1\}^{\mathbb{N}}$ et l'ensemble
+des stratégies d'Alice (resp. de Bob) au jeu $G(A)$.
+(\emph{Indication :} on pourra expliquer rapidement pourquoi il existe
+une bijection entre $\mathbb{N}$ et l'ensemble des positions où c'est
+à Alice, resp. à Bob, de jouer.)
+
+\begin{corrige}
+L'ensemble $P_{\mathrm{A}}$ des positions où c'est à Alice de jouer
+sont les suites binaires finies de longueur paires : on peut les
+énumérer dans l'ordre de longueur et, pour chaque longueur, dans
+l'ordre lexicographique ($()$, $00$, $01$, $10$, $11$, $0000$, $0001$,
+$0010$, etc.). Ceci fournit une bijection $g_{\mathrm{A}}\colon
+\mathbb{N} \to P_{\mathrm{A}}$ : on en déduit une bijection
+$h_{\mathrm{A}}\colon \{0,1\}^{P_{\mathrm{A}}} \to
+\{0,1\}^{\mathbb{N}}$ par $h_{\mathrm{A}}(u) = (n \mapsto
+u(g_{\mathrm{A}}(n)))$. Or $\{0,1\}^{P_{\mathrm{A}}}$ est exactement
+l'ensemble des stratégies d'Alice (ce sont les fonctions qui à une
+position où c'est à Alice de jouer associent un coup d'Alice).
+
+Exactement le même raisonnement fournit le résultat pour
+$h_{\mathrm{B}}$ : il faut simplement considérer cette fois l'ensemble
+$P_{\mathrm{B}}$ des positions où c'est à Bob de jouer, qui sont les
+suites binaires finies de longueur paires ($0$, $1$, $000$, $001$,
+etc.).
+\end{corrige}
+
+\textbf{(2)} On \emph{admet}\footnote{Plus généralement, on peut
+montrer qu'il existe une relation de bon ordre sur n'importe quel
+ensemble (théorème du bon ordre).} qu'il existe une relation de bon
+ordre $\preceq$ sur $\{0,1\}^{\mathbb{N}}$. En déduire qu'il existe
+un ordinal $\gamma$ et une bijection $\xi \mapsto u_\xi$ entre
+l'ensemble $\{\xi < \gamma\}$ des ordinaux plus petits que $\gamma$ et
+l'ensemble $\{0,1\}^{\mathbb{N}}$ (autrement dit, les $u_\xi$ sont
+deux à deux distincts et $\{u_\xi : \xi < \gamma\} =
+\{0,1\}^{\mathbb{N}}$).
+
+\begin{corrige}
+Soit $W$ l'ensemble $\{0,1\}^{\mathbb{N}}$ muni du bon ordre $\preceq$
+qu'on a supposé exister, et soit $\gamma = \#W$ son ordinal. À tout
+élément $w$ de $W$ on associe un ordinal $\#w$ qui est l'ordinal de
+l'ensemble $\{x \in W : x \prec w\}$ des prédécesseurs stricts
+de $w$ : ceci constitue une bijection strictement croissante entre $W$
+et l'ensemble $\{\xi < \gamma\}$ des ordinaux $<\gamma$ ; on appelle
+alors $\xi \mapsto u_\xi$ la bijection réciproque.
+
+(Si on préfère : l'ordinal de $W$ est le même que l'ordinal de $\{\xi
+< \gamma\}$, à savoir $\gamma$, donc il y a une — unique — bijection
+croissante entre les deux, et on appelle $\xi \mapsto u_\xi$ sa
+réciproque.)
+\end{corrige}
+
+\textbf{(3)} Expliquer en une ligne, pourquoi il existe un plus petit
+ordinal $\gamma$ tel qu'il existe une surjection $\xi \mapsto u_\xi$
+de l'ensemble $\{\xi < \gamma\}$ des ordinaux plus petits que $\gamma$
+sur l'ensemble $\{0,1\}^{\mathbb{N}}$.
+
+\begin{corrige}
+En une ligne : on vient de montrer qu'un tel $\gamma$ existe, donc il
+y en a un plus petit.
+
+(En un tout petit peu plus détaillé : comme les ordinaux sont
+bien-ordonnés, dès qu'il existe un ordinal tel que (quelque chose),
+alos il y en a un plus petit ; or il existe un ordinal tel que $\{\xi
+< \gamma\}$ se surjecte sur $\{0,1\}^{\mathbb{N}}$ — on vient de voir
+l'existence d'une telle bijection —, donc il en existe un plus petit.)
+\end{corrige}
+
+\textbf{Définition :} On notera\footnote{Il s'agit ici d'un ‘c’
+gothique (cet ordinal s'appelle le « cardinal du continu ») ; si on ne
+veut pas écrire de ‘c’ gothique on pourra, par exemple, faire un ‘c’
+souligné.} $\mathfrak{c}$ l'ordinal dont on vient de justifier
+l'existence, i.e., le plus petit $\gamma$ tel qu'on puisse écrire
+$\{u_\xi : \xi < \gamma\} = \{0,1\}^{\mathbb{N}}$ pour une certaine
+fonction $\xi \mapsto u_\xi$, qu'on fixe dans la suite.
+
+\textbf{(4)} \textbf{(a)} Si $(v_\xi)_{\xi<\alpha}$ sont des éléments
+quelconques de $\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$,
+expliquer en une ligne pourquoi il existe un élément $x$ de
+$\{0,1\}^{\mathbb{N}}$ différent de tous
+les $v_\xi$.\quad\textbf{(b)} Si $w$ est encore un élément de
+$\{0,1\}^{\mathbb{N}}$, expliquer pourquoi on peut trouver $x$ qui
+soit différent de $w$ (et toujours différent des $v_\xi$).
+
+\begin{corrige}
+\textbf{(a)} En une ligne : $\xi \mapsto v_\xi$ n'est pas surjective
+par minimalité de $\mathfrak{c}$.
+
+\textbf{(b)} Si $\alpha$ est fini, il est évident qu'on peut trouver
+$x$ différent de tous les $v_\xi$ et de $w$ (qui sont en nombre fini),
+parce que $\{0,1\}^{\mathbb{N}}$ est infini. Si $\alpha$ est infini,
+alors $\alpha = 1 + \alpha$ donc on n'a qu'à poser $v'_0 = w$ et
+$v'_{1+\xi} = v_\xi$ pour tout $\xi < \alpha$, et appliquer (a), vu
+que $\{v'_\xi : \xi<\alpha\} = \{v_\xi : \xi<\alpha\} \cup \{w\}$.
+\end{corrige}
+
+\textbf{Définition :} Si $\sigma$ est une stratégie d'Alice au jeu
+$G(A)$ et $y \in \{0,1\}^{\mathbb{N}}$, on note $\sigma \ast y$ la
+confrontation dans laquelle Alice joue selon $\sigma$ et Bob joue
+simplement les termes successifs de $y$ (indépendamment de ce que fait
+Alice ; i.e.,\footnote{Pour enlever le moindre doute : $\sigma \ast y$
+est la suite $(t_n)_{n\in\mathbb{N}}$ définie par récurrence par :
+$t_{2m} = \sigma((t_0,\ldots,t_{2m-1}))$ et $t_{2m+1} = y_m$.} $\sigma
+\ast y$ est une suite binaire dont la suite des termes impairs, ceux
+joués par Bob, est donnée par $y$, tandis qu'Alice joue les termes
+pairs selon la stratégie $\sigma$). Symétriquement, si $\tau$ est une
+stratégie de Bob et $z \in \{0,1\}^{\mathbb{N}}$, on définit $z \ast
+\tau$ comme la confrontation dans laquelle Alice joue les termes de la
+suite $z$ et Bob joue selon $\tau$.
+
+\textbf{(5)} Si $\sigma$ est une stratégie d'Alice, expliquer en une
+ligne pourquoi la fonction $y \mapsto \sigma \ast y$ (de
+$\{0,1\}^{\mathbb{N}}$ vers $\{0,1\}^{\mathbb{N}}$) est injective.
+
+\begin{corrige}
+En une ligne : si $\sigma \ast y = \sigma \ast y'$, ils ont les mêmes
+termes impairs, donc $y = y'$.
+
+(Si on préfère : $y$ se retrouve à partir de $\sigma \ast y$ comme la
+suite de ses termes impairs.)
+\end{corrige}
+
+\textbf{(6)} Si $(a_\xi)_{\xi<\alpha}$ sont des éléments quelconques
+de $\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$, déduire de
+(4)(a) et (5) qu'il existe $y \in \{0,1\}^{\mathbb{N}}$ tel que
+$\sigma \ast y$ soit différent de tous les $a_\xi$ pour $\xi<\alpha$.
+
+\begin{corrige}
+Pour chaque $\xi < \alpha$, si $a_\xi$ est de la forme $\sigma \ast
+v$, appelons $v_\xi$ le $v$ en question (qui est unique d'après (5)),
+et sinon, soit $v_\xi$ quelconque (par exemple la suite nulle). (Ou,
+si on préfère, on peut appeler $v_\xi$ la suite des termes impairs
+de $a_\xi$ dans tous les cas.)
+
+D'après (4)(a), il existe $y \in \{0,1\}^{\mathbb{N}}$ qui est
+différent de tous les $v_\xi$ pour $\xi < \alpha$. Alors $\sigma \ast
+y$ ne peut pas être égal à $a_\xi$, car si c'était le cas,
+c'est-à-dire $a_\xi = \sigma \ast y$, on aurait $\sigma \ast v_\xi =
+\sigma \ast y$, donc $v_\xi = y$ par (5), contredisant la définition
+de $y$.
+\end{corrige}
+
+\textbf{Supposition :} Dans les questions (7) à (9), on suppose que
+$(\sigma_\xi)_{\xi<\mathfrak{c}}$ sont des stratégies d'Alice et
+$(\tau_\xi)_{\xi<\mathfrak{c}}$ des stratégies de Bob. On les
+définira après la question (9), mais on n'a pas besoin d'en savoir
+plus pour l'instant.
+
+\textbf{(7)} En supposant donnés des éléments $(a_\xi)_{\xi<\alpha}$
+et $(b_\xi)_{\xi<\alpha}$ de $\{0,1\}^{\mathbb{N}}$, où $\alpha <
+\mathfrak{c}$, déduire en une ligne des questions précédentes qu'il
+existe $b'$ qui soit de la forme $\sigma_\alpha \ast y$ (pour un
+certain $y \in \{0,1\}^{\mathbb{N}}$), mais différent de tous les
+$a_\xi$ pour $\xi<\alpha$. Expliquer aussi pourquoi il existe $a'$
+qui soit de la forme $z \ast \tau_\alpha$ (pour un certain $z \in
+\{0,1\}^{\mathbb{N}}$), mais différent de tous les $b_\xi$
+pour $\xi<\alpha$ et également différent du $b'$ qu'on vient de
+trouver.
+
+\begin{corrige}
+On pose $b' = \sigma_\alpha \ast y$, où l'existence de $y$ a été
+prouvée en (6) (pour $\sigma = \sigma_\alpha$).
+
+La construction de $a'$ est symétrique, il n'y a qu'à remarquer que $z
+\mapsto z \ast \tau$ est injective, car si $z \ast \tau = z' \ast
+\tau$, ils ont les mêmes termes pairs, donc $z = z'$, tout le reste
+est presque pareil. La seule chose qui diffère est qu'on a un élément
+de plus à éviter ($b_\alpha$), mais la question (4)(b) donne justement
+ce point
+\end{corrige}
+
+On \emph{admettra} qu'il ne pose pas de problème pour
+\emph{choisir}\footnote{Ceci constitue une utilisation de l'axiome du
+choix (qui a d'ailleurs déjà été utilisé dans ce qu'on a admis à la
+question (2)).} de tels $a'$ et $b'$ en fonction de tous les autres
+paramètres.
+
+\textbf{(8)} Déduire de tout ce qui précède qu'il existe $(a_\xi)_{\xi
+ < \mathfrak{c}}$ et $(b_\xi)_{\xi < \mathfrak{c}}$ tels que :
+\begin{itemize}
+\item aucun des $a_\xi$ n'est égal à aucun des $b_\zeta$ (i.e., pour
+ tous $\xi<\mathfrak{c}$ et tout $\zeta<\mathfrak{c}$, on a $a_\xi
+ \neq b_\zeta$),
+\item pour tout $\xi < \mathfrak{c}$, il existe $y \in
+ \{0,1\}^{\mathbb{N}}$ tel que $b_\xi = \sigma_\xi \ast y$,
+\item pour tout $\xi < \mathfrak{c}$, il existe $z \in
+ \{0,1\}^{\mathbb{N}}$ tel que $a_\xi = z \ast \tau_\xi$.
+\end{itemize}
+(C'est tout ce qu'on aura besoin de savoir pour les questions
+suivantes.)
+
+\begin{corrige}
+On définit $(a_\xi)_{\xi < \mathfrak{c}}$ et $(b_\xi)_{\xi <
+ \mathfrak{c}}$ par induction transfinie sur $\xi$ : si $(a_\xi)_{\xi
+ < \alpha}$ et $(b_\xi)_{\xi < \alpha}$ ont déjà été définis, pour
+$\alpha < \mathfrak{c}$, alors on choisit $a_\alpha$ et $b_\alpha$
+comme l'existence a été montrée en (7).
+
+Pour vérifier le premier point, on distingue les cas $\xi < \zeta$ et
+$\zeta \leq \xi$. Dans le premier cas, la définition même de
+$b_\zeta$ était d'être différent de tous les $a_\xi$ pour $\xi <
+\zeta$ ; dans le second cas, la définition même de $a_\xi$ était
+d'être différent de tous les $b_\zeta$ pour $\zeta < \xi$ et aussi de
+$b_\xi$.
+
+Les deux points suivants font partie de la définition des $b_\xi$ et
+des $a_\xi$, il n'y a rien de plus à dire.
+\end{corrige}
+
+\textbf{Définition :} Appelons maintenant $A = \{a_\xi : \xi <
+\mathfrak{c}\}$ l'ensemble des $a_\xi$ qu'on vient de construire
+en (8).
+
+\textbf{(9)} Montrer que, quel que soit $\xi$, la stratégie $\tau_\xi$
+n'est pas gagnante pour Bob au jeu $G(A)$. Montrer que la stratégie
+$\sigma_\xi$ n'est pas gagnante pour Alice à ce même jeu (attention,
+ce n'est pas complètement symétrique vu que $A$ est l'ensemble
+des $a_\alpha$).
+
+\begin{corrige}
+Supposons par l'absurde que la stratégie $\tau_\xi$ soit gagnante pour
+Bob : mais on a vu que $a_\xi = z \ast \tau_\xi$ pour un certain $z$,
+donc $z \ast \tau_\xi$ est dans $A$, c'est-à-dire qu'Alice gagne la
+confrontation, ce qui contredit le fait que $\tau_\xi$ soit gagnante
+pour Bob.
+
+Supposons par l'absurde que la stratégie $\sigma_\xi$ soit gagnante
+pour Alice : mais on a vu que $b_\xi = \sigma_\xi \ast y$ pour un
+certain $y$ ; or $b_\xi$ ne peut pas être dans $A$ car il serait alors
+égal à l'un des $a_\zeta$ et on a vu que ce n'était pas le cas.
+C'est-à-die que Bob gagne la confrontation, ce qui contredit le fait
+que $\sigma_\xi$ soit gagnante pour Bob.
+\end{corrige}
+
+\textbf{Définition :} Posons maintenant $\sigma_\xi :=
+h_{\mathrm{A}}(u_\xi)$ où $h_{\mathrm{A}}$ a été définie en (1) et
+$u_\xi$ en (3), et de même $\tau_\xi := h_{\mathrm{B}}(u_\xi)$.
+
+\textbf{(10)} Montrer que ni Alice ni Bob n'ont de stratégie gagnante
+au jeu $G(A)$.
+
+\begin{corrige}
+La fonction $h_{\mathrm{A}}$ est surjective par définition,
+c'est-à-dire que n'importe quel stratégie d'Alice est de la forme
+$h_{\mathrm{A}}(u)$ pour un certain $u \in \{0,1\}^{\mathbb{N}}$ ;
+mais $\xi \mapsto u_\xi$ est surjective, c'est-à-dire que tout $u \in
+\{0,1\}^{\mathbb{N}}$ est de la forme $u_\xi$ pour un certain $\xi$.
+Autrement dit, n'importe quelle stratégie d'Alice est une des
+$\sigma_\xi$. Symétriquement, n'importe quelle stratégie de Bob est
+une des $\tau_\xi$.
+
+On vient de voir que ni $\sigma_\xi$ ni $\tau_\xi$ ne peut être une
+stratégie gagnante pour le joueur concerné : donc il n'y a aucune
+stratégie gagnante à ce jeu.
+\end{corrige}
+
+\textbf{(11)} Pourquoi ceci ne contredit pas les résultats vu en
+cours ? Que dire de la partie $A$ ?
+
+\begin{corrige}
+Les résultats du cours concernent les parties ouvertes, fermées, ou
+plus généralemnt boréliennes de $\{0,1\}^{\mathbb{N}}$. Ici on doit
+conclure que la partie $A$ n'est pas borélienne.
+\end{corrige}
+
+%
+%
+%
+
+\begin{otherlanguage}{english}
+
+\vskip1in\penalty-1000
+
+\centerline{\hbox to2truein{\hrulefill}}
+\centerline{\textbf{English translation}}
+
+\footnotesize
+
+(This translation is provided to help understand the French version,
+but the French remains the only official text and should be referred
+to in case of ambiguity or doubt, as this translation has not been
+checked carefully.)
+
+\medbreak
+
+\textbf{Exercise \ref{normal-form-games-exercise}.}
+
+\textbf{(1)} Consider the zero-sum symmetric normal form game defined
+by the following payoff matrix:
+\begin{center}
+\begin{tabular}{r|ccc}
+$\downarrow$Alice, Bob$\rightarrow$&Rock&Paper&Scissors\\\hline
+Rock&$0$&$-1$&$+1$\\
+Paper&$+1$&$0$&$-1$\\
+Scissors&$-1$&$+1$&$0$\\
+\end{tabular}
+\end{center}
+(Only Alice's payoff has been entered in each cell because the two
+players' payoffs are opposite.)
+
+What are all the Nash equilibria of this game?
+
+\textbf{(2)} We now want to add a new option “Foobar” to the above
+game, that is, we consider the game in normal form (still symmetric
+and zero-sum) defined by the payoff matrix:
+\begin{center}
+\begin{tabular}{r|cccc}
+$\downarrow$Alice, Bob$\rightarrow$&Rock&Paper&Scissors&Foobar\\\hline
+Rock&$0$&$-1$&$+1$&$-x$\\
+Paper&$+1$&$0$&$-1$&$-y$\\
+Scissors&$-1$&$+1$&$0$&$-z$\\
+Foobar&$x$&$y$&$z$&$0$\\
+\end{tabular}
+\end{center}
+(The following three sub-questions are independent.)
+
+\textbf{\hphantom{(2)} (a)} Under what (necessary and sufficient)
+condition on $x,y,z$ are the Nash equilibria found in (1) still Nash
+equilibria for this new game?\quad\textbf{(b)} Under what (necessary
+and sufficient) condition on $x,y,z$ is there a Nash equilibrium where
+both players play the Foobar option (with
+certainty)?\quad\textbf{(c)} Under what (necessary and sufficient)
+condition on $x,y,z$ is there a Nash equilibrium where both players
+play $\frac{1}{2}\text{Rock} + \frac{1}{2}\text{Foobar}$ (i.e., Rock
+or Foobar each with probability $\frac{1}{2}$)?
+
+\textbf{(3)} We change the game: we now use the payoff matrix written
+in (1), but this time the payoffs of the two players will be equal
+instead of opposite (so it is no longer a zero-sum game! the players
+are allies and no longer adversaries). The table gives the value of
+the common payoff for both players.
+
+\textbf{\hphantom{(3)} (a)} Show that the Nash equilibria found in (1)
+are still Nash equilibria of this new game. \quad\textbf{(b)} Give at
+least one Nash equilibrium different from these. Comment briefly on
+the possible difference in payoff between the Nash equilibria found in
+(a) and (b).
+
+\medbreak
+
+\textbf{Exercise \ref{modified-nim-exercise}.}
+
+In this exercise, we consider the following game:
+
+Alice and Bob have piles of tokens in front of them, which represent
+the state of the game (= the position). Each pile contains a finite
+number (natural numbers) of tokens. The piles are numbered by natural
+numbers, but only a finite number are non-empty (i.e., have $>0$
+tokens). To represent the position mathematically, we will use the
+list $(n_0, n_1, n_2, \ldots, n_k)$ where $n_i$ is the number of
+tokens in pile numbered i, and this implicitly means that all piles
+$\geq k$ are empty. A player's move consists of removing exactly one
+token from a given pile $i$ of their choice, and adding as many tokens
+as they wish (including zero) to each of the piles $j<i$, including
+adding different numbers to different piles. For example, from
+position $(0,3,2)$ one can play to $(42,1000,1)$ or to $(0,2,2)$ or to
+$(696\,729\,600,2,2)$.
+
+As usual, the player who cannot play has lost, meaning the one who
+takes the last token has won.
+
+\medskip
+
+\textbf{(1)} Show that the game just defined necessarily ends in a
+finite number of moves, regardless of the initial position and
+regardless of the moves made by the players. (Careful justification
+is required here.)
+
+\textbf{Definition:} Let us call a position “totally even” when the
+number $n_i$ of tokens in each pile is even, and “not totally even”
+when least one of the $n_i$ is odd.
+
+\textbf{(2)} Show that any move played from a totally even position
+necessarily leads to a not totally even position.
+
+\textbf{(3)} Show that from any not totally even position there is at
+least one move leading to a totally even position.
+
+\textbf{(4)} Deduce which positions in the game the first player has a
+winning strategy, and which ones the second player has one. (Very
+careful justification is required.)
+
+\textbf{(5)} Calculate, as a function of $n$, the Grundy value of
+position $(n)$ (i.e., if there is only the pile numbered $0$, and
+if it contains $n$ tokens).
+
+\textbf{(6)} Deduce the Grundy value of the positions $(0,1)$ and
+$(1,1)$, then more generally of $(n,1)$ as a function of $n$.
+
+\textbf{(7)} Deduce the Grundy value of the positions $(0,2)$ and
+$(1,2)$, and more generally of $(n_0,n_1)$ as a function of $n_0,n_1$.
+
+\textbf{(8)} Deduce the Grundy value of the position $(0,0,1)$.
+
+\textbf{(9)} Conjecture a general formula for the Grundy value
+of any position $(n_0,n_1,\ldots,n_k)$.
+
+\textbf{(10)} Prove this formula. (This question is more difficult,
+and it may be appropriate to save it for the end. One can draw
+inspiration from the proof given in class of the calculation of the
+Grundy value for the game of nim.)
+
+\medbreak
+
+\textbf{Exercise \ref{indeterminacy-exercise}.}
+
+In this exercise, we aim to show that there exists a game $A \subseteq
+\{0,1\}^{\mathbb{N}}$ such that the Gale-Stewart game $G(A) :=
+G_{\{0,1\}}(A)$ is not determined (i.e., such that neither player has
+a winning strategy).
+
+(The proof has been divided into questions allowing short answers,
+sometimes as short as a single line.)
+
+\medskip
+
+\textbf{(1)} Show that there exists a bijection $h_{\mathrm{A}}$
+(resp. $h_{\mathrm{B}}$) between $\{0,1\}^{\mathbb{N}}$ and the set of
+Alice's (resp. Bob's) strategies in the game $G(A)$. (\emph{Hint:} one
+can quickly explain why there exists a bijection between $\mathbb{N}$
+and the set of positions where it is Alice's, or Bob's, turn to play.)
+
+\textbf{(2)} We \emph{admit} that there exists a well-ordering
+relation $\preceq$ on $\{0,1\}^{\mathbb{N}}$. Deduce that there
+exists an ordinal $\gamma$ and a bijection $\xi \mapsto u_\xi$ between
+the set $\{\xi < \gamma\}$ of ordinals smaller than $\gamma$ and the
+set $\{0,1\}^{\mathbb{N}}$ (in other words, the $u_\xi$ are pairwise
+distinct and $\{u_\xi : \xi < \gamma\} = \{0,1\}^{\mathbb{N}}$).
+
+\textbf{(3)} Explain in one line why there exists a smallest
+ordinal $\gamma$ such that there exists a surjection $\xi \mapsto u_\xi$
+from the set $\{\xi < \gamma\}$ of ordinals smaller than $\gamma$
+to the set $\{0,1\}^{\mathbb{N}}$.
+
+\textbf{Definition:} We will denote $\mathfrak{c}$ the ordinal whose
+existence we just justified, i.e., the smallest $\gamma$ such that we
+can write $\{u_\xi : \xi < \gamma\} = \{0,1\}^{\mathbb{N}}$ for a
+certain function $\xi \mapsto u_\xi$, which we fix in the
+following.
+
+\textbf{(4)} \textbf{(a)} If $(v_\xi)_{\xi<\alpha}$ are any elements
+of $\{0,1\}^{\mathbb{N}}$, where $\alpha < \mathfrak{c}$, explain in
+one line why there exists an element $x$ of $\{0,1\}^{\mathbb{N}}$
+different from all the $v_\xi$.\quad\textbf{(b)} If $w$ is also an
+element of $\{0,1\}^{\mathbb{N}}$, explain why we can find $x$ that is
+different from $w$ (and still different from the $v_\xi$).
+
+\textbf{Definition:} If $\sigma$ is a strategy for Alice in the game
+$G(A)$ and $y \in \{0,1\}^{\mathbb{N}}$, we denote by $\sigma \ast y$
+the confrontation in which Alice plays according to $\sigma$ and Bob
+plays simply the successive terms of $y$ (independently of what Alice
+does; i.e.,\footnote{To remove any doubt: $\sigma \ast y$ is the
+sequence $(t_n)_{n\in\mathbb{N}}$ defined by induction by: $t_{2m} =
+\sigma((t_0,\ldots,t_{2m-1}))$ and $t_{2m+1} = y_m$.} $\sigma \ast y$
+is a binary sequence whose sequence of odd terms, those played by Bob,
+is given by $y$, while Alice plays the even terms according to the
+strategy $\sigma$). Symmetrically, if $\tau$ is a strategy for Bob
+and $z \in \{0,1\}^{\mathbb{N}}$, we define $z \ast \tau$ as the
+confrontation in which Alice plays the terms of the sequence $z$ and
+Bob plays according to $\tau$.
+
+\textbf{(5)} If $\sigma$ is a strategy for Alice, explain in one line
+why the function $y \mapsto \sigma \ast y$ (from
+$\{0,1\}^{\mathbb{N}}$ to $\{0,1\}^{\mathbb{N}}$) is injective.
+
+\textbf{(6)} If $(a_\xi)_{\xi<\alpha}$ are any elements of
+$\{0,1\}^{\mathbb{N}}$, where $\alpha < \mathfrak{c}$, deduce from
+(4)(a) and (5) that there exists $y \in \{0,1\}^{\mathbb{N}}$ such
+that $\sigma \ast y$ is different from all $a_\xi$ for $\xi<\alpha$.
+
+\textbf{Assumption:} In questions (7) to (9), we assume that
+$(\sigma_\xi)_{\xi<\mathfrak{c}}$ are strategies for Alice and
+$(\tau_\xi)_{\xi<\mathfrak{c}}$ are strategies for Bob. We will
+define them after question (9), but we don't need to know more about
+them for now.
+
+\textbf{(7)} Assuming we are given elements $(a_\xi)_{\xi<\alpha}$ and
+$(b_\xi)_{\xi<\alpha}$ of $\{0,1\}^{\mathbb{N}}$, where $\alpha <
+\mathfrak{c}$, deduce in one line from the previous questions that
+there exists $b'$ which is of the form $\sigma_\alpha \ast y$ (for
+some $y \in \{0,1\}^{\mathbb{N}}$), but different from all $a_\xi$ for
+$\xi<\alpha$. Also explain why there exists $a'$ that is of the form
+$z \ast \tau_\alpha$ (for some $z \in \{0,1\}^{\mathbb{N}}$), but
+different from all $b_\xi$ for $\xi<\alpha$ and also different from
+the $b'$ that we have just found.
+
+We will admit that it poses no problem to \emph{choose} such $a'$ and
+$b'$ as a function of all the other parameters.
+
+\textbf{(8)} Deduce from all of the above that there exist $(a_\xi)_{\xi
+< \mathfrak{c}}$ and $(b_\xi)_{\xi < \mathfrak{c}}$ such that:
+\begin{itemize}
+\item none of the $a_\xi$ is equal to any of the $b_\zeta$ (i.e., for
+all $\xi<\mathfrak{c}$ and all $\zeta<\mathfrak{c}$, we have $a_\xi
+\neq b_\zeta$),
+\item for all $\xi < \mathfrak{c}$, there exists $y \in
+\{0,1\}^{\mathbb{N}}$ such that $b_\xi = \sigma_\xi \ast y$,
+\item for all $\xi < \mathfrak{c}$, there exists $z \in
+\{0,1\}^{\mathbb{N}}$ such that $a_\xi = z \ast \tau_\xi$.
+\end{itemize}
+(This is all we will need to know for the following questions.)
+
+\textbf{Definition:} Let us now call $A = \{a_\xi : \xi <
+\mathfrak{c}\}$ the set of the $a_\xi$ that we just constructed
+in (8).
+
+\textbf{(9)} Show that, for all $\xi$, the strategy $\tau_\xi$ is not
+a winning one for Bob in the game $G(A)$. Show that the strategy
+$\sigma_\xi$ is not a winning one for Alice in this same game (note:
+this is not completely symmetric since $A$ is the set of $a_\alpha$).
+
+\textbf{Definition:} Now let $\sigma_\xi := h_{\mathrm{A}}(u_\xi)$
+where $h_{\mathrm{A}}$ was defined in (1) and $u_\xi$ in (3), and
+similarly $\tau_\xi := h_{\mathrm{B}}(u_\xi)$.
+
+\textbf{(10)} Show that neither Alice nor Bob have a winning strategy
+in the game $G(A)$.
+
+\textbf{(11)} Why doesn't this contradict the results seen in class?
+What can be said about the subset $A$?
+
+\end{otherlanguage}
+
+
+
+
+%
+%
+%
+\end{document}
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 7d20177..d5fb37f 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1947,7 +1947,7 @@ devient de maximiser $v_+ - v_-$ sous les contraintes
\[-\sum_{a\in A_1} x_a \leq -1\]
\[(\forall b\in A_2)\;v_+ - v_- - \sum_{a \in A_1} u(a,b)\, x_a \leq 0\]
Le problème dual (minimiser ${^{\mathrm{t}}\textbf{q}} y$ sous les
-contraintes ${^{\mathrm{t}}\textbf{M}} y \geq {^\mathrm{t}\textbf{q}}$
+contraintes ${^{\mathrm{t}}\textbf{M}} y \geq {^\mathrm{t}\textbf{p}}$
et $y\geq 0$) est alors de minimiser $w_+ - w_-$ sous les contraintes
\[w_+\geq 0,\; w_- \geq 0,\;\; (\forall b\in A_2)\;y_b \geq 0\]
\[\sum_{b\in A_2} y_b \geq 1\]