diff options
Diffstat (limited to 'controle-20180411.tex')
-rw-r--r-- | controle-20180411.tex | 31 |
1 files changed, 15 insertions, 16 deletions
diff --git a/controle-20180411.tex b/controle-20180411.tex index 5c7c197..08613de 100644 --- a/controle-20180411.tex +++ b/controle-20180411.tex @@ -75,14 +75,6 @@ \date{11 avril 2018} \maketitle -%% {\footnotesize -%% \immediate\write18{sh ./vc > vcline.tex} -%% \begin{center} -%% Git: \input{vcline.tex} -%% \end{center} -%% \immediate\write18{echo ' (stale)' >> vcline.tex} -%% \par} - \pretolerance=8000 \tolerance=50000 @@ -169,7 +161,7 @@ joueur est de maximiser son gain, indépendamment des autres. Le choix $E$ apporte un gain de $1$ point au joueur qui le fait (en plus des gains liés aux choix $A$ des autres comme expliqué dans la phrase suivante). Le choix $A$ apporte un gain de $2$ points, mais ces gains -sont mutualisés entre \emph{tous} les joueux, y compris ceux qui ont +sont mutualisés entre \emph{tous} les joueurs, y compris ceux qui ont choisi $E$. Autrement dit, si $k$ joueurs choisissent l'option $A$, chaque joueur gagne $\frac{2k}{N}$ à cause de ces choix (les $N-k$ joueurs qui ont choisi $E$ gagnent donc $1 + \frac{2k}{N}$ au total). @@ -237,7 +229,7 @@ suivant les flèches. (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 +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. @@ -253,19 +245,23 @@ 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). +\smallskip + (Les questions (3), (4) et (5) sont indépendantes.) +\smallskip + (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 +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é). +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). +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 @@ -278,8 +274,10 @@ 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. +la même case, ils n'interagissent pas). Comme en (1), le joueur qui +ne peut pas bouger (quand vient son tour) a perdu. Analyser le jeu en +question et expliquer comment déterminer quel joueur a une stratégie +gagnante (en fonction des positions initiales des deux pions). % @@ -319,7 +317,8 @@ vous souhaitez \item[(E)] obtenir $1$ point supplémentaire, qui sera ajouté à votre note, ou bien \item[(A)] obtenir $2$ points, qui seront mutualisés entre tous les - participants à l'épreuve. + participants à l'épreuve, c'est-à-dire que $2/N$ points seront + ajoutés à la note de chacun des $N$ participants. \end{itemize} |