From 0d2a13c9ac180e4280002410a84c7ed5de0c9828 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 5 Apr 2022 14:57:36 +0200
Subject: Write a test for 2022.

---
 controle-20220413.tex | 439 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 439 insertions(+)
 create mode 100644 controle-20220413.tex

diff --git a/controle-20220413.tex b/controle-20220413.tex
new file mode 100644
index 0000000..66dfbfd
--- /dev/null
+++ b/controle-20220413.tex
@@ -0,0 +1,439 @@
+%% 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 de $u>v$, ce qu'on supposera désormais.
+
+(1) Expliquer brièvement pourquoi il ne change rien à l'analyse du jeu
+(p.ex., le 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 $(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).
+
+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 $n' < n_i$, soit par \emph{deux}
+$n',n''$ tels que $n' + n'' < n_i$ (on peut d'ailleurs ne considérer
+que ce deuxième type de coup vu que 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
+(bleue pour Blaise, 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) > 0$ si et seulement si Blaise possède une
+  stratégie gagnante à partir de la position $T$ (qui que soit le
+  joueur qui commence), et $v(T) < 0$ lorsque c'est Roxane, et $v(T) =
+  0$ lorsque c'est le second joueur.
+\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.
+
+\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}
-- 
cgit v1.2.3