\documentclass[a4paper,10pt]{article}
 \usepackage[T1]{fontenc} %encodage des caractï¿½es
 \usepackage[latin1]{inputenc}%decodage des caractï¿½es
 \usepackage[frenchb]{babel}   %gestion du francais
 \usepackage{verbatim,ifthen}
\usepackage{textcomp,graphicx,psfrag}
\usepackage{pst-plot,array}
\usepackage{pst-node,pstcol,pst-3d,pst-eucl}
\usepackage{calc}
 \usepackage[dvips]{epsfig}
 \usepackage{amsmath}  %gestion des symboles math\'{e}matiques
\usepackage{amsfonts,mathrsfs} %gestion des fontes math\'{e}matiques
\usepackage{amssymb,amsthm}  %gestion des symboles math\'{e}matiques
\usepackage{pifont}
\usepackage{slashbox}
\usepackage{multirow}
\usepackage{tabularx}
\usepackage{multicol}
\usepackage{variations}
% %-----------------------------
 \usepackage{fancyhdr} %gestion des entetes et des pieds de page
\usepackage[dvips,ps2pdf,colorlinks=true]{hyperref}
\usepackage{calc}
%Pour une numérotation en gras à la française: a. et pas: (a)
\renewcommand{\labelenumi}{{\bf{\arabic{enumi}}.}}
\renewcommand{\labelenumii}{{\bf{\alph{enumii}}.}}

\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\usepackage[marginratio=1:1,textwidth=15cm,textheight=24cm,marginparwidth=0pt,headheight=3cm]{geometry}
\def\Ouv{$\left(\text{O},\vec{u}\,,\vec{v}\,\right)$}
\newcommand{\vect}[1]{\mathchoice%
{\overrightarrow{\displaystyle\mathstrut#1\,\,}}%
{\overrightarrow{\textstyle\mathstrut#1\,\,}}%
{\overrightarrow{\scriptstyle\mathstrut#1\,\,}}%
{\overrightarrow{\scriptscriptstyle\mathstrut#1\,\,}}}
\DeclareMathOperator{\e}{e}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}

\pagestyle{fancy}

%\usepackage[firstpage]{draftwatermark}

\newcounter{exercice}
\newcommand{\exods}[2]{% Titre-bareme
  \addtocounter{exercice}{1}
  \vspace{1em} \par \noindent
  \raisebox{-0.7ex}{\bf Exercice \no \arabic{exercice}  #1}
  \hrulefill \raisebox{-0.7ex}{\, (\, \textit{#2 points} \, )}
  \par \vspace{0.5em}
}
\theoremstyle{definition}\newtheorem{Def}{D\'efinition}
\theoremstyle{plain}\newtheorem{prop}{Propri\'et\'e}
\theoremstyle{plain}\newtheorem{theo}{Th\'{e}or\`{e}me}
\theoremstyle{remark}\newtheorem*{rem}{Remarque}
%%%_________________________________________
%%%
%%%                DEBUT
%%%_________________________________________
%\title{{\bf Titre}}
%\\rule{0cm}{1cm}\noindent\begin{center}
%includegraphics[width=7cm]{petite_frise_bague_viking}
%end{center}}
%\author{Vincent PANTALONI}
%\date{{\small {\Police Version du \today}}}
%\renewcommand{\iff}{\Longleftrightarrow}
%%%%
%\makeindex
\title{%
{\bf {\Huge Le jeu de Marienbad.}\\
Théorie mathématique,\\
stratégie gagnante.}}
\author{Vincent PANTALONI
}
\date{\today
\\[1ex]
{\bf |~|~|~|\\
|~|~|\\
|~|\\
|}}

\begin{document}
\newcommand{\eps}{\varepsilon}
\newcommand{\cp}{$(\mathcal{CP})\ $}
\newcommand{\ci}{$(\mathcal{CI})\ $}
\newcommand{\cpu}{$(\mathcal{CP}_1)\ $}
\newcommand{\cpd}{$(\mathcal{CP}_2)\ $}
\maketitle
\pagestyle{fancy}
\lfoot{\url{http://prof.pantaloni.free.fr}}
\rfoot{\href{mailto:v.pantaloni@laposte.net}{v.pantaloni@laposte.net}}
Le \emph{jeu de Marienbad} tire son nom du film \emph{L'Année dernière à
  Marienbad} d'Alain Resnais sorti en 1961, il est aussi appellé \emph{jeu
de Nim} ou \emph{Fan-tan} en Chine, ou encore \emph{Tiouk-tiouk} en
Afrique. Ce jeu est probablement très ancien, il se joue entre deux
joueurs avec des
pions, graines ou allumettes. Nous étudierons la version suivante du
jeu:

\paragraph{Règles du jeu:} On dispose des allumettes en $n$ lignes
contenant chacune un nombre quelconque d'allumettes, disons respectivement $a_1$, $a_2$,\dots{}, $a_n$ allumettes (les
$a_i$ sont dans~$\mathbb{N}^*$). Chacun des deux joueurs doit à son
tour oter un nombre quelconque (non nul) d'allumettes de la ligne
de son choix (on dira qu'il \emph{joue un coup}). Le perdant est celui qui prend la dernière allumette.
\paragraph{Exemple de partie.} Souvent on joue avec la configuration de départ ci--contre.
\\ \noindent%
\begin{minipage}{\linewidth - 2.5cm}
Montrons que dans ce cas, celui qui commence (disons le joueur 1) gagne à coup sûr si il
joue bien. Pour cela on va étudier toutes les ripostes possibles de
son adversaire, le joueur 2. Le joueur 1 commence par oter les quatre
allumettes, après quoi le joueur 2 peut laisser l'une des six configurations:
\end{minipage}
\begin{minipage}{2.5cm}
  \begin{center}
  {\bf |\\
|~|\\
|~|~|\\
|~|~|~|}
\end{center}
\end{minipage}

% \vspace{-2ex}
\setlength{\columnsep}{0.8cm}
% \setlength{\columnseprule}{0.5pt}
\begin{multicols}{6}
\begin{center}
  {\bf |\\
|~|\\
|~|}
\end{center}

\begin{center}
  {\bf \quad\\
|~|\\
|~|~|}
\end{center}

\begin{center}
  {\bf |\\
|\\
|~|~|}
\end{center}

\begin{center}
  {\bf |\\
|~|\\
|}
\end{center}

\begin{center}
  {\bf |\\
\quad\\
|~|~|}
\end{center}

\begin{center}
  {\bf |\\
|~|\\
\quad}
\end{center}
\end{multicols}%\vspace{-2ex}
\noindent Ensuite  le joueur 1 laisse les configurations suivantes. J'ai groupé
les cas deux par deux:
% \vspace{-2ex}
\setlength{\columnsep}{0.8cm}
 \setlength{\columnseprule}{0.5pt}
\begin{multicols}{3}


\begin{center}
  {\bf \quad\\
|~|\\
|~|}
\end{center}

\begin{center}
  {\bf |\\
|\\
|}
\end{center}

\begin{center}
  {\bf |}
\end{center}
\end{multicols}%\vspace{-2ex}
\noindent Pour le dernier cas, c'est fini, pour le deuxième les coups sont
forcés et le joueur~2 perd encore, il reste le premier cas à
détailler. Le joueur~2 otera une ou deux allumettes, et il restera
l'une des~deux configurations:
% \vspace{-2ex}
\setlength{\columnsep}{0.8cm}
 \setlength{\columnseprule}{0pt}
\begin{multicols}{6}
\begin{center}
  {\bf |\\
|~|}
\end{center}

\begin{center}
  {\bf |~|\\
\quad}
\end{center}
\begin{center}
  
\end{center}
\begin{center}
  
\end{center}
\begin{center}
  
\end{center}
\begin{center}
  
\end{center}
\end{multicols}%\vspace{-2ex}
Il est facile dans chaque cas au joueur~1 de laisser la dernière
allumette à son adversaire. On va montrer dans le cas général qu'il
existe une stratégie gagnante (\emph{i.e.} une méthode de jeu qui
permet à coup sûr de gagner) pour l'un des deux joueurs. Dans notre
exemple c'était pour le joueur qui commençait.
\paragraph{Décomposition en base 2.} On décompose chaque $a_i$ (pour
$i$ variant de 1 à $n$) en base~2:
\[ a_i= \sum_{k\in\N}\eps_i(k)2^k \quad\text{où}\quad \forall
k\in\{1,2,\dots{},n\}, \eps_i(k)\in\{0,1\}\]
Cette écriture est unique, et à partit d'une certaine valeur $k_i$,
tous les $\eps_i(k)$ sont nuls pour $k$ strictement supérieur
à~$k_i$. Le nombre $a_i$ peut être alors noté:
\[a_i=\overline{\eps_i(k_i)\eps_i(k_i-1)\cdots{}\eps_i(2)\eps_i(1)\eps_i(0)}\]
La barre signifiant \og en base 2.\fg{}\smallskip\\
\noindent 
{\bf Exemple:} $13=8+4+1=2^3+2^2+0 \times 2^1+2^0=\overline{1101}$. On
a $\eps(3)=\eps(2)=\eps(0=1$ et $\eps(1)=0$\\
$2^{k_i}$ est laplus grande puissance de 2 inférieure à $a_i$. On
continue ensuite avec $a_i-2^{k_i}$.\smallskip\par
Chaque ligne est ainsi décomposée en \og paquets\fg{} d'effectif une
puissance de deux. On appelera $k$-paquet un tel paquet d'effectif~$2^k$
\begin{rem}\label{rem:uniquepaquet}
  Comme les $\eps(k)$ valent 0 ou 1, chaque ligne comporte au plus un
 $k$-paquet  pour tout $k$ dans~$\mathbb{N}$.
\end{rem}
On compte ensuite le nombre total (dans toutes les lignes) de $k$-paquets pour chaque~$k$ dans~$\mathbb{N}$. \emph{i.e.} pour tout $k$
dans~$\mathbb{N}$ on calcule:
\[N(k)=\sum_{i=1}^n \eps_i(k)\]
\begin{Def}
  On dira qu'on a une \emph{configuration paire}, noté \cp  si l'un ou
  l'autre des points suivants est vérifié:
 % \begin{dingautolist}{172}
  \begin{itemize}
  \item[\cpu]:  $\forall k \in\mathbb{N}; N(k)\equiv 0~[2]$.
  \item[\cpd]: $\forall k \in\mathbb{N}^*; N(k)=0$ et $N(0)\equiv
    1~[2]$.
  \end{itemize}
Toute autre configuration sera dite impaire, qu'on notera \ci.
  % \end{dingautolist}
\end{Def}
%Dans la suite les cas \ding{172} et \ding{173} d'une \cp seront notés
%\cpu et \cpd respectivement. 
\noindent \cpu signifie que tous les
    $N(k)$ sont pairs, et \cpd qu'il n'y a que des lignes d'une
    allumette, et ces lignes sont en nombre impair. Si on reprend
    notre partie exemple du début, on remarque que le joueur~1 a
    toujours laissé une \cp à son adversaire qui lui n'a pu que
    laisser une \ci au joueur~1.\smallskip\\
\noindent 
{\bf Exemple:} La configuration $(|;||;|||)=(1;2;3)$ est paire car on décompose 3
en $3=2+1=\overline{11}$ et on a donc au total deux paquets de 1 et
deux paquets de 2, \emph{i.e.} $N(0)=N(1)=2$. Par contre vérifiez que
les six configurations possibles qui ont suivi sont des~\ci.\smallskip

On peut maintenant
    énoncer les deux propriétes qui font qu'il existe une stratégie
    gagnante pour celui qui peut à un moment laisser une situation
    paire à son adversaire:
    \begin{prop}
      \label{prop:marienbad1}
Toute \cp devient nécessairement une \ci après un coup.
    \end{prop}
\begin{prop}
      \label{prop:marienbad2}
De toute \ci on peut obtenir une \cp en un coup.
    \end{prop}
Ces deux propriétés asurent conjointement qu'un des joueurs pourra
toujours laisser une \cp à son adversaire. Le nombre d'allumettes se
réduisant à chaque coup, il finira par laisser la dernière allumette
(c'est une \cp!) à son adversaire, ainsi il gagnera.
\begin{proof}
  \textbf{(Propriété~\ref{prop:marienbad1}.)} On suppose qu'on a une
  \cp. 
  \begin{itemize}
  \item Si on a une \cpd, c'est trivial: On n'a que des lignes de 1 en
  nombre impair, après quoi on laisse nécessairement que des lignes
  de~1 en nombre pair, ce qui est une \ci. (\'Eventuellement on prend
  la dernière allumette et on a perdu)
\item On suppose qu'on a une \cpu. L'idée est la suivante: lorsqu'on
  enlève un nombre quelconque d'allumettes, il existe $k$ tel qu'on suprime exactement un $k$-paquet dont la parité change et devient donc
  impair, ainsi on a une \ci.
%  En fait on peut supprimer plusieurs
%   paquets, mais un seul de chaque type, on peut aussi créer un paquet
%   (ou plus)
%   mais de types inférieurs et dont on changera la parité. Par exemple en
%   otant 1 allumette parmi 4, on supprime un paquet de 4 et on en
%   créer un de 1 et un de~2, en tous cas la parité des paquets de 4
%   a changé et cela nous suffit.
  Formalisons celà.\par
 On choisit un tas quelconque avec $a$ allumettes ($a\in\N^*$). On note en base 2:
\[ a=\sum_{k\in\N}\eps(k)2^k \]
En otant des allumettes, on en laisse $a'=
\sum_{k\in\N}\eps'(k)2^k$. avec $a'$ strictement inférieur à~$a$. Donc
il existe un certain $k_0$ dans~$\N$ tel que $\eps(k_0)=1$ et
$\eps'(k_0)=0$. En effet, comme $a\neq a'$ il existe un $k$ dans~$\N$ tel que
$\eps(k)\neq\eps'(k)$, et si pour tout $k$ dans $\N$:
$\eps(k)=1\implies\eps'(k)=1$ alors on aurait $a'\geq a$, ce qui n'est
pas. On peut donc considérer un entier naturel $k_0$ tel que : 
\[\eps(k_0)=1\quad\text{et}\quad\eps'(k_0)=0.\]
On a une \cpu, donc $N(k_0)$ est pair, ainsi après un coup on a
$N'(k_0)=N(k_0)-1$ qui est impair et on laisse donc une~\ci.
  \end{itemize}
\end{proof}
\begin{proof}
  \textbf{(Propriété~\ref{prop:marienbad2}.)} On suppose qu'on a une
  \ci. On distingue encore plusieurs cas:
  \begin{itemize}
  \item Si il n'y a que des lignes de 1 (en nombre pair), on n'a pas
    le choix: on en prend une et on a une~\cpd.
  \item  Si il n'y a que des lignes de 1, sauf une, disons la ligne $\ell$ c'est aussi facile
    de laisser une~\cpd: on retire toutes les allumettes ou on en
    laisse une sur cette ligne~$\ell$.
  \item Il nous reste le cas où il existe au moins deux lignes
    comportant plus d'une allumette. On va exposer une méthode pour
    laisser une~\cpu dans ce cas. C'est à dire ne laisser que des
    $N'(k)$ pairs.\par
Soit $k^*$ le plus grand entier $k$ tel que $N(k)$ est impair. On
choisit une ligne~$\ell$ comportant un paquet de $2^{k^*}$ allumettes
\emph{i.e.} une ligne d'effectif~$a$ tel que $\eps(k^*)=1$. L'objectif
est de soustraire à~$a$ un nombre d'allumettes tel que tous les $N(k)$
pairs le restent et que que tous les $N(k)$ impairs deviennent
pairs. On distingue trois ensembles:
\begin{align*}
  \mathscr{P}&=\left\{k\in\N\,; N(k)\equiv 0~[2] \right\}\\
  \mathscr{I}^+&=\left\{k\in\N\,; N(k)\equiv 1~[2] \ \,\text{et}\ 
    \eps(k)=1 \right\}\\
  \mathscr{I}_-&=\left\{k\in\N\,; N(k)\equiv 1~[2] \ \,\text{et}\ 
  \eps(k)=0 \right\}
\end{align*}
On veut changer la parité des $N(k)$ lorsque $k$ appartient à
$\mathscr{I}_-$ ou $\mathscr{I}^+$ et ne pas la changer pour les $k$
dans~$\mathscr{P}$. Lorsque $k\in\mathscr{I}^+$ cela signifie que la
ligne~$\ell$ contient un $k$-paquet et on veut donc le supprimer; lorsque $k\in\mathscr{I}_-$ cela signifie que la
ligne~$\ell$ ne contient pas de $k$-paquet et on veut le créer. C'est
possible: 
\smallskip\\
\noindent 
{\bf Exemple:} Supposons que $a=90$ qui s'écrit en base~2:
$a=\overline{1011010}$. Supposons que:
\[ \mathscr{P}=\left\{0;3;5;6 \right\};\ %
\mathscr{I}^+=\left\{1;4 \right\};\ %
\mathscr{I}_-=\left\{2 \right\}%
\]
Ainsi  $k^*=4$. Pour plus de lisibilité, je note un $+$ ou un $-$ au
dessus du chiffre correspondant dans l'écriture de~$a$ selon si il correspond
à un $k$ de $\mathscr{I}^+$ ou de $\mathscr{I}_-$:
\[
a=\overline{\stackrel{}{1}\stackrel{}{0}\stackrel{+}{1}\stackrel{}{1}\stackrel{-}{0}\stackrel{+}{1}\stackrel{}{0}}
\]
Il suffit alors d'échanger les 0 et 1 si ils comportent un signe. On pose:
\[
a'=\overline{10{\bf 0}1{\bf 1}{\bf 0}0}
\]
Ce nombre $a'$ est bien inférieur à $a$, on a donc retiré des
allumettes, et on a changé la parité de tous les $k$-paquets pour lesquels
$N(k)$ était impair.
\smallskip
Formalisons celà dans le cas général. On a:
\begin{align*}
  a&=\sum_{k\in\mathscr{P}}\eps(k)2^k+\sum_{k\in\mathscr{I}^+}\eps(k)2^k+\sum_{k\in\mathscr{I}_-}\eps(k)2^k\\
&=\sum_{k\in\mathscr{P}}\eps(k)2^k+\sum_{k\in\mathscr{I}^+}2^k
\end{align*}
On pose alors: 
\[a'=\sum_{k\in\mathscr{P}}\eps(k)2^k+\sum_{k\in\mathscr{I}_-}2^k\]
C'est à dire qu'on retire $a-a'$ allumettes, vérifions que $a-a'$ est
supérieur à~1:
\begin{align*}
  a-a'&=\sum_{k\in\mathscr{I}^+}2^k-\sum_{k\in\mathscr{I}_-}2^k\\
      &=2^{k^*}+\sum_{k\in\mathscr{I}^+\setminus\{k^*\}}2^k-\sum_{k\in\mathscr{I}_-}2^k\\
&\geq 2^{k^*}-\sum_{k\in\mathscr{I}_-}2^k
\end{align*}
Or par définition de $k^*$, et par le choix d'une ligne qui contient
un $k^*$--paquet, on a $k^*$ qui appartient à~ $\mathscr{I}^+$éet: 
\[\forall k \in \mathscr{I}_-\,;\ k\leq (k^*-1) \]
 ainsi:

\[  a-a'\geq 2^{k^*}-\sum_{k=0}^{k^*-1} 2^k =1\]
On a donc bien enlevé au moins une allumette. Par construction de $a'$ on a:
\begin{list}{$\bullet$}{}
\item $k\in \mathscr{P}^{\phantom{+}}\implies N'(k)=N(k)$
\item $k\in \mathscr{I}^+\implies N'(k)=N(k)-1$
\item $k\in \mathscr{I}^{\phantom{+}}_-\implies N'(k)=N(k)+1$
\end{list}
Ainsi pour tout $k$ dans $\mathbb{N}$, $N'(k)$ est pair et on a bien
une~\cpu.
  \end{itemize}
\end{proof}
%\paragraph{En pratique:}
\end{document}