Start writing an exam exercise on the nim product.

1 files changed, 62 insertions, 0 deletions

diff --git a/controle-20160421.tex b/controle-20160421.tex
index a67231a..d77b957 100644
--- a/controle-20160421.tex
+++ b/controle-20160421.tex
@@ -278,6 +278,68 @@ et on a prouvé que c'étaient bien les seuls.
 \end{corrige}
 
 
+%
+%
+%
+
+\exercice
+
+On considère le jeu suivant : une position du jeu consiste en un
+certain nombre (fini) de jetons placés sur un damier transfini dont
+les cases étiquetées par un couple $(\alpha,\beta)$ d'ordinaux (on
+dira que $\alpha$ est [le numéro de] la ligne de la case et $\beta$
+[le numéro de] la colonne).
+
+Un coup du jeu consiste à faire l'opération suivante : le joueur qui
+doit jouer choisit un jeton du jeu, disons qu'il soit sur la case
+$(\alpha,\beta)$, et il choisit aussi $\alpha' < \alpha$ et $\beta' <
+\beta$, il retire le jeton choisi de la case $(\alpha,\beta)$ et le
+remplace par \emph{trois} jetons, sur les cases $(\alpha',\beta)$,
+$(\alpha,\beta')$ et $(\alpha',\beta')$.  (À titre d'exemple, si le
+jeu comporte un seul jeton sur la case $(42,7)$, un coup valable
+consiste à le remplacer par trois jetons, sur les cases $(18,7)$,
+$(42,5)$ et $(18,5)$.)  Le nombre de jetons présents augmente donc
+de $2$ à chaque coup joué.
+
+On remarquera que les jetons sur la ligne ou la colonne $0$ ne peuvent
+plus être retirés ou servir de quelque manière que ce soit : on pourra
+dire que cette ligne et cette colonne $0$ sont la « défausse » des
+jetons.  Le jeu se termine lorsque chacun des jetons est sur la ligne
+ou la colonne $0$ (=dans la défausse), car il n'est alors plus
+possible de jouer.  Les joueurs (Alice et Bob) jouent à tour de rôle
+et celui qui ne peut plus jouer a perdu.
+
+(0) Décrire brièvement le jeu complètement équivalent dans lequel il
+n'y a pas de ligne ou de colonne $0$ (on fait démarrer la numérotation
+à $1$) et il n'y a pas de défausse (les jetons disparaissent plutôt
+qu'être défaussés) : quels sont les types de coups possibles à ce
+jeu ?
+
+\begin{corrige}
+Les jetons défaussés ne jouant aucun rôle dans le jeu, on peut les
+ignorer et obtenir un jeu équivalent.  Les lignes et les colonnes sont
+alors numérotés par des ordinaux non nuls, c'est-à-dire $\geq 1$.  Les
+quatre types de coups possibles dans ce jeu, selon que $\alpha'$ et/ou
+$\beta'$ vaut $0$, sont alors :
+\begin{itemize}
+\item simplement retirer un jeton de la case $(\alpha,\beta)$ [cas où
+  $\alpha' = 0$ et $\beta' = 0$],
+\item déplacer un jeton de la case $(\alpha,\beta)$ vers une case
+  $(\alpha,\beta')$ plus à gauche (i.e., $\beta' < \beta$) dans la
+  ligne [cas où $\alpha' = 0$ et $\beta' \neq 0$],
+\item déplacer un jeton de la case $(\alpha,\beta)$ vers une case
+  $(\alpha',\beta)$ plus haut (i.e., $\alpha' < \alpha$) dans la
+  colonne [cas où $\alpha' \neq 0$ et $\beta' = 0$],
+\item remplacer un jeton de la case $(\alpha,\beta)$ par un jeton sur
+  une case $(\alpha,\beta')$ plus à gauche dans la ligne, un autre sur
+  une case $(\alpha',\beta)$ plus haut dans la colonne, et un
+  troisième sur la case $(\alpha',\beta')$ à l'intersection de la
+  nouvelle ligne et de la nouvelle colonne, comme dans le jeu
+  d'origine [cas où $\alpha' \neq 0$ et $\beta' \neq 0$].
+\end{itemize}
+\end{corrige}
+
+
 
 %
 %