diff options
| -rw-r--r-- | controle-20250626.tex | 188 |
1 files changed, 182 insertions, 6 deletions
diff --git a/controle-20250626.tex b/controle-20250626.tex index aa134a4..00897c6 100644 --- a/controle-20250626.tex +++ b/controle-20250626.tex @@ -297,10 +297,9 @@ l'état du jeu. Les piles sont numérotées $0$, $1$, $2$, etc. Chaque pile contient un certain nombre fini (entier naturel) de jetons. Il n'y a qu'un nombre fini de piles non vides (c'est-à-dire, ayant un nombre non-nul de jetons). Pour représenter la position -mathématiquement, on utilisera la liste $(n_0, n_1, n_2, \ldots, -n_{k-1})$ où $n_i$ est le nombre de jetons de la pile numérotée $i$, -et où ceci signifie implicitement que toutes les piles $\geq k$ sont -vides. +mathématiquement, on utilisera la liste $(n_0, n_1, n_2, \ldots, n_k)$ +où $n_i$ est le nombre de jetons de la pile numérotée $i$, et où ceci +signifie implicitement que toutes les piles $\geq k$ sont vides. Un coup d'un joueur consiste à retirer \emph{exactement un} jeton d'une certaine pile $i$, de son choix, et d'ajouter \emph{autant qu'il @@ -315,6 +314,22 @@ c'est-à-dire que celui qui prend le dernier jeton a gagné. forcément en temps fini, quelle que soit la position initiale. (On justifiera soigneusement.) +\begin{corrige} +On associe à la position $(n_0,\ldots,n_k)$ l'ordinal $\omega^k\cdot +n_k + \cdots + \omega\cdot n_1 + n_0$ (remarquons qu'il s'agit d'une +écriture en forme normale de Cantor). Un coup du jeu consiste à +remplacer un certain $n_i$ par $n_i-1$ et tous les $n_j$ avec $j<i$ +par des $n'_j$ où $n'_j \geq n_j$. Le tuple +$(n'_0,\ldots,n'_{i-1},n_i-1,n_{i+1},\ldots,n_k)$ qui résulte du coup +est lexicographiquement inférieur à $(n_0,\ldots,n_k)$ pour l'ordre +lexicographique donnant le poids le plus fort aux $n_j$ avec $j$ +grand, ce qui signifie justement que l'ordinal qu'on vient de lui +associer a diminué strictement. Comme toute suite strictement +décroissante d'ordinaux est finie, le jeu termine en temps fini, +\end{corrige} + +\smallskip + Appelons « position totalement paire » une position dans laquelle le nombre $n_i$ de jetons de chaque pile est pair. @@ -322,32 +337,193 @@ nombre $n_i$ de jetons de chaque pile est pair. paire conduit nécessairement à une position qui n'est pas totalement paire. +\begin{corrige} +On a retiré un jeton d'une certaine pile $i$, donc si le nombre de +jetons était pair avant le coup, il est devenu impair, et la position +n'est plus totalement paire. +\end{corrige} + \textbf{(3)} Montrer que depuis toute position qui n'est pas totalement paire il existe au moins un coup conduisant à une position totalement paire. +\begin{corrige} +Si $(n_0,\ldots,n_k)$ est une position qui n'est pas totalement paire, +il existe un $n_i$ impair : soit $i$ le plus grand possible tel que +$n_i$ soit impair (tous les $n_j$ avec $j>i$ sont donc pairs). Le +coup consistant à retirer un jeton de la pile $i$ (qui passe donc à +$n_i-1$ jetons, lequel nombre est pair) et à en ajouter un à toutes +les piles $j<i$ telles que $n_j$ soit impair (qui passent donc à +$n_j+1$ jetons, lequel nombre est pair) est légal selon les règles du +jeu, et conduit à une position totalement paire. +\end{corrige} + \textbf{(4)} En déduire quelles sont les positions du jeu dans lesquelles le premier joueur a une stratégie gagnante, et quelles sont celles dans lesquelles le second joueur en a une. (On justifiera très soigneusement.) +\begin{corrige} +Considérons la stratégie $\sigma$ consistant à jouer vers une position +totalement paire si on est dans une position qui ne l'est pas (c'est +possible par la question (3)) et à retirer un jeton quelconque sinon +(et bien sûr, à capituler s'il n'y a plus de jeton). Le joueur qui +applique cette stratégie $\sigma$ depuis une position qui n'est pas +totalement paire va gagner : chacun de ces coups mènera à une position +totalement paire et son adversaire va forcément en sortir au coup +suivant, donc (par une récurrence immédiate) le joueur dont on parle +sera toujours face à une position qui n'est pas totalement paire, et +gagnera car le jeu ne peut pas durer indéfiniment longtemps +(question (1)). Ceci montre que les positions qui ne sont pas +totalement paires sont gagnantes pour le premier joueur (ce sont des +positions $N$) et que celles qui sont totalement paires sont gagnantes +pour le second joueur (ce sont des positions $P$). + +Si on préfère, on peut aussi rédiger ainsi : on a vu au (1) que le +graphe des positions du jeu est bien-fondé. On peut donc montrer par +induction bien-fondée sur la position $x$ que $x$ est une position $P$ +si et seulement si elle est totalement paire. Si $x$ est totalement +paire, aucun de ses voisins sortants n'est totalement pair +d'après (2), donc ils sont tous $N$ par l'hypothèse d'induction, donc +$x$ est $P$ ; et réciproquement, si $x$ est $P$, tous ses voisins sont +$N$, donc par hypothèse d'induction aucun n'est totalement pair, donc +$x$ n'est pas totalement pair par (la contraposée de) la question (3). +Ceci conclut l'induction. +\end{corrige} + \textbf{(5)} Calculer, en fonction de $n$, la valeur de Grundy de la position $(n)$ (c'est-à-dire s'il n'y a que la pile numérotée $0$, et qu'elle comporte $n$ jetons). +\begin{corrige} +On a $\gr((0)) = 0$ car c'est un puits, et $\gr((1)) = \mex\{0\} = 1$ +puis $\gr((2)) = \mex\{1\} = 0$, et ainsi de suite. + +Pour simplifier la notation dans les réponses ultérieures, notons +$(n\%2)$ l'entier valant $0$ si $n$ est pair et $1$ si $n$ est impair. + +Une récurrence sur $n$ permet de prouver que $\gr((n)) = (n\%2)$ : en +effet, si $n$ est pair, $\gr((n)) = \mex(\{\gr((n-1))\}) = \mex\{1\} = +0$, et si $n$ est impair, $\gr((n)) = \mex(\{\gr((n-1))\}) = \mex\{0\} += 1$. +\end{corrige} + \textbf{(6)} En déduire la valeur de Grundy des posititions $(0,1)$ et $(1,1)$, puis plus généralement de $(n,1)$ en fonction de $n$. +\begin{corrige} +On a $\gr((0,1)) = \mex\{\gr((n)) : n\in\mathbb{N}\} = \mex\{0,1\} = +2$. On en déduit que $\gr((1,1)) = \mex(\{\gr((n+1)) : +n\in\mathbb{N}\} \cup \{\gr((0,1))\}) = \mex\{0,1,2\} = 3$. On +vérifie alors par récurrence sur $n$ que $\gr((n,1)) = 2$ si $n$ est +pair et $\gr((n,1)) = 3$ si $n$ est impair (i.e., $2+(n\%2)$, si on +veut) : en effet, si $n$ est pair, $\gr((n,1)) = \mex(\{\gr((m)) : +m\geq n\} \cup \{\gr((n-1,1))\}) = \mex(\{0,1,3\}) = 2$, et si $n$ est +impair, $\gr((n,1)) = \mex(\{\gr((m)) : m\geq n\} \cup +\{\gr((n-1,1))\}) = \mex(\{0,1,2\}) = 3$. +\end{corrige} + \textbf{(7)} En déduire la valeur de Grundy des positions $(0,2)$ et $(1,2)$, plus plus généralement de $(n_0,n_1)$ en fonction de $n_0,n_1$. +\begin{corrige} +On a $\gr((0,2)) = \mex\{\gr((n,1)) : n\in\mathbb{N}\} = \mex\{2,3\} = +0$ (ce qu'on peut aussi conclure du fait que $(0,2)$ est totalement +paire). On en déduit que $\gr((1,2)) = \mex(\{\gr((n+1,1)) : +n\in\mathbb{N}\} \cup \{\gr((0,2))\}) = \mex\{2,3,0\} = 1$. + +On peut alors mener une récurrence sur $n_1$ et, pour chaque $n_1$, +sur $n_0$ (ou, si on préfère, une induction transfinie sur l'ordinal +$\omega\cdot n_1 + n_0$) pour montrer : $\gr((n_0,n_1)) = 2(n_1\%2) + +(n_0\%2)$. En effet, +\begin{itemize} +\item si $n_0$ et $n_1$ sont pairs, on a $\gr((n_0,n_1)) = + \mex(\{\gr((m,n_1-1)) : m\geq n_0\} \cup \{\gr((n_0-1,n_1))\}) = + \mex\{2,3,1\} = 0$ (ce qu'on peut aussi conclure du fait que + $(n_0,n_1)$ est totalement paire), +\item si $n_0$ est impair et $n_1$ pair, on a $\gr((n_0,n_1)) = + \mex(\{\gr((m,n_1-1)) : m\geq n_0\} \cup \{\gr((n_0-1,n_1))\}) = + \mex\{2,3,0\} = 1$, +\item si $n_0$ est pair et $n_1$ impair, on a $\gr((n_0,n_1)) = + \mex(\{\gr((m,n_1-1)) : m\geq n_0\} \cup \{\gr((n_0-1,n_1))\}) = + \mex\{0,1,3\} = 2$, +\item si $n_0$ et $n_1$ sont impairs, on a $\gr((n_0,n_1)) = + \mex(\{\gr((m,n_1-1)) : m\geq n_0\} \cup \{\gr((n_0-1,n_1))\}) = + \mex\{0,1,2\} = 3$. +\end{itemize} +Ceci couvre tous les cas et conclut la récurrence. +\end{corrige} + \textbf{(8)} En déduire la valeur de Grundy de la position $(0,0,1)$. +\begin{corrige} +On a $\gr((0,0,1)) = \mex\{\gr((n_0,n_1)) : n_0,n_1\in\mathbb{N}\} = +\mex\{0,1,2,3\} = 4$. +\end{corrige} + \textbf{(9)} Conjecturer une formule générale pour la valeur de Grundy -d'une position $(n_0,n_1,\ldots,n_{k-1})$ quelconque. +d'une position $(n_0,n_1,\ldots,n_k)$ quelconque. -\textbf{(10)} Démontrer cette formule. +\begin{corrige} +Les résultats précédents suggèrent que $\gr((n_0,n_1,\ldots,n_k))$ ne +dépend que de la parité de $n_0,\ldots,n_k$, c'est-à-dire de ce qu'on +a noté $(n_i\%2)$. Les valeurs calculées jusqu'à présent inspirent à +penser que +\[ +\gr((n_0,n_1,\ldots,n_k)) = 2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2) +\] +(C'est-à-dire qu'on lit les $(n_i\%2)$ comme un nombre en binaire et +qu'il donne la valeur de Grundy.) +\end{corrige} + +\textbf{(10)} Démontrer cette formule. (Cette question est plus +difficile, et il peut être opportun de la garder pour la fin.) + +\begin{corrige} +On va montrer par induction transfinie sur l'ordinal $\omega^k\cdot +n_k + \cdots + \omega\cdot n_1 + n_0$ associé à la position +$(n_0,n_1,\ldots,n_k)$ (ou, ce qui revient essentiellement au même, +par induction bien-fondée sur la position elle-même) que la formule +ci-dessus est valable. Comme $\gr((n_0,n_1,\ldots,n_k))$ est +le $\mex$ de l'ensemble $S$ des $\gr((n'_0,n'_1,\ldots,n'_k))$ où +$(n'_0,n'_1,\ldots,n'_k)$ parcourt tous les voisins sortants de +$(n_0,n_1,\ldots,n_k)$, pour montrer que $\gr((n_0,n_1,\ldots,n_k)) = +2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2)$, il s'agit de +vérifier (A) que $2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2)$ +n'est pas dans $S$ et (B) que tout nombre $r < 2^k\,(n_k\%2) + \cdots ++ 2\,(n_1\%2) + (n_0\%2)$ est dans $S$. Or par hypothèse d'induction, +les éléments de $S$ sont les $2^k\,(n'_k\%2) + \cdots + 2\,(n'_1\%2) + +(n'_0\%2)$ avec $(n'_0,n'_1,\ldots,n'_k)$ voisin sortant de +$(n_0,n_1,\ldots,n_k)$. + +Montrons (A) : on sait qu'un des $n'_i$ vaut $n_i-1$. Ceci assure que +$(n'_i\%2) \neq (n_i\%2)$, donc par unicité des écritures binaires, +que $2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2)$ est différent de +$2^k\,(n'_k\%2) + \cdots + 2\,(n'_1\%2) + (n'_0\%2)$ (au moins un bit +diffère). Ceci conclut le (A). + +Montrons (B) : si $r < 2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + +(n_0\%2)$, appelons $r = 2^k\,b_k + \cdots + 2\,b_1 + b_0$ son +écriture binaire, où $b_j \in \{0,1\}$. Soit $i$ le plus grand +possible tel que $b_i \neq (n_i\%2)$ : donc forcément $b_i = +((n_i-1)\%2)$. (On prendra note du fait que $b_j = (n_j\%2)$ si $j>i$ +par maximalité de $i$.) Définissons les $n'_j$ comme suit : on pose +$n'_j = n_j$ si $j>i$, et $n'_i = n_i-1$, et enfin, pour $j<i$, on +pose $n'_j = n_j + ((n_j+b_j)\%2)$. Par construction (comme $n'_j = +n_j$ si $j>i$ et $n'_i = n_i$ et $n'_j \geq n_j$ si $j\leq i$), le +$(n'_0,n'_1,\ldots,n'_k)$ qu'on vient de définir est bien un voisin +sortant de $(n_0,n_1,\ldots,n_k)$. Par ailleurs, $(n'_j\%2) = b_j$ : +en effet, pour $j>i$ cela résulte de $b_j = (n_j\%2)$ et $n'_j = +n_j$ ; pour $j=i$ cela résulte de $b_i = ((n_i-1)\%2)$ et $n'_i = +n_i-1$ ; et pour $j<i$ cela résulte du fait que $n'_j = n_j + +((n_j+b_j)\%2)$ est congru à $n_j + n_j + b_j$ donc à $b_j$ +modulo $2$. En comparant insérant la formule $(n'_j\%2) = b_j$ qu'on +vient de montrer dans $r = 2^k\,b_k + \cdots + 2\,b_1 + b_0$, on voit +que $r = 2^k\,(n'_k\%2) + \cdots + 2\,(n'_1\%2) + (n'_0\%2)$. qui est +donc dans $S$. Ceci conclut le (B), donc l'induction et l'ensemble de +la démonstration. +\end{corrige} % |