From 7e5e532094908dd3b5768bf830ca8f7087b9f932 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Thu, 18 Jun 2026 12:42:40 +0200
Subject: Third exercise, on a restricted variant of nim.

---
 controle-20260622.tex | 107 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 107 insertions(+)

diff --git a/controle-20260622.tex b/controle-20260622.tex
index e1f5345..266e314 100644
--- a/controle-20260622.tex
+++ b/controle-20260622.tex
@@ -551,6 +551,113 @@ parité considéré est déterminé.
   mais dont on ignore s'il est dans $\mathbf{P}$.\par}
 
 
+%
+%
+%
+
+\exercise
+
+Dans cet exercice, on considère une variante du jeu de nim (fini) dans
+laquelle on limite le nombre de bâtonnets qui peuvent être retirés en
+un seul coup.
+
+\medskip
+
+\textbf{(1)} Soit $k\geq 1$ un entier naturel, et soit
+$n\in\mathbb{N}$ un entier naturel.  On considère le jeu combinatoire
+dans lequel il y a une seule rangée de bâtonnets, initialement avec
+$n$ bâtonnets, et où chaque joueur, quand vient son tour, retire un
+nombre quelconque entre $1$ et $k$ bâtonnets.  (Plus exactement, les
+positions du jeu sont les entiers $i$ avec $0\leq i\leq n$, et on peut
+passer de la position $i$ à la position $j$ lorsque $1\leq i-j\leq
+k$.)  Comme d'habitude, le joueur qui ne peut pas jouer perd.
+Calculer la valeur de Grundy $\mathrm{g}_k(n)$ de ce jeu.
+(\textit{Indication :} On pourra commencer par calculer à la main les
+valeurs $\mathrm{g}_k(i)$ pour $0\leq i\leq k$, puis
+$\mathrm{g}_k(k+1)$ et plus si besoin est, et s'en servir pour
+conjecturer une formule générale que l'on démontrera.)
+
+\begin{corrige}
+La définition de la fonction de Grundy donne :
+\[
+\mathrm{g}_k(n) = \mex\{\mathrm{g}_k(i) : \max(0,n-k) \leq i \leq n-1\}
+\]
+où comme d'habitude $\mex S$ désigne le plus petit entier naturel qui
+n'est pas dans $S$.  Tant que $n\leq k$, on a donc juste
+$\mathrm{g}_k(n) = n$ comme au jeu de nim ; en revanche,
+$\mathrm{g}_k(k+1) = \mex\{1,2,\ldots,k\} = 0$ ; on a ensuite
+$\mathrm{g}_k(k+2) = \mex\{0,2,\ldots,k\} = 1$, et ainsi de suite.  On
+voit donc qu'il y a périodicité de période $k+1$.  Par récurrence
+sur $n$ on montre donc
+\[
+\mathrm{g}_k(n) = n \% (k+1)
+\]
+où $n \% (k+1)$ désigne le reste (compris entre $0$ et $k$ inclus) de
+la division euclidienne de $n$ par $k+1$.  On a déjà vu que c'était le
+cas pour $0\leq n\leq k$ ; et si $n>k$, on a $\mathrm{g}_k(n) =
+\mex\{\mathrm{g}_k(i) : n-k \leq i \leq n-1\}$, où (par hypothèse de
+récurrence) l'ensemble dont on prend le $\mex$ contient tous les
+restes des divisions euclidiennes modulo $k+1$ à l'exception de celle
+de $n$, qui est donc la valeur de $\mathrm{g}_k(n)$, ce qui conclut la
+récurrence.
+\end{corrige}
+
+\medskip
+
+\textbf{(2)} On considère maintenant le jeu combinatoire suivant : une
+position consiste en un certain nombre de bâtonnets $n_1,\ldots,n_r$
+arrangés en lignes (où $n_k$ désigne le nombre de bâtonnets sur la
+ligne numérotée $k$) ; chaque joueur, quand vient son tour, retire des
+bâtonnets selon les règles suivantes :
+\begin{itemize}
+\item comme au jeu de nim usuel, les bâtonnets retirés sont sur une et
+  une seule ligne (i.e., un des $n_k$ est remplacé par un $n'_k$ avec
+  $n'_k < n_k$), mais en plus
+\item le nombre de bâtonnets retirés ne peut pas excéder le numéro de
+  la ligne (i.e., $1 \leq n_k - n'_k \leq k$ : on peut retirer au plus
+  $1$ bâtonnet de la première ligne, ou au plus $2$ de la deuxième,
+  etc.).
+\end{itemize}
+En exprimant ce jeu en fonction des jeux considérés à la question (1),
+exprimer la valeur de Grundy de la position $(n_1,\ldots,n_r)$ en
+fonction des $\mathrm{g}_k(i)$.
+
+\begin{corrige}
+Comme les différentes lignes n'interagissent pas du tout, le jeu qu'on
+a décrit est la somme disjonctive du jeu décrit à la question (1) pour
+les différents $k$ qui numérotent les lignes.  D'après le théorème vu
+en cours sur le calcul de la fonction de Grundy d'une somme
+disjonctive, la valeur de Grundy recherchée est la somme de nim (=XOR)
+$\bigoplus_{k=1}^r \mathrm{g}_k(n_k) = \bigoplus_{k=1}^r (n \%
+(k+1))$.
+\end{corrige}
+
+\medskip
+
+\textbf{(3)} Exemple : calculer la valeur de Grundy de la position
+$(1,3,5,7)$ (soit $1$ bâtonnet sur la ligne $1$, $3$ sur la ligne $2$,
+etc.) pour le jeu décrit en (2).  Quel coup feriez-vous si vous deviez
+jouer en premier à partir de cette position ?
+
+\begin{corrige}
+On trouve :
+\begin{itemize}
+\item $n_1 \% (1+1) = 1 \% 2 = 1$,
+\item $n_2 \% (2+1) = 3 \% 3 = 0$,
+\item $n_3 \% (3+1) = 5 \% 4 = 1$,
+\item $n_4 \% (4+1) = 7 \% 5 = 2$.
+\end{itemize}
+Le XOR de tous ces nombres est $2$ : comme cette valeur de Grundy est
+non nulle, le premier joueur a une stratégie gagnante.  Pour trouver
+un coup gagnant, on cherche à trouver un $k$ et un $n'_k$ tel que le
+remplacement de $n_k$ par $n'_k$ annule la valeur de Grundy.  Le plus
+évident est de remplacer $n_4 = 7$ par $n'_4 = 5$ (i.e., retirer
+$2$ bâtonnets de la ligne $4$) ; mais on peut aussi remplacer $n_2 =
+3$ par $n'_2 = 2$ (i.e., retirer $1$ bâtonnet de la ligne $2$) ou bien
+remplacer $n_3 = 5$ par $n'_3 = 3$ (i.e., retirer $2$ bâtonnets de la
+ligne $3$).
+\end{corrige}
+
 
 %
 %
-- 
cgit v1.2.3