%% 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{\|}} % \newcommand{\dblunderline}[1]{\underline{\underline{#1}}} % \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 (mais certaines peuvent se ressembler). 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 (possiblement jusqu'à 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{question} Considérons le jeu suivant : Alice choisit une ligne du tableau suivant, \emph{puis} (en ayant connaissance du choix qu'Alice vient de faire) Bob choisit une colonne ; Alice gagne alors un score égal au nombre inscrit dans le tableau (à la ligne et la colonne choisies) et Bob gagne le score opposé. (Chaque joueur cherche à maximiser son score.) \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 affirmations suivantes est correcte ? \rightanswer il s'agit d'un jeu à information parfaite, et Alice a une stratégie 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 $\geq +2$ \answer 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é $\geq 0$ \answer 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é $\geq +1$ \end{question} % % % \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) ; 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) 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 \emph{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} Considérons le jeu en forme normale à 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 en forme normale à 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} \begin{question} Considérons le jeu en forme normale à 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, 0, \frac{1}{2}, \frac{1}{2}, 0)$ \end{question} \end{qvar} % % % \begin{qvar} \begin{question} Considérons le jeu en forme normale à 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 en forme normale à 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 en forme normale à 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 (en forme normale) 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 (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 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 (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 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} \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 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 $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} % % % \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} \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[->] (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 $3$ \answer $0$ \answer $1$ \answer $2$ \answer $4$ \end{question} \end{qvar} % % % \begin{question} Quel joueur a une stratégie gagnante dans 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 (l0) at (-40bp,0bp) [draw,circle] {}; \node (c0) at (0bp,0bp) [draw,circle] {}; \node (r0) at (40bp,0bp) [draw,circle] {}; \node (l1) at (-40bp,-40bp) [draw,circle] {}; \node (c1) at (0bp,-40bp) [draw,circle] {}; \node (r1) at (40bp,-40bp) [draw,circle] {}; \node (l2) at (-40bp,-80bp) [draw,circle] {}; \node (c2) at (0bp,-80bp) [draw,circle] {}; \node (r2) at (40bp,-80bp) [draw,circle] {}; \node (l3) at (-40bp,-120bp) [draw,circle] {}; \node (c3) at (0bp,-120bp) [draw,circle] {}; \node (r3) at (40bp,-120bp) [draw,circle] {}; \node (l4) at (-40bp,-160bp) [draw,circle] {}; \node (c4) at (0bp,-160bp) [draw,circle] {}; \node (r4) at (40bp,-160bp) [draw,circle] {}; \node (c5) at (0bp,-200bp) [draw,circle] {$s$}; \draw[->] (l0) -- (c0); \draw[->] (r0) -- (c0); \draw[->] (l1) -- (l0); \draw[->] (l1) -- (c0); \draw[->] (c1) -- (l0); \draw[->] (c1) -- (r0); \draw[->] (r1) -- (r0); \draw[->] (r1) -- (c0); \draw[->] (l1) -- (c1); \draw[->] (r1) -- (c1); \draw[->] (l2) -- (l1); \draw[->] (l2) -- (c1); \draw[->] (c2) -- (l1); \draw[->] (c2) -- (r1); \draw[->] (r2) -- (r1); \draw[->] (r2) -- (c1); \draw[->] (l2) -- (c2); \draw[->] (r2) -- (c2); \draw[->] (l3) -- (l2); \draw[->] (l3) -- (c2); \draw[->] (c3) -- (l2); \draw[->] (c3) -- (r2); \draw[->] (r3) -- (r2); \draw[->] (r3) -- (c2); \draw[->] (l3) -- (c3); \draw[->] (r3) -- (c3); \draw[->] (l4) -- (l3); \draw[->] (l4) -- (c3); \draw[->] (c4) -- (l3); \draw[->] (c4) -- (r3); \draw[->] (r4) -- (r3); \draw[->] (r4) -- (c3); \draw[->] (l4) -- (c4); \draw[->] (r4) -- (c4); \draw[->] (c5) -- (l4); \draw[->] (c5) -- (r4); \end{tikzpicture} \end{center} \rightanswer le second joueur \answer le premier joueur \answer aucun des deux \end{question} % % % \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 ? (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 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 : 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$) ? \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 : 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} % % % \begin{question} Sachant que $\varepsilon_0 = \omega^{\varepsilon_0}$, auquel ordinaux suivants est égal $\varepsilon_0^{\varepsilon_0}$ ? \rightanswer $\omega^{\omega^{(\varepsilon_0\cdot 2)}}$ (lire : $\omega$ puissance [$\omega$ puissance $\varepsilon_0\cdot 2$]) \answer $\omega^{\omega^{(\varepsilon_0^2)}}$ (lire : $\omega$ puissance [$\omega$ puissance $\varepsilon_0^2$]) \answer $\omega^{(\varepsilon_0\cdot 2)}$ (lire : $\omega$ puissance $\varepsilon_0\cdot 2$) \answer $\omega^{(\varepsilon_0 + 1)}$ (lire : $\omega$ puissance $\varepsilon_0 + 1$) \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 $