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