From a4604390708a78be76ff69530e6ca2995f968ad6 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Sat, 7 Apr 2018 21:45:40 +0200 Subject: Two more exercises. --- controle-20180411.tex | 101 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 101 insertions(+) diff --git a/controle-20180411.tex b/controle-20180411.tex index ad422b0..6272a14 100644 --- a/controle-20180411.tex +++ b/controle-20180411.tex @@ -165,6 +165,107 @@ considéré ci-dessus. questions (2) et (3). +% +% +% + +\exercice + +Considérons le graphe suivant : + +\begin{center} +\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp] +\node (a) at (0bp,0bp) [draw,circle] {$a$}; +\node (b) at (-40bp,0bp) [draw,circle] {$b$}; +\node (c) at (-80bp,0bp) [draw,circle] {$c$}; +\node (d) at (-20bp,-30bp) [draw,circle] {$d$}; +\node (e) at (-60bp,-30bp) [draw,circle] {$e$}; +\node (f) at (-100bp,-30bp) [draw,circle] {$f$}; +\node (g) at (-40bp,-60bp) [draw,circle] {$g$}; +\node (h) at (-80bp,-60bp) [draw,circle] {$h$}; +\draw [->] (a) -- (b); \draw [->] (b) -- (c); +\draw [->] (a) -- (d); \draw [->] (b) -- (d); +\draw [->] (b) -- (e); \draw [->] (c) -- (e); +\draw [->] (c) -- (f); \draw [->] (f) -- (e); \draw [->] (d) -- (e); +\draw [->] (d) -- (g); \draw [->] (e) -- (g); +\draw [->] (e) -- (h); \draw [->] (f) -- (h); +\end{tikzpicture} +\end{center} + +Les questions qui suivent étudient toutes différentes variantes d'un +jeu consistant à déplacer un ou plusieurs pions sur ce graphe en +suivant les flèches. + +\medskip + +(1) Dans un premier temps, on considère le jeu suivant : deux joueurs +déplacent un pion (commun) sur ce graphe ; chacun, tour à tour, +déplace le pion d'un sommet du graphe vers un sommet adjacent en +suivant une flèche (i.e., vers un voisin sortant) ; suivant la +convention habituelle, celui qui ne peut pas jouer a perdu. Indiquer, +en fonction de la position initiale du pion ($a$ à $h$), quel joueur a +une stratégie gagnante. + +(2) On modifie maintenant le jeu de la manière suivante : il y a +\emph{plusieurs} pions ; chaque joueur, à son tour, peut et doit +déplacer l'un quelconque des pions, mais un seul, selon les mêmes +règles que précédemment ; plusieurs pions peuvent se trouver sur la +même case, ils n'interagissent pas. Comme précédemment, le joueur qui +ne peut pas jouer (c'est-à-dire, si tous les pions sont bloqués dans +des puits) a perdu. Analyser le jeu en question et expliquer comment +déterminer quel joueur a une stratégie gagnante. Traiter l'exemple de +la situation initiale où un pion est placé en chacun des sommets +$a,b,d,e$ (soit quatre pions au total). + +(3) On modifie maintenant encore un peu le jeu : comme dans la +question (2), il y a plusieurs pions sur le graphe, mais maintenant, +au lieu de déplacer un pion, un joueur peut aussi choisir d'en retirer +un (autrement dit, il y a deux coups possibles : soit déplacer un pion +quelconque suivant une flèche, soit retirer un pion quelconque) ; les +pions n'interagissent pas. Analyser le jeu en question et expliquer +comment déterminer quel joueur a une stratégie gagnante (on pourra +commencer par chercher la valeur de Grundy du jeu où il n'y a qu'un +seul pion et la comparer à la valeur de Grundy du jeu non modifié). +Traiter l'exemple de la situation initiale où un pion est placé en +chacun des sommets $a,b,d,e$ (soit quatre pions au total). + +(4) Les joueurs s'appellent ici Gandalf et Harry (Potter). On revient +au jeu considéré en (1) (on déplace un seul pion, commun, et on ne +peut pas le retirer), mais cette fois, si le pion arrive au sommet $g$ +le joueur Gandalf gagne (indépendamment de qui l'y a amené), tandis +que si le pion arrive en $h$, c'est Harry qui gagne. Indiquer, en +fonction de la position initiale du pion ($a$ à $h$), quel joueur a +une stratégie gagnante. + +(5) On considère enfin le jeu où deux joueurs, disons Xavier et +Yvonne, ont chacun un pion : chacun, quand vient son tour, déplace son +pion indépendamment de l'autre (les deux pions peuvent se trouver sur +la même case, ils n'interagissent pas). Analyser le jeu en question +et expliquer comment déterminer quel joueur a une stratégie gagnante. + + +% +% +% + +\exercice + +On considère le jeu de solitaire (c'est-à-dire, à un seul joueur) +suivant : on joue sur une rangée de cases qui pourront être numérotées +de $0$ à $N$, et qui peuvent chacune contenir un nombre quelconque de +pierres. Initialement, on place une seule pierre sur la case $N$. À +chaque coup, le joueur choisit une pierre sur la case $i$, il la +retire et, si $i>0$ ajoute $k$ pierres sur la case $i-1$, où $k$ est +le numéro du coup (compté à partir de $1$ : autrement dit, le premier +coup remplace une pierre par une pierre, le second remplace une pierre +par deux pierres, le troisième remplace une pierre par trois pierres +et ainsi de suite). + +Le jeu se termine quand toutes les pierres ont été retirées. +Démontrer que cela se produit effectivement en temps fini (on ne +demande pas de majorer le nombre de coups en fonction de $N$). + + % % -- cgit v1.2.3