path: root/controle-2020qcm.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]
%
\newenvironment{qcm}{\relax}{\relax}
\newenvironment{qvar}{\relax}{\relax}
\newcounter{quescnt}
\newenvironment{question}%
{\stepcounter{quescnt}\bigskip\noindent\textbf{Question~\arabic{quescnt}.}\par\nobreak}
{\relax}
\newcounter{answcnt}[quescnt]
\newcommand\answer{%
\stepcounter{answcnt}\smallskip\textbf{(\Alph{answcnt})}~}
\let\rightanswer=\answer
%
\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}
%
\newif\ifcorrige
\corrigefalse
\def\seedval{test}
%
%
%
\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{26 juin 2020}
\maketitle

\pretolerance=8000
\tolerance=50000

\vskip1truein\relax

\noindent\textbf{Consignes.}

Ce contrôle de connaissances est un QCM (questionnaire à choix
multiples).  Chaque question admet une unique réponse correcte.  Les
questions sont totalement indépendantes les unes des autres.  La
sélection des questions et l'ordre ont été tirés aléatoirement et
n'obéissent donc à aucune logique particulière.

La réponse est attendue sous forme d'une liste de numéros de question
suivie de la réponse proposée : par exemple, « \verb=1A 2B 4D= » pour
signifier que la réponse proposée à la question 1 est (A), la réponse
proposée à la question 2 est (B), et la réponse proposée à la
question 4 est (D).

Une réponse incorrecte sera (deux fois) plus fortement pénalisée
qu'une absence de réponse : il est donc préférable de ne pas répondre
à une question que de répondre aléatoirement.

\medbreak

Durée : 1h de 17h30 à 18h30

\vfill

\noindent
Sujet généré pour : \texttt{\seedval}

\medskip

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

\pagebreak

\begin{qcm}


%
%
%

\begin{qvar}

\begin{question}

Considérons le jeu à somme nulle, symétrique, entre Alice et Bob, dont
la matrice des gains est donnée par le tableau suivant (Alice choisit
la ligne, Bob choisit la colonne, le tableau donne le gain d'Alice et
le gain de Bob est l'opposé de la valeur indiquée) :

\begin{center}
\begin{tabular}{r|rrrrr}
$\downarrow$Alice, Bob$\rightarrow$&U&V&W&X&Y\\\hline
U&$0$&$0$&$+1$&$+1$&$-1$\\
V&$0$&$0$&$-1$&$-1$&$+1$\\
W&$-1$&$+1$&$0$&$0$&$+2$\\
X&$-1$&$+1$&$0$&$0$&$-1$\\
Y&$+1$&$-1$&$-2$&$+1$&$0$\\
%% m = Matrix(QQ, 5, 5, [[0, 0, 1, 1, -1], [0, 0, -1, -1, 1], [-1, 1, 0, 0, 2], [-1, 1, 0, 0, -1], [1, -1, -2, 1, 0]])
\end{tabular}
\end{center}

Laquelle des réponses suivantes est une stratégie optimale à ce jeu ?
(Chaque réponse proposée est la liste des probabilités de jouer les
options U,V,W,X,Y dans cet ordre.)

\rightanswer
$(\frac{1}{2}, 0, \frac{1}{4}, 0, \frac{1}{4})$

\answer
$(1, 0, 0, 0, 0)$

\answer
$(0, \frac{1}{3}, 0, \frac{1}{3}, \frac{1}{3})$

\answer
$(0, 0, 0, 0, 1)$

\end{question}

\begin{question}

Considérons le jeu à somme nulle, symétrique, entre Alice et Bob, dont
la matrice des gains est donnée par le tableau suivant (Alice choisit
la ligne, Bob choisit la colonne, le tableau donne le gain d'Alice et
le gain de Bob est l'opposé de la valeur indiquée) :

\begin{center}
\begin{tabular}{r|rrrrr}
$\downarrow$Alice, Bob$\rightarrow$&U&V&W&X&Y\\\hline
U&$0$&$+1$&$-1$&$0$&$-1$\\
V&$-1$&$0$&$+2$&$-1$&$-1$\\
W&$+1$&$-2$&$0$&$+1$&$+2$\\
X&$0$&$+1$&$-1$&$0$&$0$\\
Y&$+1$&$+1$&$-2$&$0$&$0$\\
%% m = Matrix(QQ, 5, 5, [[0, 1, -1, 0, -1], [-1, 0, 2, -1, -1], [1, -2, 0, 1, 2], [0, 1, -1, 0, 0], [1, 1, -2, 0, 0]])
\end{tabular}
\end{center}

Laquelle des réponses suivantes est une stratégie optimale à ce jeu ?
(Chaque réponse proposée est la liste des probabilités de jouer les
options U,V,W,X,Y dans cet ordre.)

\rightanswer
$(\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4}, 0)$

\answer
$(\frac{1}{5}, \frac{1}{5}, \frac{1}{5}, \frac{1}{5}, \frac{1}{5})$

\answer
$(0, 0, 0, 0, 1)$

\answer
$(\frac{1}{3}, \frac{1}{3}, \frac{1}{3}, 0, 0)$

\end{question}

\end{qvar}


%
%
%

\begin{qvar}

\begin{question}

Considérons le jeu à somme nulle, entre Alice et Bob, dont la matrice
des gains est donnée par le tableau suivant (Alice choisit la ligne,
Bob choisit la colonne, le tableau donne le gain d'Alice et le gain de
Bob est l'opposé de la valeur indiquée) :

\begin{center}
\begin{tabular}{r|rrr}
$\downarrow$Alice, Bob$\rightarrow$&X&Y&Z\\\hline
U&$-3$&$0$&$+3$\\
V&$0$&$-1$&$-3$\\
W&$-2$&$+2$&$-1$\\
%% m = Matrix(QQ, 3, 3, [[-3, 0, 3], [0, -1, -3], [-2, 2, -1]])
\end{tabular}
\end{center}

Quelle est la stratégie optimale de chacun des deux joueurs à ce jeu ?
(Chaque réponse proposée est la liste des probabilités pour Alice de
jouer les options U,V,W dans cet ordre puis pour Bob de jouer X,Y,Z.)

\rightanswer
$(\frac{1}{3}, \frac{2}{3}, 0)$ pour Alice, et $(\frac{2}{3}, 0,
\frac{1}{3})$ pour Bob

\answer
$(\frac{1}{4}, \frac{3}{4}, 0)$ pour Alice, et $(\frac{1}{4},
\frac{3}{4}, 0)$ pour Bob

\answer
$(0,1,0)$ pour Alice, et $(1,0,0)$ pour Bob

\end{question}

\begin{question}

Considérons le jeu à somme nulle, entre Alice et Bob, dont la matrice
des gains est donnée par le tableau suivant (Alice choisit la ligne,
Bob choisit la colonne, le tableau donne le gain d'Alice et le gain de
Bob est l'opposé de la valeur indiquée) :

\begin{center}
\begin{tabular}{r|rrr}
$\downarrow$Alice, Bob$\rightarrow$&X&Y&Z\\\hline
U&$-3$&$-2$&$+2$\\
V&$+1$&$+2$&$0$\\
W&$0$&$-2$&$-3$\\
%% m = Matrix(QQ, 3, 3, [[-3, -2, 2], [1, 2, 0], [0, -2, -3]])
\end{tabular}
\end{center}

Quelle est la stratégie optimale de chacun des deux joueurs à ce jeu ?
(Chaque réponse proposée est la liste des probabilités pour Alice de
jouer les options U,V,W dans cet ordre puis pour Bob de jouer X,Y,Z.)

\rightanswer
$(\frac{1}{6}, \frac{5}{6}, 0)$ pour Alice, et $(\frac{1}{3}, 0,
\frac{2}{3})$ pour Bob

\answer
$(\frac{3}{8}, 0, \frac{5}{8})$ pour Alice, et $(\frac{5}{8}, 0,
\frac{3}{8})$ pour Bob

\answer
$(0,1,0)$ pour Alice, et $(0,0,1)$ pour Bob

\end{question}

\begin{question}

Considérons le jeu à somme nulle, entre Alice et Bob, dont la matrice
des gains est donnée par le tableau suivant (Alice choisit la ligne,
Bob choisit la colonne, le tableau donne le gain d'Alice et le gain de
Bob est l'opposé de la valeur indiquée) :

\begin{center}
\begin{tabular}{r|rrr}
$\downarrow$Alice, Bob$\rightarrow$&X&Y&Z\\\hline
U&$-3$&$-2$&$+2$\\
V&$+3$&$+1$&$0$\\
W&$+1$&$+1$&$-1$\\
%% m = Matrix(QQ, 3, 3, [[-3, -2, 2], [3, 1, 0], [1, 1, -1]])
\end{tabular}
\end{center}

Quelle est la stratégie optimale de chacun des deux joueurs à ce jeu ?
(Chaque réponse proposée est la liste des probabilités pour Alice de
jouer les options U,V,W dans cet ordre puis pour Bob de jouer X,Y,Z.)

\rightanswer
$(\frac{1}{5}, \frac{4}{5}, 0)$ pour Alice, et $(0, \frac{2}{5},
\frac{3}{5})$ pour Bob

\answer
$(\frac{1}{3}, 0, \frac{2}{3})$ pour Alice, et $(0, \frac{1}{2},
\frac{1}{2})$ pour Bob

\answer
$(0,1,0)$ pour Alice, et $(0,0,1)$ pour Bob

\end{question}

\end{qvar}


%
%
%

\begin{question}

Considérons le jeu analogue à pierre-papier-ciseaux, sauf que les deux
joueurs \emph{détestent} choisir tous les deux la même option, si bien
que la matrice des gains est la suivante (ce n'est plus un jeu à somme
nulle !) :

\begin{center}
\begin{tabular}{r|ccc}
$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux\\\hline
Pierre&$-100,-100$&$-1,+1$&$+1,-1$\\
Papier&$+1,-1$&$-100,-100$&$-1,+1$\\
Ciseaux&$-1,+1$&$+1,-1$&$-100,-100$\\
\end{tabular}
\end{center}

On considère deux profils de stratégies mixtes : (x) Alice et Bob
jouent tous les deux une option entre pierre, papier ou ciseaux
choisie aléatoirement avec probabilité $\frac{1}{3}$ (comme la
stratégie optimale dans le cas du jeu à somme nulle) ; et : (y) Alice
et Bob jouent tous les deux : papier avec probabilité $\frac{101}{200}
= 0.505$, pierre avec probabilité $\frac{99}{200} = 0.495$ et jamais
ciseaux.  Que pensez-vous de ces deux profils ?

\rightanswer
(x) est un équilibre de Nash, mais (y) n'en est pas un

\answer
(x) n'est pas un équilibre de Nash, mais (y) en est un

\answer
(x) et (y) sont tous les deux des équilibres de Nash

\answer
ni (x) ni (y) n'est un équilibre de Nash

\end{question}


%
%
%

\begin{qvar}

\begin{question}

Douze joueurs jouent au jeu suivant : chacun choisit une option parmi
« rouge », « vert » ou « bleu ».  Chacun reçoit alors un score (entre
$1$ et $12$) égal au nombre de joueurs ayant choisi cette option.

On considère trois profils de stratégies mixtes : (x) tous les joueurs
jouent « rouge » ; (y) chaque joueur joue une option tirée au hasard
uniformément (c'est-à-dire avec probabilité $\frac{1}{3}$ pour
chacune) ; et (z) chaque joueur joue une option tirée au hasard mais
uniquement entre « rouge » et « vert », chacune avec
probabilité $\frac{1}{2}$.  Que pensez-vous de ces profils ?

\rightanswer
(x), (y) et (z) sont tous les trois des équilibres de Nash

\answer
(x) est un équilibre de Nash, mais (y) et (z) n'en sont pas

\answer
(y) est un équilibre de Nash, mais (x) et (z) n'en sont pas

\answer
(y) et (z) sont tous les deux des équilibres de Nash, mais (x) n'en
est pas

\answer
(x) et (y) sont tous les deux des équilibres de Nash, mais (z) n'en
est pas

\answer
ni (x) ni (y) ni (z) n'est un équilibre de Nash

\end{question}

\begin{question}

Douze joueurs jouent au jeu suivant : chacun choisit une option parmi
« rouge », « vert » ou « bleu ».  Chacun reçoit alors un score (entre
$-1$ et $-12$) égal à \emph{l'opposé} du nombre de joueurs ayant
choisi cette option.

On considère trois profils de stratégies mixtes : (x) tous les joueurs
jouent « rouge » ; (y) chaque joueur joue une option tirée au hasard
uniformément (c'est-à-dire avec probabilité $\frac{1}{3}$ pour
chacune) ; et (z) chaque joueur joue une option tirée au hasard mais
uniquement entre « rouge » et « vert », chacune avec
probabilité $\frac{1}{2}$.  Que pensez-vous de ces profils ?

\rightanswer
(y) est un équilibre de Nash, mais (x) et (z) n'en sont pas

\answer
(x), (y) et (z) sont tous les trois des équilibres de Nash

\answer
(x) est un équilibre de Nash, mais (y) et (z) n'en sont pas

\answer
(y) et (z) sont tous les deux des équilibres de Nash, mais (x) n'en
est pas

\answer
(x) et (y) sont tous les deux des équilibres de Nash, mais (z) n'en
est pas

\answer
ni (x) ni (y) ni (z) n'est un équilibre de Nash

\end{question}

\end{qvar}


%
%
%

\begin{question}

Ambre et Bastien ($8$ ans) jouent à
pierre-papier-ciseaux-éléphant-souris, dont les règles sont les
suivantes : chacun choisit une des cinq options (pierre, papier,
ciseau, éléphant ou souris) indépendamment de l'autre, et
\begin{itemize}
\item si les deux joueurs ont choisi la même option, le jeu est nul,
  sinon :
\item si les deux joueurs ont choisi parmi pierre, papier ou ciseaux,
  le gagnant est déterminé comme à pierre-papier-ciseaux (i.e., le
  papier gagne sur la pierre, les ciseaux gagnent sur le papier et la
  pierre gagne sur les ciseaux),
\item l'éléphant gagne sur tout sauf la souris,
\item la souris gagne sur l'éléphant et perd contre tout le reste.
\end{itemize}
(On accordera la valeur $+1$ au fait de gagner, $-1$ au fait de
perdre, et $0$ à un match nul.)

Quelle est la stratégie optimale à ce jeu ?

\rightanswer
jouer chacun de pierre, papier et ciseaux avec probabilité
$\frac{1}{9}$, éléphant avec probabilité $\frac{1}{3}$ et souris avec
probabilité $\frac{1}{3}$

\answer
jouer chacun de pierre, papier et ciseaux avec probabilité
$\frac{1}{3}$, et jamais éléphant ni souris

\answer
jouer chacun de pierre, papier, ciseaux avec probabilité
$\frac{1}{6}$, éléphant avec probabilité $\frac{1}{2}$ et jamais
souris

\answer
jouer chacun de pierre, papier et ciseaux avec probabilité
$\frac{1}{4}$, éléphant avec probabilité $\frac{1}{8}$ et souris avec
probabilité $\frac{1}{8}$

\answer
jouer chacune des cinq options avec probabilité $\frac{1}{5}$

\end{question}


%
%
%

\begin{qvar}

\begin{question}

Alice et Bob jouent au jeu de type Gale-Stewart suivant : chacun à son
tour choisit un chiffre binaire (soit $0$ soit $1$ : Alice choisit
$a_1$ puis Bob choisit $a_2$ puis Alice choisit $a_3$ et ainsi de
suite).  Au bout d'un nombre infini de tours, on considère le nombre
réel $x$ entre $0$ et $1$ dont l'écriture binaire fractionnaire est
formée de ces chiffres (c'est-à-dire $x = \sum_{i=1}^{+\infty}
a_i\,2^{-i}$, ou $0{.}a_1a_2a_3\ldots$ en écriture binaire) : si $x
\leq \frac{1}{3}$, Alice gagne, tandis que si $x > \frac{1}{3}$, Bob
gagne.  (À toutes fins utiles, on rappelle que $\frac{1}{3}$ s'écrit
$0{.}01010101\ldots$ en binaire.)  Que pensez-vous de ce jeu ?

\rightanswer
Alice a une stratégie gagnante

\answer
Bob a une stratégie gagnante

\answer
aucun joueur n'a de stratégie gagnante

\answer
un joueur a une stratégie gagnante, mais il est impossible de savoir
lequel

\end{question}

\end{qvar}


%
%
%

\begin{qvar}

\begin{question}

C'est à votre tour de jouer au jeu de nim dans une configuration où il
y a $1$, $4$, $10$ et $12$ bâtonnets sur les (quatre) lignes du jeu.
Que faites-vous (pour suivre la stratégie gagnante) ?

\rightanswer
retirer $1$ bâtonnet de la ligne qui en a $10$ (qui passe donc à $9$)

\answer
retirer $3$ bâtonnets de la ligne qui en a $10$ (qui passe donc à $7$)

\answer
retirer le seul bâtonnet de la ligne qui en a $1$ (qui disparaît donc)

\answer
retirer $3$ bâtonnets de la ligne qui en a $12$ (qui passe donc à $9$)

\end{question}

\begin{question}

C'est à votre tour de jouer au jeu de nim dans une configuration où il
y a $1$, $6$, $8$ et $12$ bâtonnets sur les (quatre) lignes du jeu.
Que faites-vous (pour suivre la stratégie gagnante) ?

\rightanswer
retirer $1$ bâtonnet de la ligne qui en a $6$ (qui passe donc à $5$)

\answer
retirer $3$ bâtonnets de la ligne qui en a $6$ (qui passe donc à $3$)

\answer
retirer le seul bâtonnet de la ligne qui en a $1$ (qui disparaît donc)

\answer
retirer $3$ bâtonnets de la ligne qui en a $8$ (qui passe donc à $5$)

\end{question}

\end{qvar}


%
%
%

\begin{qvar}

\begin{question}

On considère le jeu combinatoire (impartial, à information parfaite)
associé au graphe orienté acyclique représenté ci-dessous, la position
de départ étant notée $s$ :

\begin{center}
\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
\node (n00) at (0bp,0bp) [draw,circle] {};
\node (n01) at (40bp,0bp) [draw,circle] {};
\node (n02) at (80bp,0bp) [draw,circle] {};
\node (n10) at (0bp,-40bp) [draw,circle] {};
\node (n11) at (40bp,-40bp) [draw,circle] {};
\node (n12) at (80bp,-40bp) [draw,circle] {};
\node (n20) at (0bp,-80bp) [draw,circle] {};
\node (n21) at (40bp,-80bp) [draw,circle] {};
\node (n22) at (80bp,-80bp) [draw,circle] {$s$};
\draw[->] (n01) -- (n00);  \draw[->] (n02) -- (n01);
\draw[->] (n11) -- (n10);  \draw[->] (n12) -- (n11);
\draw[->] (n21) -- (n20);  \draw[->] (n22) -- (n21);
\draw[->] (n11) -- (n00);  \draw[->] (n12) -- (n01);
\draw[->] (n21) -- (n10);  \draw[->] (n22) -- (n11);
\draw[->] (n10) -- (n00);  \draw[->] (n20) -- (n10);
\draw[->] (n11) -- (n01);  \draw[->] (n21) -- (n11);
\draw[->] (n12) -- (n02);  \draw[->] (n22) -- (n12);
\end{tikzpicture}
\end{center}

Quelle est la valeur de Grundy du jeu (i.e., celle de la
position $s$) ?

\rightanswer
$0$

\answer
$1$

\answer
$2$

\answer
$3$

\answer
$4$

\end{question}

\end{qvar}


%
%
%

\begin{question}

Alice et Bob jouent au jeu suivant sur un échiquier $8\times 8$ sur
lequel est positionné un unique pion (commun aux deux joueurs) :
\begin{itemize}
\item le pion démarre sur la case au coin sud-est de l'échiquier, et
  Alice joue en premier,
\item chaque joueur, tour à tour, déplace le pion d'une seule case,
  soit vers le nord, soit vers l'ouest, soit (en diagonale) vers le
  nord-ouest, mais sans dépasser les limites de l'échiquier,
\item celui qui atteint la case au coin nord-ouest de l'échiquier a
  \emph{gagné} (il revient au même de dire que le joueur qui ne peut
  plus jouer a perdu).
\end{itemize}

Que pensez-vous de ce jeu ?

\rightanswer
Alice a une stratégie gagnante, et (pour la suivre) doit commencer par
déplacer le pion en diagonale (d'une case vers le nord-ouest)

\answer
Alice a une stratégie gagnante, et (pour la suivre) doit commencer par
déplacer le pion d'une case vers le nord ou, indifféremment, vers
l'ouest

\answer
Alice a une stratégie gagnante, et (pour la suivre) peut commencer par
un coup quelconque

\answer
Bob a une stratégie gagnante

\end{question}


%
%
%

\begin{question}

On considère une variante du jeu de nim, mais avec la différence qu'on
peut retirer \emph{un ou deux} bâtonnets d'une seule ligne (et dans la
limite du nombre effectivement présent sur cette ligne !).  Par
exemple, à partir de la position $(1,2,3)$ (c'est-à-dire la position
dans laquelle il y $1$ bâtonnet sur une ligne, $2$ sur une autre, et
$3$ sur la troisième), on pourrait aller en $(0,2,3)$ ou $(1,1,3)$ ou
$(1,0,3)$ ou $(1,2,2)$ ou $(1,2,1)$ mais pas en $(1,2,0)$.  Comme
d'habitude, le jeu se termine quand un joueur ne peut plus jouer
(c'est-à-dire quand il n'y a plus de bâtonnets), et le joueur qui
devait jouer a alors perdu.

Laquelle des descriptions suivantes définit la stratégie gagnante de
ce jeu ?  (On pourra commencer par la valeur de Grundy de la position
où il y a une unique ligne avec $n$ bâtonnets, et se rappeler que la
valeur de Grundy de la somme de nim de deux jeux est la somme de nim
des valeurs de Grundy.)

\rightanswer
jouer de manière à ce qu'il y ait un nombre pair de lignes ayant un
nombre de bâtonnets congru à $1$ modulo $3$ et aussi un nombre pair de
lignes ayant un nombre de bâtonnets congru à $2$ modulo $3$

\answer
jouer de manière à ce qu'il y ait un nombre impair de lignes ayant un
nombre de bâtonnets congru à $1$ modulo $3$ et aussi un nombre pair de
lignes ayant un nombre de bâtonnets congru à $2$ modulo $3$

\answer
jouer de manière à ce qu'il y ait un nombre pair de lignes ayant un
nombre de bâtonnets non multiple de $3$

\answer
jouer de manière à ce que le nombre total de bâtonnets (sur toutes les
lignes) soit multiple de $3$

\end{question}


%
%
%

\begin{question}

On considère le jeu suivant (inspiré du jeu de nim) : on a une unique
rangée de bâtonnets, et chaque joueur, quand vient son tour, peut
retirer un nombre de bâtonnets égal à une puissance de $2$
(c'est-à-dire que s'il y a $n$ bâtonnets avant de jouer, il en laisse
$n-2^k$ pour un certain $k$ entier avec $2^k \leq n$ ; par exemple,
s'il y a $17$ bâtonnets, on peut en laisser $16$, $15$, $13$, $7$ ou
$1$).  Comme d'habitude, le jeu se termine quand un joueur ne peut
plus jouer (c'est-à-dire quand il n'y a plus de bâtonnets), et le
joueur qui devait jouer a alors perdu.

Laquelle des suites suivantes donne la valeur de Grundy de la position
où il y a $n$ bâtonnets (pour $n=0,1,2,3,\ldots$) ?

\rightanswer
$0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2\ldots$

\answer
$0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\ldots$

\answer
$0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1\ldots$

\answer
$0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3\ldots$

\answer
$0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1\ldots$

\answer
$0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1\ldots$

\end{question}


%
%
%

\begin{question}

On considère le jeu suivant (inspiré du jeu de nim) : l'état du jeu
est formé d'un certain nombre de tas de pierres, chaque tas comportant
$\geq 1$ pierre.  Chaque joueur, quand vient son tour, choisit un tas
ayant $\geq 2$ pierres et le scinde en deux tas ayant chacun $\geq 1$
pierres (autrement dit, il remplace un tas de $n \geq 2$ pierres par
deux tas ayant $n_1$ et $n_2$ pierres, avec $n = n_1 + n_2$ et
$n_1\geq 1$ et $n_2 \geq 1$).  En particulier, le nombre total de
pierres ne change jamais.  Comme d'habitude, le jeu se termine quand
un joueur ne peut plus jouer (c'est-à-dire quand il n'y a plus que des
tas de $1$ pierre), et le joueur qui devait jouer a alors perdu.

Quelle formule de récurrence permet de calculer la fonction de Grundy
$f(n) := \gr(H_n)$ de l'état $H_n$ du jeu ayant un unique tas de $n$
pierres ?

\rightanswer
$f(1) = 0$ et $f(n) = \mex\{f(k)\oplus f(n-k) : 1\leq k\leq n-1\}$

\answer
$f(1) = 0$ et $f(n) = \mex\{f(k) : 1\leq k\leq n-1\}$

\answer
$f(1) = 0$ et $f(n) = \mex\{f(k) + f(n-k) : 1\leq k\leq n-1\}$

\answer
$f(1) = 0$ et $f(n) = \mex\{f(k_1) \oplus \cdots \oplus f(k_r) : k_1,\ldots,k_r \geq 1 \ \text{et}\ k_1+\cdots+k_r = n\}$

\end{question}


%
%
%

\begin{qvar}

\begin{question}

Lequel des ordinaux suivants est le plus grand ?

\rightanswer
$(\omega^{(\omega^{(\omega\cdot 4)})\cdot 2})\cdot 3$

\answer
$(\omega^{(\omega^{(\omega\cdot 3)})\cdot 4})\cdot 2$

\answer
$(\omega^{(\omega^{(\omega\cdot 2)})\cdot 3})\cdot 4$

\end{question}

\begin{question}

Lequel des ordinaux suivants est le plus grand ?

\rightanswer
$(\omega^{(\omega^{(\omega\cdot 2)})\cdot 2})+ 2$

\answer
$(\omega^{(\omega^{(\omega\cdot 2)})+ 2})\cdot 2$

\answer
$(\omega^{(\omega^{(\omega+ 2)})\cdot 2})\cdot 2$

\end{question}

\end{qvar}


%
%
%

\begin{question}

Auquel ordinaux suivants est égal $\omega + \omega^2 +
\omega^\omega$ ?

\rightanswer
$\omega^\omega$

\answer
$\omega^\omega + \omega^2 + \omega$

\answer
$\omega$

\answer
$\omega^{\omega+1}$

\answer
$\omega^\omega\cdot 2$

\end{question}


%
%
%

\begin{question}

Auquel ordinaux suivants est égal $\omega \cdot \omega^2 \cdot
\omega^\omega$ (produit de $\omega$, de $\omega^2$ et de
$\omega^\omega$ dans cet ordre) ?

\rightanswer
$\omega^\omega$

\answer
$\omega^{\omega+3}$

\answer
$\omega$

\answer
$\omega^{\omega+1}$

\answer
$\omega^{\omega\cdot 2}$

\end{question}


%
%
%

\begin{question}

Auquel ordinaux suivants est égal $2^{\omega\cdot 2}$ (lire :
$2$ puissance $\omega\cdot 2$) ?

\rightanswer
$\omega^2$

\answer
$\omega$

\answer
$\omega^\omega$

\answer
$\omega^{\omega^2}$

\answer
$\omega^{\omega^\omega}$

\end{question}


\end{qcm}
%
%
%
\end{document}