From 27a58e0dd89f966b6cb95780373334f2c448d3e2 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Sun, 17 Apr 2016 20:05:34 +0200
Subject: Start writing an exam exercise on the nim product.
---
controle-20160421.tex | 62 +++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 62 insertions(+)
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}
+
+
%
%
--
cgit v1.2.3