summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-04-17 18:05:34 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-04-18 10:22:35 (GMT)
commit27a58e0dd89f966b6cb95780373334f2c448d3e2 (patch)
tree3eb11771df5517ebb816a40ae5889cb33c521d60
parent7c6d53e9fb8db5009818f18c06ce7bdac48eb54b (diff)
downloadmitro206-27a58e0dd89f966b6cb95780373334f2c448d3e2.zip
mitro206-27a58e0dd89f966b6cb95780373334f2c448d3e2.tar.gz
mitro206-27a58e0dd89f966b6cb95780373334f2c448d3e2.tar.bz2
Start writing an exam exercise on the nim product.
-rw-r--r--controle-20160421.tex62
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}
+
+
%
%