summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--controle-2020qcm.tex96
1 files changed, 52 insertions, 44 deletions
diff --git a/controle-2020qcm.tex b/controle-2020qcm.tex
index eba8d6e..f33cec5 100644
--- a/controle-2020qcm.tex
+++ b/controle-2020qcm.tex
@@ -142,21 +142,21 @@ Laquelle des affirmations suivantes est correcte ?
\rightanswer
il s'agit d'un jeu à information parfaite, et Alice a une stratégie
-lui garantissant un score de $-1$
+lui garantissant un score $\geq -1$
\answer
il s'agit d'un jeu à information parfaite, et Alice a une stratégie
-lui garantissant un score de $+2$
+lui garantissant un score $\geq +2$
\answer
-il s'agit d'un jeu en forme normale, sans information parfaite, et les
+il s'agit d'un jeu en forme normale, à information imparfaite, et les
deux joueurs ont une stratégie leur donnant à chacun un score espéré
-nul
+$\geq 0$
\answer
-il s'agit d'un jeu en forme normale, sans information parfaite, et les
+il s'agit d'un jeu en forme normale, à information imparfaite, et les
deux joueurs ont une stratégie leur donnant à chacun un score espéré
-de $+1$
+$\geq +1$
\end{question}
@@ -170,22 +170,25 @@ de $+1$
Alice et Bob jouent au jeu suivant : chacun tour à tour place un pion
sur un échiquier $8\times 8$ de manière à n'être ni sur la même ligne,
ni sur la même colonne, ni sur une même diagonale (dans un sens ou
-dans l'autre) qu'un pion déjà placé (par un joueur ou l'autre). Le
-premier qui ne peut pas jouer a perdu.
+dans l'autre) qu'un pion déjà placé (par un joueur ou l'autre) ;
+autrement dit, les pions ne doivent pas pouvoir se prendre selon un
+mouvement de dame aux échecs. Comme d'habitude, le premier joueur qui
+ne peut pas jouer a perdu.
Chloé tient le raisonnement suivant (imitant le raisonnement
justifiant que dans le jeu de chomp le premier joueur a une stratégie
-gagnante) : « (1) il s'agit d'un jeu à information parfaite impartial
-défini par un graphe bien-fondé, donc l'un des deux joueurs a une
-stratégie gagnante ; (2) il s'agit forcément d'Alice : en effet,
-supposons par l'absurde que ce soit Bob, alors Bob aurait un coup
-gagnant à jouer en réponse à n'importe quel coup initial d'Alice, mais
-Alice pourrait jouer ce coup dès le premier tour, se mettant ainsi
-dans la position supposément gagnante ».
+gagnante) : « (1) on a affaire à un jeu à information parfaite,
+impartial, défini par un graphe bien-fondé, donc l'un des deux joueurs
+a une stratégie gagnante ; (2) ce joueur est forcément Alice : en
+effet, supposons par l'absurde que ce soit Bob, alors Bob aurait un
+coup gagnant à jouer en réponse à n'importe quel coup initial d'Alice,
+mais Alice pourrait jouer ce coup dès le premier tour, se mettant
+ainsi dans la position supposément gagnante ».
Que pensez-vous de ce raisonnement (on ne demande pas de se prononcer
sur l'exactitude de la conclusion, i.e., si Alice a une stratégie
-gagnante ou pas, mais sur le raisonnement qu'on vient d'écrire) ?
+gagnante ou pas, mais sur le \emph{raisonnement} qu'on vient
+d'écrire) ?
\rightanswer
la partie (1) est correcte, mais la partie (2) ne l'est pas (Alice ne
@@ -317,7 +320,7 @@ $(\frac{1}{2}, 0, \frac{1}{2}, 0, 0)$
$(0, 0, \frac{2}{5}, \frac{2}{5}, \frac{1}{5})$
\answer
-$(0, \frac{1}{2}, \frac{1}{2}, 0, 0)$
+$(0, 0, \frac{1}{2}, \frac{1}{2}, 0)$
\end{question}
@@ -488,7 +491,9 @@ ni (x) ni (y) n'est un équilibre de Nash
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.
+$1$ et $12$) égal au nombre (total) de joueurs ayant choisi cette
+option. (Autrement dit, chaque joueur choisit sa couleur et essaie
+d'être dans un groupe aussi grand que possible.)
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
@@ -523,8 +528,9 @@ ni (x) ni (y) ni (z) n'est un équilibre de Nash
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.
+$-1$ et $-12$) égal à \emph{l'opposé} du nombre (total) de joueurs
+ayant choisi cette option. (Autrement dit, chaque joueur choisit sa
+couleur et essaie d'être dans un groupe aussi petit que possible.)
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
@@ -684,9 +690,9 @@ binaires $\dblunderline{a} := (a_1,a_2,a_3,\ldots)$ (indicées par
$\mathbb{N}_{>0} = \{1,2,3,4,\ldots\}$) ayant la propriété suivante :
il existe $k\geq 1$ tel que $a_{k+i} = a_i$ pour tout $1\leq i\leq k$,
autrement dit, les $k$ premiers termes de la suite $(a_1,\ldots,a_k)$
-sont répétés en $(a_{k+1},\ldots,a_{2k})$. (À titre d'exemple, toute
-suite commençant par $(0,1,0,1,\ldots)$ appartient à $A$ puisque les
-$k=2$ premiers termes sont répétés.)
+sont immédiatement répétés en $(a_{k+1},\ldots,a_{2k})$. (À titre
+d'exemple, toute suite commençant par $(0,1,0,1,\ldots)$ appartient
+à $A$ puisque les $k=2$ premiers termes sont immédiatement répétés.)
Alice et Bob jouent au jeu de type Gale-Stewart suivant : chacun à son
tour choisit un chiffre binaire (soit $0$ soit $1$ : Alice choisit
@@ -985,7 +991,9 @@ lequel est positionné un unique pion (commun aux deux joueurs) :
plus jouer a perdu).
\end{itemize}
-Que pensez-vous de ce jeu ?
+Que pensez-vous de ce jeu ? (On pourra par exemple calculer de proche
+en proche la valeur de Grundy, ou le type $\mathtt{P}$ ou
+$\mathtt{N}$, de chacune des $64$ positions possibles.)
\rightanswer
Alice a une stratégie gagnante, et (pour la suivre) doit commencer par
@@ -1056,15 +1064,15 @@ lignes) soit multiple de $3$
\begin{question}
-On considère le jeu suivant (inspiré du jeu de nim) : on a une
-(unique) ligne 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.
+On considère le jeu suivant : on a une (unique) ligne 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$) ?
@@ -1096,16 +1104,16 @@ $0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1\ldots$
\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.
+On considère le jeu suivant : 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$
@@ -1288,7 +1296,7 @@ d'un des tas, disons du tas numéroté $k$, puis Raoul rajoute autant de
pierre qu'il le souhaite sur les tas de numéro $<k$ (si Patience a
retié une pierre du tas $0$, Raoul ne joue pas). Patience gagne si
elle finit par retirer toutes les pierres, tandis que Raoul gagne si
-cela ne se produit pas (i.e., si le jeu dure infiniment longtemps).
+cela ne se produit jamais (i.e., si le jeu dure infiniment longtemps).
On souhaite montrer que Patience gagne forcément, quoi qu'elle fasse
et quoi que fasse Raoul. Quel ordinal proposez-vous d'associer à