path: root/controle-20260622.tex

%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[a4paper,margin=2.5cm]{geometry}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{ucs}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{matrix,calc}
\usepackage{hyperref}
%
%\externaldocument{notes-mitro206}[notes-mitro206.pdf]
%
\theoremstyle{definition}
\newtheorem{comcnt}{Whatever}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
\newcommand\exercise{%
\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
\renewcommand{\qedsymbol}{\smiley}
%
\newcommand{\outnb}{\operatorname{outnb}}
\newcommand{\downstr}{\operatorname{downstr}}
\newcommand{\precs}{\operatorname{precs}}
\newcommand{\mex}{\operatorname{mex}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\limp}{\Longrightarrow}
\newcommand{\gr}{\operatorname{gr}}
\newcommand{\rk}{\operatorname{rk}}
\newcommand{\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{2026-06-22}
\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 \textcolor{red}{XXX} pages (page de garde incluse).
\else
Cet énoncé comporte \textcolor{red}{XXX} pages (page de garde incluse).
\fi

\vfill
{\noindent\tiny
\immediate\write18{sh ./vc > vcline.tex}
Git: \input{vcline.tex}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pagebreak


%
%
%

\exercise

L'expérience de pensée suivante a circulé sur divers réseaux sociaux
en avril–mai 2026 :

\begin{narrower}
« Devant chaque personne sur Terre apparaissent deux boutons, un bleu
  et un rouge.  Chacun doit appuyer en secret sur l'un des deux.  Si
  au moins 50\% appuient sur le bouton bleu, tout le monde survit.
  Sinon, seuls ceux qui ont appuyé sur le bouton rouge survivent.  Que
  feriez-vous ? »\par
\end{narrower}

Nous allons étudier ce problème sous l'angle de la pure théorie des
jeux\footnote{En supposant, entre autres hypothèses simplificatrices
critiquables, que chacun n'est préoccupé que par sa propre survie.}.
On considère donc le jeu en forme normale suivant : $n\geq 2$ joueurs
doivent fait un choix simultané entre deux options, $B$ (bleu) et
$R$ (rouge) ; par ailleurs, on a fixé à l'avance\footnote{On suppose
tacitement que ce seuil, comme l'ensemble des règles du jeu, sont
connus de tous les joueurs.  Dans l'expérience de pensée du texte cité
ci-dessus ce serait $s = \lceil n/2\rceil$, le plus petit entier $\geq
n/2$, mais ceci n'aura pas d'impact sur le raisonnement donc on ne
supposera rien.} un nombre $2 \leq s \leq n$.  Le gain des joueurs est
déterminé par les règles suivantes :
\begin{itemize}
\item si $\geq s$ joueurs ont choisi l'option $B$, alors le gain de
  chaque joueur est $0$ ;
\item sinon (c'est-à-dire : si $> n-s$ joueurs ont choisi
  l'option $R$), alors le gain des joueurs ayant choisi $R$ est $0$ et
  celui des joueurs ayant choisi l'option $B$ est $-1$.
\end{itemize}

Le but de l'exercice est de déterminer les équilibres de Nash de ce
jeu.

On rappelle qu'on dit que $R$ est dans le \textbf{support} d'une
stratégie (mixte) $(1-p) B + p R$ lorsque $p>0$, et que $B$ est dans
le support de $(1-p) B + p R$ lorsque $p<1$.

\medskip

\textbf{(1)} Considérons un joueur $i$ particulier.\quad
\textbf{(a)} Montrer que si $> n-s$ des $n-1$ autres joueurs jouent
une stratégie ayant $R$ dans son support, alors le joueur $i$
considéré a une espérance de gain strictement plus grande en
jouant $R$ qu'en jouant $B$.  (On demande une démonstration
mathématiquement précise ici.)\quad\textbf{(b)} Montrer qu'au
contraire si $\leq n-s$ des autres joueurs jouent une stratégie ayant
$R$ dans son support, alors le joueur $i$ a une espérance de gain
égale à $0$ quel que soit son choix.

\begin{corrige}
\textbf{(a)} Appelons $\mathscr{R}$ l'ensemble des joueurs $j \neq i$
qui jouent une stratégie $(1-p_j) B + p_j R$ ayant $R$ dans son
support (les autres jouent donc la stratégie pure $B$).  Le gain du
joueur $i$ est $0$ s'il joue $R$ ; s'il joue $B$, son gain est
l'opposé de la probabilité (appelons-la $q$) que $> n-s$ joueurs
jouent $R$.  Si le cardinal $\#\mathscr{R}$ de $\mathscr{R}$ vaut $>
n-s$, alors cette probabilité $q$ vaut $\geq\prod_{j\in\mathscr{R}}
p_j > 0$ (puisque au moins dans le cas où chaque joueur
$j\in\mathscr{R}$ joue effectivement $R$, l'événement « $>
n-s$ joueurs jouent $R$ » se sera produit) ; et alors l'espérance du
gain du joueur $i$ considéré est strictement plus grande (à
savoir $0$) en jouant $R$ que s'il joue $B$ (à savoir $-q$).  C'est ce
qui était demandé.

\textbf{(b)} Si le joueur $i$ considéré joue $R$, son gain vaut de
toute façon $0$ donc il n'y a rien à prouver.  Mais s'il joue $B$,
comme on a supposé que $\leq n-s$ des autres joueurs jouent $R$, on
est dans le cas où $\geq s$ joueurs jouent $B$, et le gain de tous les
joueurs vaut $0$, donc l'affirmation de l'énoncé est vraie aussi.
\end{corrige}

\medskip

\textbf{(2)} En déduire que, dans un équilibre de Nash, si $B$ est
dans le support de la stratégie d'un certain joueur $i$, alors $\leq
n-s$ des autres joueurs jouent une stratégie ayant $R$ dans le
support.

\begin{corrige}
Si $B$ est dans le support de la stratégie du joueur $i$, alors c'est
une meilleure réponse possible au profil de stratégie des autres
joueurs, et d'après (1)(a), ceci implique que $\leq n-s$ des autres
joueurs jouent une stratégie ayant $R$ dans son support.
\end{corrige}

\medskip

\textbf{(3)} Considérons un équilibre de Nash et appelons
respectivement : $n_B$ le nombre de joueurs qui jouent la stratégie
pure $B$ ; $n_R$ ceux qui jouent la stratégie pure $R$, et $n_M$ ceux
qui jouent une stratégie mixte $(1-p) B + p R$ ayant à la fois
$B$ et $R$ dans le support (i.e., telle que $0<p<1$).  En appliquant
la question (2) à un joueur bien choisi, montrer que :
\begin{itemize}
\item[\textbf{(a)}] si $n_B > 0$, alors $n_M + n_R \leq n-s$
  (c'est-à-dire $n_B \geq s$) ;
\end{itemize}
et, d'autre part, que :
\begin{itemize}
\item[\textbf{(b)}] si $n_M > 0$, alors $n_M + n_R \leq n-s+1$
  (c'est-à-dire $n_B \geq s-1$).
\end{itemize}

\begin{corrige}
Observons avant tout que $n_B + n_M + n_R = n$ de façon évidente.

Pour montrer (a) : si $n_B > 0$, on peut appliquer la question (2) à
un joueur $i$ qui joue la stratégie pure $B$ ; elle nous permet de
dire que $\leq n-s$ des autres joueurs jouent une stratégie ayant $R$
dans le support, et comme $i$ lui-même joue purement $B$, on voit que
$\leq n-s$ parmi tous les joueurs jouent une stratégie ayant $R$ dans
le support, c'est-à-dire $n_M + n_R \leq n-s$, c'est-à-dire $n_B \geq
s$.

Pour montrer (b) : si $n_M > 0$, on peut appliquer la question (2) à
un joueur $i$ qui joue une stratégie ayant à la fois $B$ et $R$ dans
le support ; elle nous permet de dire que $\leq n-s$ des autres
joueurs jouent une stratégie ayant $R$ dans le support, et comme $i$
lui-même compte aussi, on voit que $\leq n-s+1$ parmi tous les joueurs
jouent une stratégie ayant $R$ dans le support, c'est-à-dire $n_M +
n_R \leq n-s+1$, c'est-à-dire $n_B \geq s-1$.
\end{corrige}

\medskip

\textbf{(4)} Conclure qu'il y a deux sortes d'équilibres de Nash :
\begin{itemize}
\item ceux où $\geq s$ joueurs jouent la stratégie pure $B$,
\item celui où \emph{tous} les joueurs jouent la stratégie pure $R$.
\end{itemize}
On vérifiera que ce sont bien des équilibres de Nash.

\begin{corrige}
Si on garde la notation $(n_B,n_M,n_R)$ de la question (3) pour un
équilibre de Nash, on a soit $n_R < n$ soit $n_R = n$.  Le second cas
correspond bien à la situation où tous les joueurs jouent la stratégie
pure $R$.  Dans le second cas, $n_B + n_M > 0$ donc soit $n_B > 0$
soit $n_M > 0$.  Si $n_B > 0$, alors (3)(a) donne $n_B \geq s$,
c'est-à-dire qu'on est dans la situation où $\geq s$ joueurs jouent la
stratégie pure $B$ ; mais si $n_M > 0$, alors (3)(b) donne $n_B \geq
s-1 > 0$ car $s \geq 2$, et on est ramené au cas qu'on vient de
traiter.  Ceci achève de démontrer que tout équilibre de Nash est
d'une des deux sortes qu'on a dites.

Montrons enfin que ce sont effectivement des équilibres de Nash : pour
ce qui est de la première sorte, il y a $\leq n-s$ joueurs jouant une
stratégie ayant $R$ dans son support, donc c'est exactement ce
qu'affirme la question (1)(b).  Et pour la seconde sorte, c'est
évident (l'option $R$ est une meilleure réponse à n'importe quel
profil de stratégies des autres joueurs).
\end{corrige}

\medskip

\textbf{(5)} Pour $n=3$ et $s=2$, faire un dessin dans l'espace
$(p_1,p_2,p_3)$ (où $(1-p_i) B + p_i R$ est la stratégie du
joueur $i$) où on montrera le domaine des profils de stratégies mixtes
possibles, et la partie correspondant aux équilibres de Nash.

\begin{corrige}
On dessine un cube de côté $1$ : l'ensemble du cube $[0,1]^3$
correspond aux profils de stratégies mixtes $(p_1,p_2,p_3)$
possibles ; la partie correspondant aux équilibres de Nash est le
sommet $(1,1,1)$ (tous les joueurs jouent purement $R$) ainsi que la
réunion des trois arêtes passant par $(0,0,0)$ (correspond aux
situations où deux joueurs jouent purement $B$ et le troisième suit
une stratégie quelconque).
\end{corrige}

\medskip

\textbf{(6)} La conclusion de la question (4) est fausse pour $s=1$ :
expliquer pourquoi, et indiquer à quel endroit dans le raisonnement on
a utilisé l'hypothèse $s\geq 2$.

\begin{corrige}
Pour $s=1$, le jeu est trivial : le gain de chaque joueur est
toujours $0$ (en effet, si tous les joueurs jouent $R$, leur gain
est $0$ de toute façon, et si un joueur joue $B$ alors le gain de tous
les joueurs est $0$ par la première clause des règles).  Il s'ensuit
que n'importe quel profil de stratégies mixtes est un équilibre de
Nash, et ils ne sont pas tous d'une des deux sortes qu'on a dites
en (4).  L'hypothèse $s\geq 2$ a été utilisée en (4), juste après
l'utilisation de la question (3)(b), pour passer de $n_B \geq s-1$ à
$n_B > 0$.
\end{corrige}


%
%
%

\exercise

Le but de cet exercice est de montrer la détermination d'une certaine
généralisation des jeux combinatoires étudiés en cours : les « jeux de
parité ».

Pour simplifier la terminologie, faisons d'abord la définition
suivante : si $(u_0,u_1,u_2,\ldots) \in X^{\mathbb{N}}$ est une suite
(infinie) à valeurs dans un ensemble $X$, on dira qu'une valeur $v \in
X$ est \textbf{infiniment récurrente} pour la suite lorsque la suite
prend cette valeur un nombre infini de fois, c'est-à-dire : $\forall
n\in\mathbb{N}.\; \exists i\geq n.\; (u_i = v)$ ; ou, ce qui revient
au même, $\{i\in\mathbb{N} : u_i=v\}$ est infini.  Il est clair que
toute suite (infinie) à valeurs dans un ensemble fini possède au moins
une valeur infiniment récurrente (on ne demande pas de justifier ce
fait, qu'on pourra utiliser).

Un \textbf{jeu de parité} est défini par la donnée : d'un graphe
orienté $G$ (qui n'est pas supposé fini, ni bien-fondé) ; d'un sommet
$x_0$ de $G$ appelé « position initiale » ; et d'une fonction $\pi
\colon G \to \mathbb{N}$ \emph{bornée}\footnote{C'est-à-dire qu'il
existe $N\in\mathbb{N}$ tel que $\pi$ ne prenne que des valeurs $\leq
N$.}, appelée « priorité ».  La règle du jeu est la suivante : les
joueurs Impair et Pair alternent, chacun choisissant un voisin sortant
de la position actuelle (c'est-à-dire que Impair commence en
choisissant $x_1$ voisin sortant de $x_0$, puis Pair choisit $x_2$
voisin sortant de $x_1$, puis Impair choisit $x_3$ voisin sortant
de $x_2$, et ainsi de suite).  Le gagnant est défini par les règles
suivantes :
\begin{itemize}
\item si un joueur ne peut pas jouer, ce joueur perd (i.e., son
  adversaire gagne) ;
\item si la confrontation $\dblunderline{x} :=
  (x_0,x_1,x_2,x_3,\ldots)$ dure un temps infini, alors (puisque $\pi$
  était supposée bornée) il existe au moins une valeur qui soit
  infiniment récurrente pour la suite $(\pi(x_0), \pi(x_1), \ldots)$
  des priorités des sommets parcourus : le gagnant est alors donné par
  la parité du maximum de ces valeurs (autrement dit, on pose $u_i =
  \pi(x_i)$, on appelle $p := \max\{v : v\text{~infiniment récurrente
    dans~}(u_i)\}$ et Impair gagne si $p$ est impair tandis que Pair
  gagne si $p$ est pair).
\end{itemize}
Pour le dire de façon plus courte, le jeu se joue comme un jeu
combinatoire normal, mais si la confrontation est infinie, au lieu de
considérer que cela conduit à une issue nulle, le gagnant est donné
par la parité de la plus grande priorité infiniment récurrente.  Il a
donc toujours un gagnant et un perdant.

{\footnotesize (Intuitivement, on peut imaginer le jeu ainsi : les
  sommets $x$ avec $\pi(x)$ pair donnent un petit avantage au joueur
  Pair, les sommets avec $\pi(x)$ impair donnent un petit avantage au
  joueur Impair ; et cet avantage est d'autant plus important que
  $\pi(x)$ est grand.  Si l'issue de la confrontation n'est pas
  déterminée par le fait qu'un joueur soit dans l'impossibilité de
  jouer, elle l'est par le fait qu'un de ces petits avantages se soit
  infiniment accumulé.)\par}

\medskip

\textbf{(1)} À titre d'exemple, considérons le graphe $G =
\{g_0,g_1,g_2\}$ avec une arête de chaque $g_i$ vers chaque autre
$g_j$ (où $j\neq i$), la position initiale $g_0$, et les priorités
$\pi(g_i) = i$.  Décrire une stratégie gagnante explicite pour Pair
dans ce jeu.

\begin{corrige}
Pair peut jouer de la manière suivante : si la position actuelle est
$g_0$ ou $g_1$, il joue vers $g_2$, sinon, il joue vers $g_0$.
(Notons qu'il joue toujours vers un sommet dans $\{g_0,g_2\}$.)  Si la
position $g_1$ est infiniment récurrente dans une confrontation, alors
c'est forcément Impair qui a joué infiniment souvent vers cette
position (puisque Pair joue toujours dans $\{g_0,g_2\}$), donc au coup
suivant Pair joue vers $g_2$, et alors $g_2$ est infiniment récurrente
aussi.  Donc la plus grande priorité infiniment récurrente ne peut pas
être $1$, seule priorité impaire, donc elle est paire et Pair gagne.
\end{corrige}

\medskip

On va maintenant montrer que les jeux de parité sont toujours
déterminés, c'est-à-dire qu'un des joueurs a une stratégie
gagnante\footnote{On autorise ici les stratégies \emph{historiques},
c'est-à-dire que le coup choisi a le droit de dépendre de tous les
coups antérieurs et pas seulement de la position actuelle.  (Il
s'avère que les jeux de parité sont aussi déterminés pour les
stratégies positionnelles, mais on ne s'intéressera pas à cette
subtilité ici.)}.

\medskip

\textbf{(2)} Montrer que, pour $i,v\in\mathbb{N}$, l'ensemble
\[
S_{i,v} := \{\dblunderline{x}\in G^{\mathbb{N}} : \pi(x_i) = v\}
\]
est \emph{ouvert} (sous-entendu : pour la topologie produit de la
topologie discrète) dans $G^{\mathbb{N}}$.

\begin{corrige}
Si $\dblunderline{x} \in S_{i,v}$ alors toute suite commençant par les
mêmes valeurs $x_0,\ldots,x_i$ que $\dblunderline{x}$ est encore
dans $S_{i,v}$, c'est-à-dire que $S_{i,v}$ contient le $(i+1)$-ième
voisinage fondamental de $\dblunderline{x}$, donc en est un voisinage,
et ceci montre que $S_{i,v}$ est ouvert.
\end{corrige}

\medskip

\textbf{(3)} Pour $v\in\mathbb{N}$, montrer que l'ensemble $P_v$ des
suites $\dblunderline{x}\in G^{\mathbb{N}}$ pour lesquelles la
priorité $v$ est infiniment récurrente est :
\[
\bigcap_{n=0}^{+\infty} \bigcup_{i=n}^{+\infty} S_{i,v}
\]
— et que l'ensemble $M_v$ de celles pour lesquelles pour lesquelles
$v$ est précisément la plus grande priorité infiniment récurrente
est :
\[
P_v \setminus \bigcup_{w=v+1}^{+\infty} P_w
\]

\begin{corrige}
Dire que $v$ est infiniment récurrente signifie :
\[
\forall n\in\mathbb{N}.\; \exists i\geq n.\; (\pi(x_i) = v)
\]
C'est exactement dire que $\dblunderline{x} \in
\bigcap_{n=0}^{+\infty} \bigcup_{i=n}^{+\infty} S_{i,v}$ d'après la
définition de $S_{i,v}$, et de l'intersection et de la réunion.

Dire que $v$ est la plus grande priorité infiniment récurrente
signifie exactement qu'elle l'est et qu'aucune priorité $w\geq v+1$ ne
l'est, c'est-à-dire que $\dblunderline{x} \in P_v \setminus
\bigcup_{w=v+1}^{+\infty} P_w$.
\end{corrige}

\medskip

\textbf{(4)} Pour avoir toujours affaire à des confrontations
infinies, lorsqu'un joueur ne peut plus jouer selon les règles, on
conviendra qu'il joue n'importe quoi et a automatiquement perdu (i.e.,
la suite des coups après est arbitraire et sans importance).  En
reprenant un raisonnement du cours, rappeler pourquoi $G^{\mathbb{N}}$
est la réunion disjointe $A \cup B \cup D$ où $A$, resp. $B$ sont des
ouverts décrivant des confrontations gagnées par Impair, resp. Pair
parce que l'autre joueur a violé en premier la règle de choisir un
voisin sortant, et $D$ est un fermé décrivant les confrontations où
chaque $x_{i+1}$ est un voisin sortant de $x_i$.

\begin{corrige}
Appelons $D$ l'ensemble des suites $\dblunderline{x} \in
G^{\mathbb{N}}$ telles que chaque $x_{i+1}$ est un voisin sortant
de $x_i$, et $A$ l'ensemble des suites telles qu'il existe $i$ tel que
$x_{i+1}$ n'est pas un voisin sortant de $x_i$ et que le plus petit
tel $i$ est impair (i.e., Pair a violé la règle en premier, donc
Impair gagne), et $B$ l'ensemble des suites telles qu'il existe $i$
tel que $x_{i+1}$ n'est pas un voisin sortant de $x_i$ et que le plus
petit tel $i$ est pair (i.e., Impair a violé la règle en premier, donc
Pair gagne).  Il est clair que $G^{\mathbb{N}} = A \cup B \cup D$,
réunion disjointe.  Les ensembles $A,B$ sont ouverts comme on l'a vu
en cours (rappel : si $i$ est le plus petit tel que $x_{i+1}$ n'est
pas un voisin sortant de $x_i$, alors toute suite commençant par
$x_0,\ldots,x_{i+1}$ a la même propriété) ; l'ensemble $D$ est donc
fermé comme complémentaire de l'ouvert $A\cup B$.
\end{corrige}

\medskip

\textbf{(5)} Dans les notations des questions (2)–(4), quelle est la
partie de $G^{\mathbb{N}}$ décrivant exactement les confrontations
gagnées par Impair ?

\begin{corrige}
Il s'agit de l'ensemble
\[
A \cup \left(D \cap \bigcup_{k=0}^{+\infty} M_{2k+1}\right)
\]
correspondant aux deux façons de gagner : soit Pair ne peut plus jouer
et viole la règle (la confrontation est dans $A$), soit la règle est
suivie jusqu'au bout et la plus grande priorité infiniment récurrente
est impaire.

(Pour les pinailleurs : il y a un problème de numérotation des suites,
puisque Impair joue en premier avec le choix de $x_1$.  On peut
résoudre cette petite difficulté en numérotant les suites à partir
de $1$, ou en convenant que Pair joue en premier et perd immédiatement
s'il ne choisit pas la position initiale $x_0$ imposée.  Ça ne change
rien et ce n'est pas important ici.)
\end{corrige}

\medskip

\textbf{(6)} En appliquant un théorème vu en cours, conclure que le
jeu est déterminé.

\begin{corrige}
On rappelle que les boréliens sont la plus petite partie de
$\mathscr{P}(G^{\mathbb{N}})$ contenant les ouverts et stable par
complémentaire et réunions dénombrables (donc aussi intersections
dénombrables).

L'ensemble $S_{i,v}$ est borélien car ouvert.  L'ensemble
$\bigcup_{i=n}^{+\infty} S_{i,v}$ est donc aussi borélien (en fait,
ouvert).  L'ensemble $P_v := \bigcap_{n=0}^{+\infty}
\bigcup_{i=n}^{+\infty} S_{i,v}$ est donc aussi borélien (intersection
dénombrable de boréliens).  L'ensemble $\bigcup_{w=v+1}^{+\infty} P_w$
est donc aussi borélien (réunion dénombrable de boréliens).
L'ensemble $M_v := P_v \setminus \bigcup_{w=v+1}^{+\infty} P_w$,
c'est-à-dire $P_v \cap (G^{\mathbb{N}} \setminus
\bigcup_{w=v+1}^{+\infty} P_w)$ est donc aussi borélien (intersection
d'un borélien et du complémentaire d'un borélien).  L'ensemble
$\bigcup_{k=0}^{+\infty} M_{2k+1}$ est donc encore borélien.
L'ensemble $D$ est fermé, donc borélien (complémentaire d'un ouvert),
et l'ensemble $A$ est ouvert, donc borélien.  Donc finalement,
l'ensemble $A \cup \left(D \cap \bigcup_{k=0}^{+\infty}
M_{2k+1}\right)$ trouvé en (5) est borélien.

Le théorème de détermination borélienne pour les jeux de Gale-Stewart,
vu en cours, s'applique donc et permet de conclure que le jeu de
parité considéré est déterminé.
\end{corrige}

\medskip

{\footnotesize\textbf{À lire après l'épreuve, pour votre culture :}
  Les jeux de parité, dans le cas où $G$ est fini, ont une grande
  importance en informatique théorique, notamment en théorie de la
  complexité parce que la question de décider quel joueur a une
  stratégie gagnante est un problème qui est connu pour être à la fois
  dans $\mathbf{NP}$ et $\mathbf{coNP}$ (et même « quasipolynomial »),
  mais dont on ignore s'il est dans $\mathbf{P}$.\par}


%
%
%

\exercise

Dans cet exercice, on considère une variante du jeu de nim (fini) dans
laquelle on limite le nombre de bâtonnets qui peuvent être retirés en
un seul coup.

\medskip

\textbf{(1)} Soit $k\geq 1$ un entier naturel, et soit
$n\in\mathbb{N}$ un entier naturel.  On considère le jeu combinatoire
dans lequel il y a une seule rangée de bâtonnets, initialement avec
$n$ bâtonnets, et où chaque joueur, quand vient son tour, retire un
nombre quelconque entre $1$ et $k$ bâtonnets.  (Plus exactement, les
positions du jeu sont les entiers $i$ avec $0\leq i\leq n$, et on peut
passer de la position $i$ à la position $j$ lorsque $1\leq i-j\leq
k$.)  Comme d'habitude, le joueur qui ne peut pas jouer perd.
Calculer la valeur de Grundy $\mathrm{g}_k(n)$ de ce jeu.
(\textit{Indication :} On pourra commencer par calculer à la main les
valeurs $\mathrm{g}_k(i)$ pour $0\leq i\leq k$, puis
$\mathrm{g}_k(k+1)$ et plus si besoin est, et s'en servir pour
conjecturer une formule générale que l'on démontrera.)

\begin{corrige}
La définition de la fonction de Grundy donne :
\[
\mathrm{g}_k(n) = \mex\{\mathrm{g}_k(i) : \max(0,n-k) \leq i \leq n-1\}
\]
où comme d'habitude $\mex S$ désigne le plus petit entier naturel qui
n'est pas dans $S$.  Tant que $n\leq k$, on a donc juste
$\mathrm{g}_k(n) = n$ comme au jeu de nim ; en revanche,
$\mathrm{g}_k(k+1) = \mex\{1,2,\ldots,k\} = 0$ ; on a ensuite
$\mathrm{g}_k(k+2) = \mex\{0,2,\ldots,k\} = 1$, et ainsi de suite.  On
voit donc qu'il y a périodicité de période $k+1$.  Par récurrence
sur $n$ on montre donc
\[
\mathrm{g}_k(n) = n \% (k+1)
\]
où $n \% (k+1)$ désigne le reste (compris entre $0$ et $k$ inclus) de
la division euclidienne de $n$ par $k+1$.  On a déjà vu que c'était le
cas pour $0\leq n\leq k$ ; et si $n>k$, on a $\mathrm{g}_k(n) =
\mex\{\mathrm{g}_k(i) : n-k \leq i \leq n-1\}$, où (par hypothèse de
récurrence) l'ensemble dont on prend le $\mex$ contient tous les
restes des divisions euclidiennes modulo $k+1$ à l'exception de celle
de $n$, qui est donc la valeur de $\mathrm{g}_k(n)$, ce qui conclut la
récurrence.
\end{corrige}

\medskip

\textbf{(2)} On considère maintenant le jeu combinatoire suivant : une
position consiste en un certain nombre de bâtonnets $n_1,\ldots,n_r$
arrangés en lignes (où $n_k$ désigne le nombre de bâtonnets sur la
ligne numérotée $k$) ; chaque joueur, quand vient son tour, retire des
bâtonnets selon les règles suivantes :
\begin{itemize}
\item comme au jeu de nim usuel, les bâtonnets retirés sont sur une et
  une seule ligne (i.e., un des $n_k$ est remplacé par un $n'_k$ avec
  $n'_k < n_k$), mais en plus
\item le nombre de bâtonnets retirés ne peut pas excéder le numéro de
  la ligne (i.e., $1 \leq n_k - n'_k \leq k$ : on peut retirer au plus
  $1$ bâtonnet de la première ligne, ou au plus $2$ de la deuxième,
  etc.).
\end{itemize}
En exprimant ce jeu en fonction des jeux considérés à la question (1),
exprimer la valeur de Grundy de la position $(n_1,\ldots,n_r)$ en
fonction des $\mathrm{g}_k(i)$.

\begin{corrige}
Comme les différentes lignes n'interagissent pas du tout, le jeu qu'on
a décrit est la somme disjonctive du jeu décrit à la question (1) pour
les différents $k$ qui numérotent les lignes.  D'après le théorème vu
en cours sur le calcul de la fonction de Grundy d'une somme
disjonctive, la valeur de Grundy recherchée est la somme de nim (=XOR)
$\bigoplus_{k=1}^r \mathrm{g}_k(n_k) = \bigoplus_{k=1}^r (n \%
(k+1))$.
\end{corrige}

\medskip

\textbf{(3)} Exemple : calculer la valeur de Grundy de la position
$(1,3,5,7)$ (soit $1$ bâtonnet sur la ligne $1$, $3$ sur la ligne $2$,
etc.) pour le jeu décrit en (2).  Quel coup feriez-vous si vous deviez
jouer en premier à partir de cette position ?

\begin{corrige}
On trouve :
\begin{itemize}
\item $n_1 \% (1+1) = 1 \% 2 = 1$,
\item $n_2 \% (2+1) = 3 \% 3 = 0$,
\item $n_3 \% (3+1) = 5 \% 4 = 1$,
\item $n_4 \% (4+1) = 7 \% 5 = 2$.
\end{itemize}
Le XOR de tous ces nombres est $2$ : comme cette valeur de Grundy est
non nulle, le premier joueur a une stratégie gagnante.  Pour trouver
un coup gagnant, on cherche à trouver un $k$ et un $n'_k$ tel que le
remplacement de $n_k$ par $n'_k$ annule la valeur de Grundy.  Le plus
évident est de remplacer $n_4 = 7$ par $n'_4 = 5$ (i.e., retirer
$2$ bâtonnets de la ligne $4$) ; mais on peut aussi remplacer $n_2 =
3$ par $n'_2 = 2$ (i.e., retirer $1$ bâtonnet de la ligne $2$) ou bien
remplacer $n_3 = 5$ par $n'_3 = 3$ (i.e., retirer $2$ bâtonnets de la
ligne $3$).
\end{corrige}


%
%
%
\end{document}