diff options
| -rw-r--r-- | controle-2020qcm.tex | 96 |
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 à |