From 71173bdd18d60f5b253121b180186bd50becd453 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Thu, 7 Apr 2022 14:36:00 +0200 Subject: Re-read test. --- controle-20220413.tex | 60 ++++++++++++++++++++++++++------------------------- 1 file changed, 31 insertions(+), 29 deletions(-) diff --git a/controle-20220413.tex b/controle-20220413.tex index 66dfbfd..5c2448d 100644 --- a/controle-20220413.tex +++ b/controle-20220413.tex @@ -145,13 +145,14 @@ $D$&$x$, $v$&$y$, $y$\\\hline \end{tabular} \end{center} -On se limitera à l'étude de $u>v$, ce qu'on supposera désormais. +On se limitera à l'étude du cas où $u>v$, ce qu'on supposera +désormais. (1) Expliquer brièvement pourquoi il ne change rien à l'analyse du jeu -(p.ex., le calcul des équilibres de Nash) de remplacer tous les gains +(p.ex., au calcul des équilibres de Nash) de remplacer tous les gains $t$ d'un joueur donné par $at+b$ où $a>0$ et $b$ est quelconque. En déduire qu'on peut supposer, dans le jeu ci-dessus, que $u=1$ et -$v=0$, ce qu'on fera désormais. +$v=0$, ce qu'on fera désormais : \begin{center} \begin{tabular}{r|c|c|} @@ -161,12 +162,12 @@ $D$&$x$, $0$&$y$, $y$\\\hline \end{tabular} \end{center} -(2) À quelle condition $(C,C)$ (c'est-à-dire : Alice joue $C$ et Bob -joue $C$) est-il un équilibre de Nash ? À quelle condition $(D,D)$ -est-il un équilibre de Nash ? À quelle condition $(C,D)$ est-il un -équilibre de Nash ? Qu'en est-il de $(D,C)$ ? (À chaque fois, on -demande des conditions sous forme d'inégalités portant sur -$x$ et $y$.) +(2) À quelle condition le profil $(C,C)$ (c'est-à-dire : Alice +joue $C$ et Bob joue $C$) est-il un équilibre de Nash ? À quelle +condition $(D,D)$ est-il un équilibre de Nash ? À quelle condition +$(C,D)$ est-il un équilibre de Nash ? Qu'en est-il de $(D,C)$ ? (À +chaque fois, on demande des conditions sous forme d'inégalités portant +sur $x$ et $y$.) On suppose dans la suite (pour écarter des cas limites pénibles) que $x$ n'est pas exactement égal à $1$ et que $y$ n'est pas exactement @@ -221,19 +222,21 @@ On s'intéresse ici à la variation suivante du jeu de nim (fini) : après avoir retiré des bâtonnets d'une ligne, un joueur peut en outre, s'il le souhaite, \emph{couper} la ligne en deux, ce qui crée deux lignes au lieu d'une, en répartissant comme il le veut les bâtonnets -de la ligne initiale (après en avoir retiré au moins un). +de la ligne initiale (après en avoir retiré au moins un) entre ces +deux lignes. De façon plus formelle, l'état du jeu est donné par la liste des nombres $n_1,\ldots,n_r \in \mathbb{N}$ de bâtonnets des différentes lignes du jeu (on peut ignorer ceux pour lesquels $n_i=0$) ; et un coup du jeu consiste à choisir un $1\leq i\leq r$ et à remplacer $n_i$ -dans la liste soit par un entier $n' < n_i$, soit par \emph{deux} -$n',n''$ tels que $n' + n'' < n_i$ (on peut d'ailleurs ne considérer -que ce deuxième type de coup vu que prendre $n''=0$ revient à n'avoir -que $n'$). Comme d'habitude, le joueur qui ne peut pas jouer a perdu -(i.e., le gagnant est celui qui retire le dernier bâtonnet) ; et la -disposition des lignes ou des bâtonnets au sein d'une ligne n'a pas -d'importance, seul compte leur nombre (et tout est fini). +dans la liste soit par un entier neturels $n' < n_i$, soit par +\emph{deux} entiers naturels $n',n''$ tels que $n' + n'' < n_i$ (on +peut d'ailleurs ne considérer que ce deuxième type de coup puisque +prendre $n''=0$ revient à n'avoir que $n'$). Comme d'habitude, le +joueur qui ne peut pas jouer a perdu (i.e., le gagnant est celui qui +retire le dernier bâtonnet) ; et la disposition des lignes ou des +bâtonnets au sein d'une ligne n'a pas d'importance, seul compte leur +nombre (et tout est fini). (1) Expliquer pourquoi la valeur de Grundy de la position $(n_1,\ldots,n_r)$ du jeu est la somme de nim $f(n_1) \oplus \cdots @@ -272,13 +275,13 @@ types d'arêtes). Deux joueurs, Blaise et Roxane, alternent et chacun à son tour choisit une arête de l'arbre, bleue pour Blaise ou rouge pour Roxane, et l'efface, ce qui fait automatiquement disparaître du même coup tout le sous-arbre qui descendait de cette arête (voir -figure). L'arête choisie doit avoir la couleur associée au joueur -(bleue pour Blaise, rouge pour Roxane), mais toutes les arêtes qui en -descendent sont effacées quelle que soit leur couleur. Le jeu se -termine lorsque plus aucun coup n'est possible (c'est-à-dire que le -joueur qui doit jouer n'a plus d'arête de sa couleur), auquel cas, -selon la convention habituelle, le joueur qui ne peut plus jouer a -perdu. +figure). L'arête choisie doit avoir la couleur associée au joueur, +c'est-à-dire bleue pour Blaise ou rouge pour Roxane, mais toutes les +arêtes qui en descendent sont effacées quelle que soit leur couleur. +Le jeu se termine lorsque plus aucun coup n'est possible (c'est-à-dire +que le joueur qui doit jouer n'a plus d'arête de sa couleur), auquel +cas, selon la convention habituelle, le joueur qui ne peut plus jouer +a perdu. À titre d'exemple, ceci illustre un coup possible de Roxane (effacement d'une arête rouge et de tout le sous-arbre qui en @@ -377,10 +380,9 @@ v+1&\hbox{~si $v\geq 0$}\\ \end{array} \right. \] -\item[(d)] On a $v(T) > 0$ si et seulement si Blaise possède une - stratégie gagnante à partir de la position $T$ (qui que soit le - joueur qui commence), et $v(T) < 0$ lorsque c'est Roxane, et $v(T) = - 0$ lorsque c'est le second joueur. +\item[(d)] On a $v(T) \geq 0$ si et seulement si Blaise possède une + stratégie gagnante en jouant en second à partir de la position $T$, + et $v(T) \leq 0$ lorsque Roxane en possède une. \end{itemize} (2) Utiliser ces règles admises pour calculer la valeur de l'arbre @@ -389,7 +391,7 @@ tracé à gauche dans la figure ci-dessus (avant effacement). Pour d'indiquer à côté de chaque sommet la valeur du sous-arbre qui en descend, et à côté de chaque arête la valeur du sous-arbre avec l'arête en question. En déduire qui a une stratégie gagnante dans -cette position. +cette position selon le joueur qui commence. \smallbreak -- cgit v1.2.3