path: root/controle-20190408.tex

%% 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{8 avril 2019}
\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} : exercice 1 : $3$ points ; exercice 2 :
$4$ points ; exercice 3 : $10$ points ; exercice 4 : $3$ points ;
points bonus : comme indiqué.

\emph{Avertissement :} Les exercices ne sont pas tous une application
immédiate du cours ; il est parfois nécessaire de s'inspirer des
techniques ou raisonnements vus en cours pour raisonner dans des
cadres légèrement différents.

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

\pagebreak


%
%
%

\exercice

On s'intéresse dans cet exercice à des jeux à deux joueurs (que l'on
appellera Alice et Bob) de la forme suivante :
\begin{itemize}
\item Alice et Bob sont autour d'une table sur laquelle se trouvent un
  certain nombre (fini) de \emph{jetons} ; chaque jeton porte un
  entier naturel qu'on appellera son \emph{type} ; il peut y avoir
  plusieurs jetons de même type (par exemple, trois jetons de
  type $0$, deux jetons de type $1$ et un jeton de type $1729$) ; le
  nombre (fini) de jetons de jetons de chaque type constitue l'état du
  jeu, et il est visible de tous ;
\item Alice et Bob jouent tour à tour, et chacun, quand vient son
  tour, doit retirer un jeton de la table et le \emph{remplacer}
  éventuellement par des jetons de type(s) strictement plus petit(s) :
  les règles exactes de remplacement seront différentes d'une question
  à l'autre, mais prendront toujours la forme « un joueur peut
  remplacer un jeton de type $n$ par telle ou telle combinaison de
  jetons de types $<n$ » ; dans tous les cas, un coup consiste à
  retirer un unique jeton et à en poser éventuellement plusieurs ; il
  y aura toujours au moins une manière de remplacer un jeton de
  type $n$ donné ;
\item il n'y a aucune interaction entre les jetons, c'est-à-dire que
  les remplacements permis pour un jeton de type $n$ ne dépendront que
  de $n$ et pas des autres jetons présents sur la table (ni de
  l'identité du joueur, ni du numéro du coup, ni de quelque autre
  information) ;
\item on notera que les jetons de type $0$ ne peuvent être que retirés
  (il n'y a aucun remplacement possible puisqu'il n'existe pas de
  jeton de type $<0$) ;
\item le gagnant est celui qui retire le dernier jeton (puisque son
  adversaire ne peut plus jouer).
\end{itemize}

\smallskip

Dans les questions (1) à (3), on ne fait pas d'hypothèse particulière
sur les règles de remplacement autre que celles qui sont indiquées
ci-dessus.  Dans les questions (4) à (6), on traite le cas de règles
de remplacement particulières.

\medskip

(1) Montrer que le jeu termine toujours en temps fini.  On pourra pour
cela associer judicieusement un ordinal à l'état du jeu et montrer
qu'il décroît strictement à chaque tour.

\medskip

(2)(a) En notant $J(n_1,\ldots,n_r)$ l'état du jeu dans lequel $r$
jetons se trouvent sur la table et ont les types $n_1,\ldots,n_r$
(éventuellement répétés, p.ex. $J(0,0,0,1,1,1729)$), expliquer
pourquoi $J(n_1,\ldots,n_r)$ peut s'identifier à la somme de nim des
positions $J(n_1),\ldots,J(n_r)$ (où $J(n)$ désigne l'état du jeu
ayant un unique jeton de type $n$).\quad(b) En déduire la valeur de
Grundy $\gr J(n_1,\ldots,n_r)$ de $J(n_1,\ldots,n_r)$ en fonction de
celles $\gr J(n_i)$ des $J(n_i)$.\quad(c) Qui a une stratégie gagnante
dans une position du type $J(n,n)$ ?  Expliciter une telle stratégie
en termes simples.

(\emph{Convention :} $J()$ est le jeu nul dans lequel il ne reste plus
aucun jeton.  Notamment, on a $\gr J() = 0$.)

\medskip

(3)(a) Pour une règle de remplacement $\mathscr{R}$ donnée, en notant
par exemple $\mathscr{R}_n$ l'ensemble (non vide) de tous les
remplacements possibles d'un jeton de type $n$ (considérés comme des
suites finies d'entiers $<n$), expliquer comment on peut calculer $\gr
J(n)$ si on suppose connus tous les $\gr J(n')$
pour $n'<n$.\quad(b) On rappelle que le seul remplacement possible
d'un jeton de type $0$ est de l'enlever purement et simplement (i.e.,
$\mathscr{R}_0 = \{()\}$ si on veut) : en déduire la valeur de $\gr
J(0)$ et celle de $\gr J(0,\ldots,0)$ (avec, disons, $r$ jetons de
type $0$).

\medskip

(4) On suppose dans cette question que la règle de remplacement est la
suivante : un joueur peut remplacer un jeton de type $n$ par un nombre
quelconque (y compris $0$) de jetons de type $n-1$.  (Autrement dit, à
chaque coup, le joueur retire un jeton de type $n$ et si $n>0$ il
ajoute ensuite, optionnellement, le nombre qu'il souhaite de jetons de
type $n-1$.  Par exemple, on peut remplacer un jeton de type $1729$
par $42$ jetons de type $1728$ ; on peut aussi le retirer sans
remplacement.)\quad(a) Dans ces conditions, que vaut $\gr J(n)$ ?  (On
pourra par exemple commencer par calculer $\gr J(n)$ pour $n=0,1,2,3$,
conjecturer une formule générale, et la démontrer par récurrence
sur $n$.)\quad(b) Exprimer de façon simple la stratégie gagnante du
jeu considéré dans cette question.

\medskip

(5) On suppose dans cette question que la règle de remplacement est la
suivante : un joueur peut remplacer un jeton de type $n$ par un nombre
quelconque (y compris $0$) de jetons de type $k<n$, mais le type doit
être le même pour tous les jetons remplacés.  (Autrement dit, à chaque
coup, le joueur retire un jeton de type $n$ et si $n>0$ il ajoute
ensuite, optionnellement, le nombre qu'il souhaite de jetons d'un même
type $k\leq n-1$.  Par exemple, on peut remplacer un jeton de
type $1729$ par $42$ jetons de type $1728$ ou $1728$ jetons de
type $42$ ; on peut aussi le retirer sans remplacement.)  Dans ces
conditions, que vaut $\gr J(n)$ ?  (On pourra par exemple commencer
par calculer $\gr J(n)$ pour $n=0,1,2,3$, conjecturer une formule
générale, et la démontrer par récurrence sur $n$.)

\medskip

(6) On suppose dans cette question que la règle de remplacement est la
suivante : un joueur peut remplacer un jeton de type $n$ par un nombre
quelconque (y compris $0$) de jetons de types $<n$.  (Autrement dit, à
chaque coup, le joueur retire un jeton de type $n$ et si $n>0$ il
ajoute ensuite, optionnellement, le nombre qu'il souhaite de jetons de
n'importe quels types $<n$.  Par exemple, on peut remplacer un jeton
de type $1729$ par $42$ jetons de type $1728$ et $666$ de type $0$ ;
on peut aussi le retirer sans remplacement.)\quad(a) Dans ces
conditions, que vaut $\gr J(n)$ ?  (On pourra par exemple commencer
par calculer $\gr J(n)$ pour $n=0,1,2,3$, conjecturer une formule
générale, et la démontrer par récurrence sur $n$.)\quad(b) Exprimer de
façon simple la stratégie gagnante du jeu considéré dans cette
question.


%
%
%

\exercice

On définit une opération binaire $\alpha\boxplus\beta$ (appelée
« somme naturelle » ou « somme de Hessenberg ») sur les ordinaux (ici
notés $\alpha,\beta$) par la formule suivante :
\[
\alpha \boxplus \beta = \sup\nolimits^+ \Big( \{\alpha'\boxplus\beta :
\alpha' < \alpha\} \cup\, \{\alpha\boxplus\beta' : \beta' <
\beta\}\Big)
\]
où on rappelle que $\sup^+ S$, si $S$ est un ensemble d'ordinaux,
désigne \emph{le plus petit ordinal strictement plus grand que tous
  les éléments de $S$} (c'est aussi $\sup\{\gamma+1 : \gamma\in S\}$
mais c'est probablement moins utile d'y penser sous cette forme).
Autrement dit, $\alpha\boxplus\beta$ désigne le plus petit ordinal qui
soit strictement supérieur à tous les $\alpha'\boxplus\beta$ pour
$\alpha'<\alpha$ ainsi qu'à tous les $\alpha\boxplus\beta'$
pour $\beta'<\beta$.  Cette définition a bien un sens par induction
bien-fondée.

\medskip

(1)(a) Calculer $m\boxplus n$ pour $0\leq m\leq 5$ et $0\leq n\leq
5$.\quad(b) Conjecturer une formule générale pour $m\boxplus n$
lorsque $m,n\in\mathbb{N}$ (c'est-à-dire
$m,n<\omega$).\quad(c) Démontrer cette formule.

\medskip

(2)(a) Montrer que $\boxplus$ est commutative, c'est-à-dire que
$\alpha\boxplus\beta = \beta\boxplus\alpha$ quels que
soient $\alpha,\beta$.\quad(b) Montrer que $\boxplus$ admet $0$ pour
élément neutre, c'est-à-dire que $\alpha\boxplus 0 = 0\boxplus\alpha =
\alpha$ pour tout ordinal $\alpha$.

\medskip

On \underline{admettra} pour la suite que $\boxplus$ est associative,
c'est-à-dire que $(\alpha_1\boxplus\alpha_2) \boxplus \alpha_3 =
\alpha_1 \boxplus (\alpha_2\boxplus\alpha_3)$ quels que soient
$\alpha_1,\alpha_2,\alpha_3$, et que
$\alpha_1\boxplus\cdots\boxplus\alpha_n$ est le plus petit ordinal
strictement supérieur à tous les
$\alpha_1\boxplus\cdots\boxplus\beta_i\boxplus
\cdots\boxplus\alpha_n$, où exactement un des $\alpha_i$ a été
remplacé par un ordinal $\beta_i$ strictement plus petit
(généralisation de la définition au cas de $n$ termes).

\smallskip

Si $\alpha$ est un ordinal et $n\geq 1$ un entier naturel, on
\underline{notera} $\alpha\boxdot n$ pour la somme naturelle $\alpha
\boxplus \cdots \boxplus \alpha$ de $n$ fois l'ordinal $\alpha$ (on
pourra aussi poser $\alpha\boxdot 0 = 0$).  Dans ces conditions, il
est trivial que $(\alpha\boxdot n) \boxplus (\alpha\boxdot n') =
\alpha\boxdot (n+n')$.

\medskip

(3) Montrer par induction transfinie sur $\alpha$ que si $\alpha =
\omega^{\gamma_1} n_1 + \cdots + \omega^{\gamma_r} n_r$ (où $\gamma_1
> \cdots > \gamma_r$ sont des ordinaux en ordre strictement
décroissant et $n_1,\ldots,n_r$ des entiers naturels non nuls ;
c'est-à-dire qu'il s'agit de la forme normale de Cantor de $\alpha$)
alors on a $\alpha = (\omega^{\gamma_1} \boxdot n_1) \boxplus \cdots
\boxplus (\omega^{\gamma_r} \boxdot n_r)$.

\emph{Indication :} On imitera de près la démonstration du fait donné
en cours que si $\alpha = 2^{\gamma_1} + \cdots + 2^{\gamma_r}$ (où
$\gamma_1 > \cdots > \gamma_r$ sont des ordinaux en ordre strictement
décroissant ; c'est-à-dire qu'il s'agit de la l'écriture binaire
de $\alpha$) alors on a $\alpha = 2^{\gamma_1} \oplus \cdots \oplus
2^{\gamma_r}$.  Il n'y a pas grand-chose à modifier à part remplacer
$\mex$ par $\sup^+$ aux endroits utiles.  (Cette question est un peu
longue, mais il est possible de traiter la suite en l'admettant.)

\medskip

(4)(a) En déduire la manière dont on calcule $\alpha\boxplus\beta$ à
partir des formes normales de Cantor de
$\alpha$ et $\beta$.\quad(b) En particulier, calculer
$(\omega+1)\boxplus(\omega+1)$, et comparer avec $(\omega+1) +
(\omega+1)$.

\medskip

(5) On considère le jeu à deux joueurs suivant : les deux joueurs
s'appellent Blaise et Roxane, et ils jouent tour à tour (on ne précise
pas qui commence) ; l'état du jeu est défini par trois ordinaux, qu'on
notera $(\alpha,\beta,\rho)$, et il est visible de tous ; les coups
possibles de Blaise consistent à diminuer strictement soit l'ordinal
$\alpha$ soit l'ordinal $\beta$ (c'est-à-dire passer de
$(\alpha,\beta,\rho)$ à $(\alpha',\beta,\rho)$ avec $\alpha'<\alpha$
ou à $(\alpha,\beta',\rho)$ avec $\beta'<\beta$), tandis que les coups
possibles de Roxane consistent à diminuer strictement l'ordinal $\rho$
(c'est-à-dire passer de $(\alpha,\beta,\rho)$ à $(\alpha,\beta,\rho')$
avec $\rho'<\rho$) ; le joueur qui ne peut plus jouer a perdu.

Montrer que, dans ce jeu, Blaise possède une stratégie gagnante
lorsque $\rho > \alpha\boxplus\beta$, que Roxane possède une stratégie
gagnante lorsque $\rho < \alpha\boxplus\beta$, et que le second joueur
possède une stratégie gagnante lorsque $\rho = \alpha\boxplus\beta$.


%
%
%

\exercice

Soit $n\geq 3$ un entier naturel.  On considère le jeu suivant : Alice
et Bob choisissent chacun en secret un entier naturel $0\leq i\leq
n-1$ et le révèlent simultanément.  Si les deux nombres sont égaux, la
partie est nulle ; sinon, le gagnant est celui qui a choisi le plus
grand, \emph{sauf} dans le cas où un joueur a choisi $n-1$ et l'autre
joueur a choisi $0$, et alors c'est celui qui a choisi $0$ qui gagne.

(On considérera qu'un gain apporte une valeur de $+1$ à celui qui
gagne, une perte une valeur de $-1$ à celui qui perd, et qu'une partie
nulle a une valeur de $0$ pour les deux joueurs.)

(1) De quelle sorte de jeu s'agit-il ?  Écrire explicitement sa
matrice de gains dans le cas $n=5$.  Pour des raisons de symétrie,
quelle est la valeur du jeu ?

(2) Montrer qu'une stratégie mixte optimale consiste à jouer chacune
des options $0$, $n-2$ et $n-1$ avec probabilité $\frac{1}{3}$ (et
jamais les autres).  On l'appellera $s_0$.

(3) Si Alice joue selon la stratégie $s_0$ décrite en (2) et si Bob
joue l'option $i$, quel est le gain espéré de Bob en fonction de $i$ ?

(4) Déduire de (3) qu'aucune stratégie optimale ne peut avoir une
option autre que $0$, $n-2$ ou $n-1$ dans son support.  (On pourra
faire jouer une telle stratégie contre $s_0$.)

(5) Montrer que la stratégie $s_0$ décrite en (2) est la seule
stratégie optimale de ce jeu.


%
%
%
\end{document}