summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2019-04-04 15:28:01 +0200
committerDavid A. Madore <david+git@madore.org>2019-04-04 15:28:01 +0200
commitf0f4ee08e7c4d98c13bc4dddda2d90b353e5d3cc (patch)
treefbd5c11f5a4fd1a19c4de3b1cb0679bae79f8207
parentf9d723c0439107cba9ae30fd85075ae3d1abefd2 (diff)
downloadmitro206-f0f4ee08e7c4d98c13bc4dddda2d90b353e5d3cc.tar.gz
mitro206-f0f4ee08e7c4d98c13bc4dddda2d90b353e5d3cc.tar.bz2
mitro206-f0f4ee08e7c4d98c13bc4dddda2d90b353e5d3cc.zip
Start writing test.
-rw-r--r--controle-20190408.tex249
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}