1 files changed, 249 insertions, 0 deletions
diff --git a/controle-20190408.tex b/controle-20190408.tex
new file mode 100644
index 0000000..65e25a0
--- /dev/null
+++ b/controle-20190408.tex
@@ -0,0 +1,249 @@
+%% 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.
+
+
+%
+%
+%
+\end{document}