diff options
| -rw-r--r-- | controle-20190408.tex | 249 |
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} |