diff options
| -rw-r--r-- | controle-20170419.tex | 256 |
1 files changed, 228 insertions, 28 deletions
diff --git a/controle-20170419.tex b/controle-20170419.tex index 8529436..b4a9f19 100644 --- a/controle-20170419.tex +++ b/controle-20170419.tex @@ -1,6 +1,6 @@ %% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt,a4paper]{article} -\usepackage[francais]{babel} +\usepackage[english,francais]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} %\usepackage{ucs} @@ -96,6 +96,8 @@ Les exercices sont totalement indépendants. Ils pourront être traités dans un ordre quelconque, mais on demande de faire apparaître de façon très visible dans les copies où commence chaque exercice. +Une traduction anglaise suit l'énoncé en français. + \medbreak L'usage de tous les documents (notes de cours manuscrites ou @@ -107,6 +109,29 @@ L'usage des appareils électroniques est interdit. Durée : 1h30 +\vskip3ex + +\begin{otherlanguage}{english} +{\footnotesize + +\noindent\textbf{Instructions.} + +The following exercises are independent. They can be answered in any +order, but the beginning and end of each exercise should be clearly +marked. + +An English translation follows the questions in French. + +The use of all documents (handwritten or printed course notes, +exercise sheets, books) is permitted. + +The use of electronic devices is forbidden. + +Duration: 1h30 + +\par} +\end{otherlanguage} + \vfill {\noindent\tiny \immediate\write18{sh ./vc > vcline.tex} @@ -121,7 +146,7 @@ Git: \input{vcline.tex} % % -\exercice +\exercice\label{hackenbush-exercise} On s'intéresse dans cet exercice au jeu de \emph{Hackenbush impartial en arbre}, défini comme suit. L'état du jeu est représenté par un @@ -189,12 +214,12 @@ devient (1) Expliquer pourquoi une position de ce jeu peut être considérée comme une somme de nim de différents jeux du même type. Plus -exactement, soit $T$ un arbre de racine $x$, soient $y_1,\ldots,y_r$ +exactement, soit $T$ un arbre de racine $x$, soient $y_1,\ldots,y_r$ les fils de $x$, soient $T_1,\ldots,T_r$ les sous-arbres ayant pour racines $y_1,\ldots,y_r$ et soient $T'_1,\ldots,T'_r$ les arbres de racine $x$ où $T'_i$ est formé de $x$ et de $T_i$ (avec une arête -entre $x$ et $y_i$) : expliquer pourquoi la position (représentée par -l'arbre) $T$ est la somme de nim de (celles représentées par) +entre $x$ et $y_i$) : expliquer pourquoi la position représentée par +l'arbre $T$ est la somme de nim de celles représentées par $T'_1,\ldots,T'_r$. Qu'en déduit-on sur la valeur de Grundy de la position $T$ ? @@ -205,17 +230,17 @@ position $T$ ? Indépendamment de ce qui précède, on va considérer une nouvelle opération sur les jeux : si $G$ est un jeu combinatoire impartial, vu comme un graphe orienté (bien-fondé), on définit un jeu noté $*{:}G$ -défini en ajoutant une unique position $0$ à $G$ comme on va l'expliquer. -Pour chaque position $z$ de $G$ il y a une position notée $*{:}z$ de -$*{:}G$, et il y a une unique autre position, notée $0$, -dans $*{:}G$ ; pour chaque arête $z \to z'$ de $G$, il y a une arête -$*{:}z\, \to \, *{:}z'$ dans $*{:}G$, et il y a de plus une arête -$*{:}z\, \to 0$ dans $*{:}G$ pour chaque $z$ (en revanche, $0$ est un -puits, c'est-à-dire qu'aucune arête n'en part) ; la position initiale -de $*{:}G$ est $*{:}z_0$ où $z_0$ est celle de $G$. De façon plus -informelle, pour jouer au jeu $*{:}G$, chaque joueur peut soit faire -un coup normal ($*{:}z\, \to \, *{:}z'$) dans $G$, soit appliquer un -coup « destruction totale » $*{:}z\, \to 0$ qui fait terminer +défini en ajoutant une unique position $0$ à $G$ comme on va +l'expliquer. Pour chaque position $z$ de $G$ il y a une position +notée $*{:}z$ de $*{:}G$, et il y a une unique autre position, +notée $0$, dans $*{:}G$ ; pour chaque arête $z \to z'$ de $G$, il y a +une arête $*{:}z\, \to \, *{:}z'$ dans $*{:}G$, et il y a de plus une +arête $*{:}z\, \to 0$ dans $*{:}G$ pour chaque $z$ (en revanche, $0$ +est un puits, c'est-à-dire qu'aucune arête n'en part) ; la position +initiale de $*{:}G$ est $*{:}z_0$ où $z_0$ est celle de $G$. De façon +plus informelle, pour jouer au jeu $*{:}G$, chaque joueur peut soit +faire un coup normal ($*{:}z\, \to \, *{:}z'$) de $G$, soit appliquer +un coup « destruction totale » $*{:}z\, \to 0$ qui fait terminer immédiatement le jeu (et celui qui l'applique a gagné\footnote{Ce jeu considéré tout seul n'est donc pas très amusant puisqu'on a toujours la possibilité de gagner instantanément.}). @@ -230,14 +255,12 @@ alors $*{:}G$ a pour valeur de Grundy $1+\alpha$. (3) On revient au jeu de Hackenbush impartial en arbre. Soit $T$ un arbre de racine $y$ et $T'$ l'arbre obtenu en ajoutant une nouvelle -racine $x$ à $T$, c'est-à-dire que les sommets de $T'$ sont ceux de -$T$ plus $x$, qui en est la racine, avec une arête entre $x$ et $y$. +racine $x$ à $T$, c'est-à-dire que les sommets de $T'$ sont ceux de +$T$ plus $x$, qui en est la racine, avec une arête entre $x$ et $y$. Expliquer pourquoi le jeu de Hackenbush représenté par $T'$ s'obtient par la construction « $*{:}$ » considérée en (2) à partir de celui -représenté par $T$. - -Qu'en déduit-on sur la valeur de Grundy de la position $T'$ par -rapport à celle de $T$ ? +représenté par $T$. Qu'en déduit-on sur la valeur de Grundy de la +position $T'$ par rapport à celle de $T$ ? \smallbreak @@ -298,7 +321,7 @@ désigne l'égalité au sens de Conway des jeux partisans). % % -\exercice +\exercice\label{normal-game-exercise} On considère le jeu en forme normale suivant : \emph{trois} joueurs (Alice, Bob et Charlie, par exemple) choisissent indépendamment les @@ -345,7 +368,7 @@ c'est le cas si et seulement si $q + r = 1$. \smallbreak -(4) Déduire de la question (3) que si un profil $(p,q,r)$ de +(4) Déduire de la question (3) que si un profil $(p,q,r)$ de stratégies mixtes est un équilibre de Nash et que $0<p<1$ alors $q+r=1$. @@ -358,10 +381,187 @@ $q$ et $r$ ; la symétrie doit permettre de simplifier le travail). \smallbreak (6) Dans cette question, on modifie le jeu : plutôt que faire leurs -choix indépendamment, les joueurs le font successivement (Alice, puis -Bob, puis Charlie). (a) Que va faire Bob si Alice -choisit $\mathtt{0}$ ? (b) Informellement, expliquer qui est avantagé -ou désavantagé par cette modification de la règle. +choix indépendamment, les joueurs les font et les déclarent +successivement (Alice, puis Bob, puis Charlie). (a) Que va faire Bob +si Alice choisit $\mathtt{0}$ ? (b) Informellement, expliquer qui est +avantagé ou désavantagé par cette modification de la règle. + + +% +% +% + +\begin{otherlanguage}{english} + +\bigbreak + +\centerline{\hbox to2truein{\hrulefill}} +\centerline{\textbf{English translation}} + +\footnotesize + +(This translation is provided to help understand the French version, +but the latter remains the official text and should be referred to in +case of ambiguity or doubt, as this translation has not been checked +as carefully.) + +\medbreak + +\textbf{Exercise \ref{hackenbush-exercise}.} + +This exercise concerns the game of \emph{impartial tree Hackenbush}, +defined as follows. The state of the game is represented by a +(finite, rooted\footnote{Meaning that the root is part of the tree + datum, which the usual convention.}) tree. Two players alternate, +each in turn chooses an edge of the tree and removes it, which +automatically causes the entire subtree from this edge to disappear +(see figure in French version). The game ends when no move is +possible (meaning that the tree is reduced to its root), at which +point, following the usual convention, the player who can no longer +play loses. + +\smallbreak + +(1) Explain why a position in this game can be considered as a nim sum +of different games of the same type. More precisely, let $T$ be a +tree with root $x$, let $y_1,\ldots,y_r$ be the children of $x$, let +$T_1,\ldots,T_r$ be the subtrees having $y_1,\ldots,y_r$ as roots, and +let $T'_1,\ldots,T'_r$ be the trees rooted at $x$ where $T'_i$ +consists of $x$ and $T_i$ (along with an edge between $x$ and $y_i$): +explain why the position represented by the tree $T$ is the nim sum of +those represented by $T'_1,\ldots,T'_r$. What can we deduce about the +Grundy value (=nim value) of the position $T$? + +\smallbreak + +\centerline{* * *} + +Independently of the above, we consider a new operation on games: if +$G$ is an impartial combinatorial game, considered as a (well-founded) +oriented graph, we define a new game noted $*{:}G$ defined by adding a +unique new position $0$ to $G$ as follows. For each position $z$ +of $G$, there is a position $*{:}z$ of $*{:}G$, and there is a unique +extra position, written $0$, in $*{:}G$; for each edge $z \to z'$ +of $G$, there is an edge $*{:}z\, \to \, *{:}z'$ in $*{:}G$, and +additionally there are edges $*{:}z\, \to 0$ in $*{:}G$ for each $z$ +(on the other hand, $0$ is a sink, meaning that it has no outgoing +edge); the initial position of $*{:}G$ is $*{:}z_0$ where $z_0$ is +that of $G$. Informally, to play the game $*{:}G$, each player can +either make a normal move ($*{:}z\, \to \, *{:}z'$) from $G$, or apply +the ``total destruction'' move $*{:}z\, \to 0$ which terminates tha +game immediately (and the one who plays it wins\footnote{Considered + alone, this game is therefore not very fun because there is always + this possibility of winning immediately.}). + +\smallbreak + +(2) Show by well-founded induction that if $G$ is a (well-founded) +impartial combinatorial game with Grundy value $\alpha$, then $*{:}G$ +has Grundy value $1+\alpha$. + +\smallbreak + +(3) We now return to impartial tree Hackenbush. Let $T$ be a tree +with root $y$ and $T'$ the tree obtained by adding a new root $x$ +to $T$, meaning that the vertices of $T'$ are those of $T$ plus $x$, +which is the root, with an edge between $x$ and $y$. Explain why the +Hackenbush game represented by $T'$ is obtained, by means of the +``$*{:}$'' construction considered in (2), from that represented +by $T$. What can we deduce about the Grundy value of the +position $T'$ with respect to that of $T$? + +\smallbreak + +(4) Use the previous questions to propose a method to compute the +Grundy value of an arbitrary position of impartial tree Hackenbush. + +\smallbreak + +(5) What is the Grundy value of the position represented in the French +version of the question? (It is identical to the one used to show an +example of a possible move.) What move would you prescribe in this +situation? + +\smallbreak + +(6) Note that the $*{:}G$ construction defined just before +question (2) can be defined in an identical way when $G$ is a partizan +game, by giving an edge $*{:}z\, \to \, *{:}z'$ the same color as +$z\to z'$, and an edge $*{:}z\, \to 0$ the color green (which means: +both blue and red). By describing a strategy, show that if $G \geq H$ +then we also have $*{:}G \geq *{:}H$, and deduce that if $G\doteq H$ +then $*{:}G \doteq *{:}H$ (where $\doteq$ denotes equality in the +sense of Conway of partizan games). + +\bigbreak + +\textbf{Exercise \ref{normal-game-exercise}.} + +We consider the following normal form game: \emph{three} players +(Alice, Bob and Charlie, say) each choose, independently of one +another, an element of the set $\{\mathtt{0},\mathtt{1}\}$: +\begin{itemize} +\item if they all choose the same option, they all receive a payoff + of $0$; +\item whereas if one chooses an option different from the two others, + whoever chooses this option gets a payoff of $2$ and the two others + receive $-1$ each. +\end{itemize} + +It is worth noting that the players have a completely symmetric rôle, +and that the options are likewise symmetric. + +(Warning: even though the sum of the payoffs of the three players is +always $0$, this is not a ``zero-sum game'' in the classical sense, +because the latter are defined only for \emph{two} players.) + +\smallbreak + +(1) Write the payoff matrix for the game under consideration. (Choose +a reasonable way to present a table with three entries, for example as +several two-entry tables put side by side.) + +\smallbreak + +If $p \in [0;1]$, we simply write $p$ for the mixed strategy for some +player consisting of choosing option $\mathtt{1}$ with +probability $p$, and option $\mathtt{0}$ with probability $1-p$. + +(2) Check that the expected payoff for Alice if she plays following +the mixed strategy $p$ while Bob plays following the mixed +strategy $q$ and Charlie following the mixed strategy $r$ is: $-2pq +-2pr +4qr + 2p - q -r$. (Here, $p,q,r$ are three real numbers between +$0$ and $1$.) + +\smallbreak + +(3) We now ask ourselves under what condition on the mixed strategy +$q$ used by Bob and the mixed strategy $r$ used by Charlie the two +options $\mathtt{0}$ and $\mathtt{1}$ for Alice are indifferent to her +(meaning that they provide her with the same expected payoff). Show +that this is the case if and only if $q + r = 1$. + +\smallbreak + +(4) Deduce from question (3) that if mixed strategy profile $(p,q,r)$ +is a Nash equilibrium and if $0<p<1$ then $q+r=1$. + +\smallbreak + +(5) Use the previous questions to find all Nash equilibria $(p,q,r)$ +in the game (one might discuss various cases according as $p=0$, $p=1$ +or $0<p<1$, and similarly for $q$ and $r$; one might use symmetry to +simplify the task). + +\smallbreak + +(6) In this question, the game is altered: instead of making their +choices independently, the players make them and declare them +successively (Alice, then Bob, then Charlie). (a) What will Bob do if +Alice chooses $\mathtt{0}$? (b) Explain informally who is favored or +disfavored by this alteration of the rule. + +\end{otherlanguage} |