Two more exercises.

1 files changed, 101 insertions, 0 deletions

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$).
+
+
 
 %
 %