diff options
| -rw-r--r-- | controle-2020qcm.tex | 227 |
1 files changed, 227 insertions, 0 deletions
diff --git a/controle-2020qcm.tex b/controle-2020qcm.tex index dd4a76d..1a0bde1 100644 --- a/controle-2020qcm.tex +++ b/controle-2020qcm.tex @@ -44,6 +44,8 @@ \newcommand{\rk}{\operatorname{rk}} \newcommand{\fuzzy}{\mathrel{\|}} % +\newcommand{\dblunderline}[1]{\underline{\underline{#1}}} +% \DeclareUnicodeCharacter{00A0}{~} % \DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} @@ -114,6 +116,46 @@ Git: \input{vcline.tex} % % +\begin{question} + +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. + +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 ». + +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) ? + +\rightanswer +la partie (1) est correcte, mais la partie (2) ne l'est pas (Alice ne +peut pas forcément se ramener à une position supposément gagnante) + +\answer +la partie (1) est incorrecte (il ne s'agit pas d'un jeu à information +parfaite impartial défini par un graphe bien-fondé) + +\answer +le raisonnement est correct (les deux parties (1) et (2) le sont) + +\end{question} + + +% +% +% + \begin{qvar} \begin{question} @@ -190,6 +232,43 @@ $(\frac{1}{3}, \frac{1}{3}, \frac{1}{3}, 0, 0)$ \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$&$+2$&$+1$&$0$&$-2$\\ +V&$-2$&$0$&$+1$&$+1$&$+1$\\ +W&$-1$&$-1$&$0$&$-1$&$+2$\\ +X&$0$&$-1$&$+1$&$0$&$-2$\\ +Y&$+2$&$-1$&$-2$&$+2$&$0$\\ +%% m = Matrix(QQ, 5, 5, [[0, 2, 1, 0, -2], [-2, 0, 1, 1, 1], [-1, -1, 0, -1, 2], [0, -1, 1, 0, -2], [2, -1, -2, 2, 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{2}{5}, 0, \frac{2}{5}, 0, \frac{1}{5})$ + +\answer +$(\frac{1}{2}, 0, \frac{1}{2}, 0, 0)$ + +\answer +$(0, 0, \frac{2}{5}, \frac{2}{5}, \frac{1}{5})$ + +\answer +$(0, \frac{1}{2}, \frac{1}{2}, 0, 0)$ + +\end{question} + \end{qvar} @@ -511,6 +590,112 @@ lequel \end{question} +\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 +< \frac{2}{3}$, Alice gagne, tandis que si $x \geq \frac{2}{3}$, Bob +gagne. (À toutes fins utiles, on rappelle que $\frac{2}{3}$ s'écrit +$0{.}10101010\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{question} + +Soit $A \subseteq \{0,1\}^{\mathbb{N}_{>0}}$ l'ensemble des suites +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.) + +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, Alice gagne si la suite +$\dblunderline{a} := (a_1,a_2,a_3,\ldots)$ appartient à $A$, tandis +que Bob gagne dans le cas contraire. (Bref, Alice cherche à ce qu'il +existe $k\geq 1$ tel que les $k$ premiers termes de la suite se +répètent immédiatement, Bob cherche à empêcher ce fait.) + +Que pensez-vous de cette partie $A$ et de ce jeu ? + +\rightanswer +$A$ est ouvert mais n'est pas fermé ; Bob a une stratégie gagnante + +\answer +$A$ est fermé mais n'est pas ouvert ; Bob a une stratégie gagnante + +\answer +$A$ est ouvert mais n'est pas fermé ; Alice a une stratégie gagnante + +\answer +$A$ est fermé mais n'est pas ouvert ; Alice a une stratégie gagnante + +\end{question} + + +% +% +% + +\begin{qvar} + +\begin{question} + +Quel joueur a une stratégie gagnante dans la configuration du jeu de +nim où il y a $5$, $7$, $9$ et $11$ bâtonnets sur les (quatre) lignes +du jeu ? + +\rightanswer +le second joueur (celui qui vient de jouer) + +\answer +le premier joueur (celui qui doit jouer) + +\end{question} + +\begin{question} + +Quel joueur a une stratégie gagnante dans la configuration du jeu de +nim où il y a $7$, $9$, $11$ et $13$ bâtonnets sur les (quatre) lignes +du jeu ? + +\rightanswer +le premier joueur (celui qui doit jouer) + +\answer +le second joueur (celui qui vient de jouer) + +\end{question} + \end{qvar} @@ -901,6 +1086,48 @@ $\omega^{\omega^\omega}$ \end{question} +% +% +% + +\begin{question} + +Patience et Raoul jouent au jeu suivant : l'état du jeu est constitué +d'un certain nombre de tas de pierres, les tas étant numérotés +$0,1,2,3\ldots,r$ ; à chaque tour de jeu, Patience retire une pierre +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). + +On souhaite montrer que Patience gagne forcément, quoi qu'elle fasse +et quoi que fasse Raoul. Quel ordinal proposez-vous d'associer à +l'état du jeu où il y a $n_i$ pierres dans le tas $i$ (i.e., $n_0$ +pierres dans le tas numéroté $0$ et $n_1$ dans le tas numéroté $1$, +etc.), de manière à s'assurer qu'il décroisse forcément ? + +\rightanswer +$\omega^r\, n_r + \omega^{r-1}\, n_{r-1} + \cdots + \omega n_1 + n_0$ + +\answer +$\omega^{n_r}\, r + \omega^{n_{r-1}}\, (r-1) + \cdots + \omega^{n_1}$ + +\answer +$\omega^{n_r} + \omega^{n_{r-1}} + \cdots + \omega^{n_1} + \omega^{n_0}$ + +\answer +$n_0 + \omega\, n_1 + \cdots + \omega^{r-1}\, n_{r-1} + \omega^r\, n_r$ + +\answer +$\omega^{n_1} + \cdots + \omega^{n_{r-1}}\, (r-1) + \omega^{n_r}\, r$ + +\answer +$\omega^{n_0} + \omega^{n_1} + \cdots + \omega^{n_{r-1}} + \omega^{n_r}$ + +\end{question} + + \end{qcm} % % |