%% 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. \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$ point par exercice (sur $20$) plus $0.5$ point bonus éventuel. \ifcorrige Ce corrigé comporte 9 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 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 faire 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 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é de la plus grande 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 perd immédiatement et que la suite des coups après ce point est arbitraire (sans importance pour le résultat). 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} % % % \exercise Si $b\geq 2$ est un entier naturel, on rappelle que l'écriture en base $b$ d'un entier naturel $n$ est l'unique écriture \[ n = b^{e_s}\, c_s + \cdots + b^{e_1}\, c_1 \] où $e_s > \cdots > e_1$ (appelés les \emph{exposants} de l'écriture) et $1\leq c_s,\ldots,c_1\leq b-1$ (appelés les \emph{chiffres} de l'écriture ; on omet le chiffre $0$, mais il faut évidemment autoriser la somme vide pour le nombre $0$ lui-même). On appelle \textbf{écriture en base $b$ itérée} l'écriture dans laquelle les exposants eux-mêmes sont écrits en base $b$ itérée. Par exemple, l'écriture en base $2$ itérée de $38$ (dont l'écriture binaire usuelle est $2^5 + 2^2 + 2^1$) est : \[ 2^{(2^2 + 1)} + 2^2 + 2 \] (en fait, si on veut être extrêmement précis, le $2$ le plus haut dans chaque tour d'exposants est mis pour $2^1$ où $1$ est lui-même mis ici pour $2^0$ ; et on n'a pas écrit les chiffres eux-mêmes, qui valent tous $1$). Si $n$ est un entier naturel, on définit la \textbf{suite de Goodstein} partant de $n$ de la manière suivante. Les termes de la suite sont indicés par les entiers naturels $b\geq 2$. Le premier terme de la suite est $g_2 := n$. Pour calculer le terme $g_{b+1}$ à partir de $g_b$, on effectue les opérations suivantes : \begin{itemize} \item écrire $g_b$ en base $b$ itérée, et remplacer chaque $b$ par $(b+1)$ dans cette écriture (sans changer les chiffres), \item puis soustraire $1$. \end{itemize} Par exemple, à partir de $n=19$, on a $g_2 = 19$, qui s'écrit en base $2$ itérée comme $2^{2^2} + 2 + 1$ ; on va donc le remplacer par $3^{3^3} + 3 + 1 = 7\,625\,597\,484\,991$ et soustraire $1$, si bien que le terme suivant est $g_3 = 7\,625\,597\,484\,990$. Le terme suivant sera alors obtenu à partir de $g_3 = 3^{3^3} + 3$ en remplaçant les $3$ par des $4$ et en soustrayant $1$, ce qui donne $g_4 = 4^{4^4} + 4 - 1 = 4^{4^4} + 3$ (un nombre valant environ $1.34\times 10^{154}$), puis on trouve $g_5 = 5^{5^5} + 2$, et ainsi de suite. La suite de Goodstein termine lorsqu'on atteint $0$ (si c'est le cas). \medbreak \textbf{(1)} Si $n$ est un entier naturel et $b\geq 2$, on définit un ordinal $f_b(n)$ de la façon suivante : écrire $n$ en base $b$ itérée et remplacer chaque $b$ par $\omega$ dans cette écriture (sans changer les chiffres). Par exemple, $f_2(38) = f_2(2^{(2^2 + 1)} + 2^2 + 2) = \omega^{(\omega^\omega+1)} + \omega^\omega + \omega$ tandis que $f_3(38) = f_3(3^3 + 3^2 + 2) = \omega^\omega + \omega^2 + 2$. Montrer que, à $b$ fixé, la fonction $f_b$ est strictement croissante (c'est-à-dire : si $n