From 474bde064eddaf8579ef6119fb16c0fbcec04656 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Sun, 22 Jun 2025 20:14:23 +0200
Subject: Write answer to second exercise.

---
 controle-20250626.tex | 188 ++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 182 insertions(+), 6 deletions(-)

(limited to 'controle-20250626.tex')

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}
 
 
 %
-- 
cgit v1.2.3