diff options
Diffstat (limited to 'controle-20260622.tex')
| -rw-r--r-- | controle-20260622.tex | 805 |
1 files changed, 805 insertions, 0 deletions
diff --git a/controle-20260622.tex b/controle-20260622.tex new file mode 100644 index 0000000..a172f34 --- /dev/null +++ b/controle-20260622.tex @@ -0,0 +1,805 @@ +%% 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<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é 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<n'$ alors $f_b(n) < f_b(n')$). + +\begin{corrige} +Directement par la définition, $f_b(n)$ est un ordinal écrit en forme +normale de Cantor itérée, qui a, de plus, la propriété que tous les +chiffres de cette écriture sont $<b$. + +Or les écritures en base $b$ itérée des entiers naturels se comparent +lexicographiquement (car c'est déjà le cas des écritures en base $b$ +ordinaires) : on compare l'exposant de la plus grande puissance de $b$ +(celle écrite en premier) par le même algorithme récursivement, puis +le chiffre correspondant, puis l'exposant suivant, etc., jusqu'à +trouver la première différence. C'est exactement le même algorithme +pour la comparaison des formes normales de Cantor itérées des +ordinaux. + +Autrement dit, $f_b$ définit une bijection croissante entre les +entiers naturels et les ordinaux $<\varepsilon_0$ dont la forme +normale de Cantor itérée n'a que des chiffres $<b$. +\end{corrige} + +\medbreak + +\textbf{(2)} Si $(g_b)$ est une suite de Goodstein, on définit une +suite d'ordinaux de même longueur $(\gamma_b)$ avec $\gamma_b < +\varepsilon_0$ de la façon suivante : pour calculer $\gamma_b$, on +écrit $g_b$ en base $b$ itérée, et remplacer chaque $b$ par $\omega$ +dans cette écriture (sans changer les chiffres). Démontrer que +$\gamma_{b+1} < \gamma_b$. + +\begin{corrige} +La définition est donc : $\gamma_b = f_b(g_b)$. Comme $g_{b+1} + 1$ +s'obtient en remplaçant tous les $b$ par $(b+1)$ dans l'écriture en +base $b$ itérée de $g_b$, on a $\gamma_b = f_{b+1}(g_{b+1} + 1)$. +Comme $\gamma_{b+1} = f_{b+1}(g_{b+1})$ et que $g_{b+1} < g_{b+1} + +1$, par la question (1), on en déduit $\gamma_{b+1} < \gamma_b$. +\end{corrige} + +\medbreak + +\textbf{(3)} En déduire que toute suite de Goodstein est finie. + +\begin{corrige} +Si on avait une suite de Goodstein $(g_b)$ infinie, on en déduirait +par la construction $\gamma_b = f_b(g_b)$ de la question (2) une suite +d'ordinaux $(\gamma_b)$ infinie strictement décroissante. Ceci n'est +pas possible, donc toute suite de Goodstein est finie. +\end{corrige} + +\medskip + +{\footnotesize\textbf{À lire après l'épreuve, pour votre culture :} La + longueur de la suite de Goodstein commençant par $n$ est un exemple + de fonction à croissance extrêmement rapide (bien qu'elle soit + évidemment calculable) : par exemple, elle domine asymptotiquement + n'importe quelle fonction primitive récursive et même la fonction + d'Ackermann. On peut par ailleurs montrer que la finitude des suite + de Goodstein n'est pas prouvable dans l'arithmétique de Peano (il + est en quelque sorte nécessaire d'introduire l'ordinal + $\varepsilon_0$ pour la prouver).\par} + + + +% +% +% + +\refstepcounter{comcnt}\bigskip\noindent\textbf{Points bonus.} + +(Ceci n'est pas un exercice à résoudre mais un choix à faire.) + +Vous disposez de deux options : indiquez clairement sur votre copie si +vous choisissez « Bleu » ou « Rouge ». (Ce choix sera gardé secret.) + +Si au moins la moitié des participants de l'épreuve choisissent +« Bleu », alors $0.5$ points seront ajoutés à la note de tous les +participants. Sinon, $0.5$ points seront ajoutés à la note seulement +des participants qui ont choisi « Rouge », + + +% +% +% +\end{document} |