diff options
| author | David A. Madore <david+git@madore.org> | 2017-04-17 23:47:42 +0200 | 
|---|---|---|
| committer | David A. Madore <david+git@madore.org> | 2017-04-17 23:47:42 +0200 | 
| commit | b88ed24c6e3494581e9116fd9bd8ae88f186e1a2 (patch) | |
| tree | 79f7ba14aa04ddd388cf34df977e3103925afd39 | |
| parent | 020e328071cb71895fa8177ff23054c0d645d408 (diff) | |
| download | mitro206-b88ed24c6e3494581e9116fd9bd8ae88f186e1a2.tar.gz mitro206-b88ed24c6e3494581e9116fd9bd8ae88f186e1a2.tar.bz2 mitro206-b88ed24c6e3494581e9116fd9bd8ae88f186e1a2.zip | |
More proofreading.
| -rw-r--r-- | controle-20170419.tex | 23 | 
1 files changed, 12 insertions, 11 deletions
| diff --git a/controle-20170419.tex b/controle-20170419.tex index 76b4af0..8529436 100644 --- a/controle-20170419.tex +++ b/controle-20170419.tex @@ -127,13 +127,13 @@ 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  arbre (fini, enraciné\footnote{C'est-à-dire que la racine fait partie    de la donnée de l'arbre, ce qui est la convention la plus -  courante.}).  Deux joueurs alternent, et chacun, quand vient son -tour, choisit une arête de l'arbre 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).  Le jeu se termine lorsque -plus aucun coup n'est possible (c'est-à-dire que l'arbre est réduit à -sa seule racine), auquel cas, selon la convention habituelle, le -joueur qui ne peut plus jouer a perdu. +  courante.}).  Deux joueurs alternent et chacun à son tour choisit +une arête de l'arbre 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).  Le jeu se termine lorsque plus aucun coup n'est +possible (c'est-à-dire que l'arbre est réduit à sa seule racine), +auquel cas, selon la convention habituelle, le joueur qui ne peut plus +jouer a perdu.  \begin{center}  \begin{tikzpicture}[baseline=0] @@ -195,12 +195,13 @@ 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) -$T'_1,\ldots,T'_r$. - -Qu'en déduit-on sur la valeur de Grundy de la position $T$ ? +$T'_1,\ldots,T'_r$.  Qu'en déduit-on sur la valeur de Grundy de la +position $T$ ?  \smallbreak +\centerline{* * *} +  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$ @@ -313,7 +314,7 @@ uns des autres un élément de l'ensemble $\{\mathtt{0},\mathtt{1}\}$ :  Il sera utile de remarquer que les joueurs ont des rôles complètement  symétriques, et que les options sont également symétriques. -(Attention, même si la somme des gans des trois joueurs vaut +(Attention, même si la somme des gains des trois joueurs vaut  toujours $0$, ce n'est pas un « jeu à somme nulle » au sens classique,  car ces derniers ne sont définis que pour \emph{deux} joueurs.) | 
