path: root/controle-20230417.tex

%% 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}