From 96c74169f8f82f11d39a8de4b16d3ef02f6d7950 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Tue, 18 Apr 2017 00:56:24 +0200 Subject: Add an English translation. --- controle-20170419.tex | 256 ++++++++++++++++++++++++++++++++++++++++++++------ 1 file 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