%% 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}