Start writing test for 2023 (first exercise on nim positions).

1 files changed, 267 insertions, 0 deletions

diff --git a/controle-20230417.tex b/controle-20230417.tex
new file mode 100644
index 0000000..e7fcdcf
--- /dev/null
+++ b/controle-20230417.tex
@@ -0,0 +1,267 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+\usepackage{wasysym}
+\usepackage{url}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{matrix,calc}
+\usepackage{hyperref}
+%
+%\externaldocument{notes-mitro206}[notes-mitro206.pdf]
+%
+\theoremstyle{definition}
+\newtheorem{comcnt}{Tout}
+\newcommand\thingy{%
+\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
+\renewcommand{\qedsymbol}{\smiley}
+%
+\newcommand{\outnb}{\operatorname{outnb}}
+\newcommand{\downstr}{\operatorname{downstr}}
+\newcommand{\precs}{\operatorname{precs}}
+\newcommand{\mex}{\operatorname{mex}}
+\newcommand{\id}{\operatorname{id}}
+\newcommand{\limp}{\Longrightarrow}
+\newcommand{\gr}{\operatorname{gr}}
+\newcommand{\rk}{\operatorname{rk}}
+\newcommand{\fuzzy}{\mathrel{\|}}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+%
+\DeclareFontFamily{U}{manual}{} 
+\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
+\newcommand{\manfntsymbol}[1]{%
+    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
+\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
+\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
+  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
+%
+\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
+\newif\ifcorrige
+\corrigetrue
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
+{{\hbox{}\nobreak\hfill\checkmark}%
+\ifcorrige\par\smallbreak\else\egroup\par\fi}
+%
+%
+%
+\begin{document}
+\ifcorrige
+\title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}}
+\else
+\title{MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}}
+\fi
+\author{}
+\date{13 avril 2022}
+\maketitle
+
+\pretolerance=8000
+\tolerance=50000
+
+\vskip1truein\relax
+
+\noindent\textbf{Consignes.}
+
+Les exercices sont totalement indépendants.  Ils pourront être traités
+dans un ordre quelconque, mais on demande de faire apparaître de façon
+très visible dans les copies où commence chaque exercice.
+
+\medbreak
+
+L'usage de tous les documents (notes de cours manuscrites ou
+imprimées, feuilles d'exercices, livres) est autorisé.
+
+L'usage des appareils électroniques est interdit.
+
+\medbreak
+
+Durée : 2h
+
+Barème \emph{indicatif} : \textcolor{red}{XXX}.
+
+\ifcorrige
+Ce corrigé comporte \textcolor{red}{XXX} pages (page de garde incluse).
+\else
+Cet énoncé comporte \textcolor{red}{XXX} pages (page de garde incluse).
+\fi
+
+\vfill
+{\noindent\tiny
+\immediate\write18{sh ./vc > vcline.tex}
+Git: \input{vcline.tex}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+
+\pagebreak
+
+
+%
+%
+%
+
+\exercice
+
+On considère le jeu de nim éventuellement transfini.  (On rappelle
+qu'il est défini de la manière suivante : une position du jeu est un
+tuple $(\alpha_1,\ldots,\alpha_r)$ d'ordinaux, on dit qu'il y a
+« $\alpha_i$ bâtonnets sur la ligne $i$ », et un coup consiste à
+décroître strictement \emph{un et un seul} des $\alpha_i$, autrement
+dit il existe un coup de $(\alpha_1,\ldots,\alpha_r)$ vers
+$(\alpha_1,\ldots,\beta,\ldots,\alpha_r)$ où $\beta<\alpha_i$ est mis
+à la place de $\alpha_i$.)
+
+Pour chacune des positions suivantes, dire si c'est une position P
+(c'est-à-dire gagnante pour le joueur qui vient de jouer) ou N
+(c'est-à-dire gagnante pour le joueur qui doit jouer), et, dans ce
+dernier cas, donner un coup gagnant possible pour le joueur en
+question.
+
+(a) $(1,2,3)$ (autrement dit, une ligne avec $1$ bâtonnet, une ligne
+avec $2$, et une ligne avec $3$)
+
+\begin{corrige}
+On a $1 = 2^0$ et $2 = 2^1$ et $3 = 2^1 + 2^0 = 2^1 \oplus 2^0$ si
+bien que $1 \oplus 2 \oplus 3 = 0$ : la valeur de Grundy de la
+position est $0$, et c'est donc une position P.
+\end{corrige}
+
+(b) $(3,6,9)$
+
+\begin{corrige}
+On a $3 = 2^1 + 2^0 = 2^1 \oplus 2^0$ et $6 = 2^2 + 2^1 = 2^2 \oplus
+2^1$ et $9 = 2^3 + 2^0 = 2^3 \oplus 2^0$ si bien que $3 \oplus 6
+\oplus 9 = 2^3 \oplus 2^2 = 2^3 + 2^2 = 12$ : la valeur de Grundy de
+la position est $12$, et c'est donc une position N.
+
+Pour trouver un coup gagnant, c'est-à-dire un coup vers une
+position P, on cherche à annuler la valeur de Grundy : autrement dit,
+on cherche à remplacer le nombre $n$ de bâtonnets d'une ligne par $n
+\oplus 12$, et il s'agit donc de trouver une ligne telle que $n \oplus
+12 < n$.  On vérifie facilement que la seule possibilité est de
+réduire la ligne ayant $9$ bâtonnets à $9 \oplus 12 = 2^2 + 2^0 = 5$
+bâtonnets.  Bref, le seul coup gagnant est $(3,6,9) \to (3,6,5)$.
+\end{corrige}
+
+(c) $(\omega,\omega2,\omega3)$
+
+\begin{corrige}
+En se rappelant que $\omega = 2^{\omega}$, on a $\omega2 =
+2^{\omega+1}$ et $\omega3 = 2^{\omega+1} + 2^{\omega}$ en binaire : on
+a donc $\omega \oplus (\omega2) \oplus (\omega3) = 0$ : la valeur de
+Grundy de la position est $0$, et c'est donc une position P.
+\end{corrige}
+
+(d) $(\omega,\omega^2,\omega^3)$
+
+\begin{corrige}
+En se rappelant de nouveau que $\omega = 2^{\omega}$, on a $\omega^2 =
+2^{\omega2}$ et $\omega^3 = 2^{\omega3}$ en binaire : on a donc
+$\omega \oplus \omega^2 \oplus \omega^3 = 2^{\omega3} + 2^{\omega2} +
+2^\omega = \omega^3 + \omega^2 + \omega =: \gamma$ : la valeur de
+Grundy de la position est $\gamma \neq 0$, et c'est cdonc une
+position N.
+
+Comme dans la question (b), on cherche à annuler la valeur de Grundy,
+autrement dit remplacer le nombre $\alpha$ de bâtonnets d'une ligne
+par $\alpha \oplus \gamma$ (où $\gamma = \omega^3 + \omega^2 +
+\omega$, qu'il vaut mieux penser comme $2^{\omega3} \oplus 2^{\omega2}
+\oplus 2^\omega$) d'une manière à ce que le résultat soit plus petit.
+On vérifie facilement que la seule possibilité est de réduire la ligne
+ayant $\omega^3$ bâtonnets à $\omega^3 \oplus \gamma = \omega^2 +
+\omega$ bâtonnets.  Bref, le seul coup gagnant est
+$(\omega,\omega^2,\omega^3) \to (\omega,\omega^2,\omega^2+\omega)$.
+\end{corrige}
+
+(e) $(\omega,\omega^\omega,\omega^{\omega^\omega})$
+
+\begin{corrige}
+En se rappelant une fois de plus que $\omega = 2^{\omega}$, on a
+$\omega^\omega = (2^\omega)^\omega = 2^{\omega\times\omega} =
+2^{\omega^2}$, et $\omega^{\omega^\omega} = (2^\omega)^{\omega^\omega}
+= 2^{\omega\times \omega^{\omega}} = 2^{\omega^{1+\omega}} =
+2^{\omega^\omega}$.  Le raisonnement est alors exactement analogue à
+la question (d) (car la seule chose qui importe dans cette question
+ait qu'on ait affaire à trois puissances de $2$ distinctes) : la
+valeur de Grundy de la position est $\gamma := 2^{\omega^\omega} +
+2^{\omega^2} + 2^\omega = \omega^{\omega^\omega} + \omega^\omega +
+\omega \neq 0$ donc c'est une position N, et le seul coup gagnant est
+$(\omega,\omega^\omega,\omega^{\omega^\omega}) \to
+(\omega,\omega^\omega,\omega^\omega + \omega)$.
+\end{corrige}
+
+(f) $(\varepsilon_1, \varepsilon_2, \varepsilon_3)$ où $\varepsilon_0
+< \varepsilon_1 < \varepsilon_2 < \varepsilon_3$ sont les quatre
+premiers ordinaux\footnote{On peut définir $\varepsilon_{n+1}$ comme
+  la limite, c'est-à-dire la borne supérieure, de la suite
+  $(u_k)_{k<\omega}$ strictement croissante définie par $u_0 =
+  (\varepsilon_n) + 1$ et $u_{k+1} = \omega^{u_k}$, c'est-à-dire $u_1
+  = \omega^{(\varepsilon_n) + 1}$ et $u_2 =
+  \omega^{\omega^{(\varepsilon_n) + 1}}$, etc., mais on n'aura pas
+  besoin de ce fait.}  vérifiant $\varepsilon = \omega^\varepsilon$.
+
+\begin{corrige}
+Pour $i \in \{1,2,3\}$ (ou n'importe quel ordinal, en fait), on a
+$\varepsilon_i = \omega^{\varepsilon_i} = (2^\omega)^{\varepsilon_i} =
+2^{\omega\cdot\varepsilon_i} = 2^{\omega\cdot\omega^{\varepsilon_i}} =
+2^{\omega^{1+\varepsilon_i}} = 2^{\omega^{\varepsilon_i}} =
+2^{\varepsilon_i}$ (en utilisant au passage le fait, facilement
+vérifié, que $1 + \rho = \rho$ quel que soit l'ordinal infini $\rho$).
+Le raisonnement est alors exactement analogue aux questions (d) et (e)
+(car la seule chose qui importe dans ces questions ait qu'on ait
+affaire à trois puissances de $2$ distinctes) : la valeur de Grundy de
+la position est $\gamma := 2^{\varepsilon_3} + 2^{\varepsilon_2} +
+2^{\varepsilon_1} = \varepsilon_3 + \varepsilon_2 + \varepsilon_1 \neq
+0$ donc c'est une position N, et le seul coup gagnant est
+$(\varepsilon_1, \varepsilon_2, \varepsilon_3) \to (\varepsilon_1,
+\varepsilon_2, \varepsilon_2 + \varepsilon_1)$.
+\end{corrige}
+
+(g) Donner un exemple de position N du jeu de nim (de préférence fini)
+avec un nombre distinct de bâtonnets sur chaque ligne (i.e., les
+$\alpha_i$ sont deux à deux distincts), où il existe strictement plus
+qu'un coup gagnant pour le joueur qui doit jouer.  (Pour indication,
+ceci est possible à partir de trois lignes de bâtonnets.)
+
+\begin{corrige}
+On cherche donc une position $(n_1,n_2,n_3)$ avec trois lignes de
+bâtonnets, de valeur de Grundy $g := n_1 \oplus n_2 \oplus n_3$, telle
+qu'au moins deux des trois quantités $n_i \oplus g$ soit strictement
+inférieure au $n_i$ correspondant (le raisonnement étant expliqué à la
+question (b)), en prenant note du fait que $n_1 \oplus g = n_2 \oplus
+n_3$ et de façon analogue pour les trois autres.  On cherche donc, par
+exemple, à avoir $n_1 \oplus n_3 < n_2$ et $n_1 \oplus n_2 < n_3$.
+Ceci n'est pas difficile en prenant par exemple pour $n_1$ une
+puissance de $2$ qui existe dans l'écriture binaire de $n_2$ et
+de $n_3$ mais telle qu'en enlevant on obtient des nombres strictement
+plus petits.  Par exemple, la position $(2,6,7)$ (de valeur de Grundy
+$2\oplus 6\oplus 7 = 3 =: g$) admet des coups gagnants vers $(2,5,7)$
+ou $(2,6,4)$ ou même $(1,6,7)$.
+\end{corrige}
+
+
+
+
+%
+%
+%
+\end{document}