%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[mathserif,a4paper]{beamer}
%\documentclass[a4paper]{article}
%\usepackage[envcountsect,noxcolor]{beamerarticle}
%\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\DeclareUnicodeCharacter{00A0}{~}
% Beamer theme:
\usetheme{Goettingen}
%\usecolortheme{albatross}
%\usecolortheme{lily}
%\setbeamercovered{transparent}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
%
\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{matrix,arrows,snakes,calc}
%
\newcommand{\mex}{\operatorname{mex}}
%
\newcommand{\itempoint}{\strut\hbox{\color{beamerstructure}\donotcoloroutermaths$\blacktriangleright$}\nobreak\hskip.5em plus.5em\relax}
\renewcommand{\thefootnote}{\textdagger}
%
\pgfmathsetmacro{\nimstickheight}{1.0}
\pgfmathsetmacro{\nimstickline}{1.25}
\pgfmathsetmacro{\nimstickdist}{0.5}
\pgfmathsetmacro{\squaresize}{0.5}
\pgfmathsetmacro{\coinradius}{0.2}
\tikzstyle{nimstick}=[brown,line width=2,line cap=round]
\tikzstyle{nimstrikered}=[red,very thick]
\tikzstyle{nimstrikeblue}=[blue,very thick]
%
%
%
\title{Le jeu de nim : thème et variations}
\subtitle{Congrès « MATh en JEANS »}
\author[David Madore]{David A. Madore\\
{\footnotesize Télécom ParisTech}\\
\texttt{david.madore@enst.fr}}
\date{25 mars 2017}
\mode<presentation>{%
\beamertemplatenavigationsymbolsempty
\usenavigationsymbolstemplate{\vbox{\hbox{\footnotesize\hyperlinkslideprev{$\leftarrow$}\insertframenumber/\inserttotalframenumber\hyperlinkslidenext{$\rightarrow$}}}}
}
\setbeamercolor{myhighlight}{fg=black,bg=white!90!green}
\setbeamercolor{otherhighlight}{fg=black,bg=white!90!blue}
\begin{document}
\mode<article>{\maketitle}
%
\begin{frame}
\titlepage
{\footnotesize\center{\url{http://www.madore.org/~david/math/20170325-mathenjeans.pdf}}}
\center{\strut\llap{=\quad}\url{goo.gl/yd7Zvn}}
{\tiny
\immediate\write18{sh ./vc > vcline.tex}
\begin{center}
Git: \input{vcline.tex}
\end{center}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}
\end{frame}
%
\section*{Plan}
\begin{frame}
\frametitle{Plan}
\tableofcontents
\end{frame}
%
\section{Le jeu de nim}
\subsection{Le jeu lui-même}
\begin{frame}
\frametitle{Le jeu de nim}

\begin{columns}
\begin{column}{0.35\textwidth}
\begin{tikzpicture}
\draw[draw=none, use as bounding box](-3.5*\nimstickdist,-3*\nimstickline-\nimstickheight-0.1) rectangle (3.5*\nimstickdist,0.1);
\begin{scope}[nimstick]
\draw (0,0) -- (0,-\nimstickheight);
\draw (-\nimstickdist,-\nimstickline) -- (-\nimstickdist,-\nimstickline-\nimstickheight);
\draw (0,-\nimstickline) -- (0,-\nimstickline-\nimstickheight);
\draw (\nimstickdist,-\nimstickline) -- (\nimstickdist,-\nimstickline-\nimstickheight);
\draw (-2*\nimstickdist,-2*\nimstickline) -- (-2*\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (-\nimstickdist,-2*\nimstickline) -- (-\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (0,-2*\nimstickline) -- (0,-2*\nimstickline-\nimstickheight);
\draw (\nimstickdist,-2*\nimstickline) -- (\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (2*\nimstickdist,-2*\nimstickline) -- (2*\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (-3*\nimstickdist,-3*\nimstickline) -- (-3*\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (-2*\nimstickdist,-3*\nimstickline) -- (-2*\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (-\nimstickdist,-3*\nimstickline) -- (-\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (0,-3*\nimstickline) -- (0,-3*\nimstickline-\nimstickheight);
\draw (\nimstickdist,-3*\nimstickline) -- (\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (2*\nimstickdist,-3*\nimstickline) -- (2*\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (3*\nimstickdist,-3*\nimstickline) -- (3*\nimstickdist,-3*\nimstickline-\nimstickheight);
\end{scope}
\end{tikzpicture}
\end{column}
\begin{column}{0.71\textwidth}
\itempoint Des bâtonnets sont disposés en lignes.

\itempoint Seul importe le nombre de bâtonnets sur chaque ligne.

\itempoint Deux joueurs s'affrontent.

\itempoint Chacun à son tour retire autant de bâtonnets qu'il veut (au
moins $1$)

\itempoint ...mais d'\underline{une ligne seulement}.

\itempoint Le gagnant est celui qui prend le dernier\\\relax
(= celui qui ne peut pas jouer perd).

\itempoint Disposition initiale standard: $(1,3,5,7)$.
\end{column}
\end{columns}

\bigskip

{\footnotesize\itempoint Variante « misère » : celui qui prend le
  dernier bâtonnet perd.  Mathématiquement moins intéressante.
  (Apparaît dans \textit{L'année dernière à Marienbad} de
  Resnais.)\par}

\end{frame}
%
\begin{frame}
\frametitle{Exemple de partie}

\begin{tabular}{c|c|c|c}
\begin{tikzpicture}[scale=0.55]
\draw[draw=none, use as bounding box](-3.5*\nimstickdist,-3*\nimstickline-\nimstickheight-0.1) rectangle (3.5*\nimstickdist,0.1);
\begin{scope}[nimstick]
\draw (0,0) -- (0,-\nimstickheight);
\draw (-\nimstickdist,-\nimstickline) -- (-\nimstickdist,-\nimstickline-\nimstickheight);
\draw (0,-\nimstickline) -- (0,-\nimstickline-\nimstickheight);
\draw (\nimstickdist,-\nimstickline) -- (\nimstickdist,-\nimstickline-\nimstickheight);
\draw (-2*\nimstickdist,-2*\nimstickline) -- (-2*\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (-\nimstickdist,-2*\nimstickline) -- (-\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (0,-2*\nimstickline) -- (0,-2*\nimstickline-\nimstickheight);
\draw (\nimstickdist,-2*\nimstickline) -- (\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (2*\nimstickdist,-2*\nimstickline) -- (2*\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (-3*\nimstickdist,-3*\nimstickline) -- (-3*\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (-2*\nimstickdist,-3*\nimstickline) -- (-2*\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (-\nimstickdist,-3*\nimstickline) -- (-\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (0,-3*\nimstickline) -- (0,-3*\nimstickline-\nimstickheight);
\draw (\nimstickdist,-3*\nimstickline) -- (\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (2*\nimstickdist,-3*\nimstickline) -- (2*\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (3*\nimstickdist,-3*\nimstickline) -- (3*\nimstickdist,-3*\nimstickline-\nimstickheight);
\end{scope}
\draw[nimstrikeblue] (1.5*\nimstickdist,-3*\nimstickline) -- (3.5*\nimstickdist,-3*\nimstickline-\nimstickheight);
\end{tikzpicture}
&
\begin{tikzpicture}[scale=0.55]
\draw[draw=none, use as bounding box](-3.5*\nimstickdist,-3*\nimstickline-\nimstickheight-0.1) rectangle (3.5*\nimstickdist,0.1);
\begin{scope}[nimstick]
\draw (0,0) -- (0,-\nimstickheight);
\draw (-\nimstickdist,-\nimstickline) -- (-\nimstickdist,-\nimstickline-\nimstickheight);
\draw (0,-\nimstickline) -- (0,-\nimstickline-\nimstickheight);
\draw (\nimstickdist,-\nimstickline) -- (\nimstickdist,-\nimstickline-\nimstickheight);
\draw (-2*\nimstickdist,-2*\nimstickline) -- (-2*\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (-\nimstickdist,-2*\nimstickline) -- (-\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (0,-2*\nimstickline) -- (0,-2*\nimstickline-\nimstickheight);
\draw (\nimstickdist,-2*\nimstickline) -- (\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (2*\nimstickdist,-2*\nimstickline) -- (2*\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (-3*\nimstickdist,-3*\nimstickline) -- (-3*\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (-2*\nimstickdist,-3*\nimstickline) -- (-2*\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (-\nimstickdist,-3*\nimstickline) -- (-\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (0,-3*\nimstickline) -- (0,-3*\nimstickline-\nimstickheight);
\draw (\nimstickdist,-3*\nimstickline) -- (\nimstickdist,-3*\nimstickline-\nimstickheight);
\end{scope}
\draw[nimstrikered] (0.5*\nimstickdist,-2*\nimstickline) -- (2.5*\nimstickdist,-2*\nimstickline-\nimstickheight);
\end{tikzpicture}
&
\begin{tikzpicture}[scale=0.55]
\draw[draw=none, use as bounding box](-3.5*\nimstickdist,-3*\nimstickline-\nimstickheight-0.1) rectangle (3.5*\nimstickdist,0.1);
\begin{scope}[nimstick]
\draw (0,0) -- (0,-\nimstickheight);
\draw (-\nimstickdist,-\nimstickline) -- (-\nimstickdist,-\nimstickline-\nimstickheight);
\draw (0,-\nimstickline) -- (0,-\nimstickline-\nimstickheight);
\draw (\nimstickdist,-\nimstickline) -- (\nimstickdist,-\nimstickline-\nimstickheight);
\draw (-2*\nimstickdist,-2*\nimstickline) -- (-2*\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (-\nimstickdist,-2*\nimstickline) -- (-\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (0,-2*\nimstickline) -- (0,-2*\nimstickline-\nimstickheight);
\draw (-3*\nimstickdist,-3*\nimstickline) -- (-3*\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (-2*\nimstickdist,-3*\nimstickline) -- (-2*\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (-\nimstickdist,-3*\nimstickline) -- (-\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (0,-3*\nimstickline) -- (0,-3*\nimstickline-\nimstickheight);
\draw (\nimstickdist,-3*\nimstickline) -- (\nimstickdist,-3*\nimstickline-\nimstickheight);
\end{scope}
\draw[nimstrikeblue] (-2.5*\nimstickdist,-3*\nimstickline) -- (1.5*\nimstickdist,-3*\nimstickline-\nimstickheight);
\end{tikzpicture}
&
\begin{tikzpicture}[scale=0.55]
\draw[draw=none, use as bounding box](-3.5*\nimstickdist,-3*\nimstickline-\nimstickheight-0.1) rectangle (3.5*\nimstickdist,0.1);
\begin{scope}[nimstick]
\draw (0,0) -- (0,-\nimstickheight);
\draw (-\nimstickdist,-\nimstickline) -- (-\nimstickdist,-\nimstickline-\nimstickheight);
\draw (0,-\nimstickline) -- (0,-\nimstickline-\nimstickheight);
\draw (\nimstickdist,-\nimstickline) -- (\nimstickdist,-\nimstickline-\nimstickheight);
\draw (-2*\nimstickdist,-2*\nimstickline) -- (-2*\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (-\nimstickdist,-2*\nimstickline) -- (-\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (0,-2*\nimstickline) -- (0,-2*\nimstickline-\nimstickheight);
\draw (-3*\nimstickdist,-3*\nimstickline) -- (-3*\nimstickdist,-3*\nimstickline-\nimstickheight);
\end{scope}
\draw[nimstrikered] (-0.5*\nimstickdist,-0*\nimstickline) -- (0.5*\nimstickdist,-0*\nimstickline-\nimstickheight);
\end{tikzpicture}
\\\hline
\begin{tikzpicture}[scale=0.55]
\draw[draw=none, use as bounding box](-3.5*\nimstickdist,-3*\nimstickline-\nimstickheight-0.1) rectangle (3.5*\nimstickdist,0.1);
\begin{scope}[nimstick]
\draw (-\nimstickdist,-\nimstickline) -- (-\nimstickdist,-\nimstickline-\nimstickheight);
\draw (0,-\nimstickline) -- (0,-\nimstickline-\nimstickheight);
\draw (\nimstickdist,-\nimstickline) -- (\nimstickdist,-\nimstickline-\nimstickheight);
\draw (-2*\nimstickdist,-2*\nimstickline) -- (-2*\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (-\nimstickdist,-2*\nimstickline) -- (-\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (0,-2*\nimstickline) -- (0,-2*\nimstickline-\nimstickheight);
\draw (-3*\nimstickdist,-3*\nimstickline) -- (-3*\nimstickdist,-3*\nimstickline-\nimstickheight);
\end{scope}
\draw[nimstrikeblue] (-3.5*\nimstickdist,-3*\nimstickline) -- (-2.5*\nimstickdist,-3*\nimstickline-\nimstickheight);
\end{tikzpicture}
&
\begin{tikzpicture}[scale=0.55]
\draw[draw=none, use as bounding box](-3.5*\nimstickdist,-3*\nimstickline-\nimstickheight-0.1) rectangle (3.5*\nimstickdist,0.1);
\begin{scope}[nimstick]
\draw (-\nimstickdist,-\nimstickline) -- (-\nimstickdist,-\nimstickline-\nimstickheight);
\draw (0,-\nimstickline) -- (0,-\nimstickline-\nimstickheight);
\draw (\nimstickdist,-\nimstickline) -- (\nimstickdist,-\nimstickline-\nimstickheight);
\draw (-2*\nimstickdist,-2*\nimstickline) -- (-2*\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (-\nimstickdist,-2*\nimstickline) -- (-\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (0,-2*\nimstickline) -- (0,-2*\nimstickline-\nimstickheight);
\end{scope}
\draw[nimstrikered] (-2.5*\nimstickdist,-2*\nimstickline) -- (0.5*\nimstickdist,-2*\nimstickline-\nimstickheight);
\end{tikzpicture}
&
\begin{tikzpicture}[scale=0.55]
\draw[draw=none, use as bounding box](-3.5*\nimstickdist,-3*\nimstickline-\nimstickheight-0.1) rectangle (3.5*\nimstickdist,0.1);
\begin{scope}[nimstick]
\draw (-\nimstickdist,-\nimstickline) -- (-\nimstickdist,-\nimstickline-\nimstickheight);
\draw (0,-\nimstickline) -- (0,-\nimstickline-\nimstickheight);
\draw (\nimstickdist,-\nimstickline) -- (\nimstickdist,-\nimstickline-\nimstickheight);
\end{scope}
\draw[nimstrikeblue] (-1.5*\nimstickdist,-1*\nimstickline) -- (1.5*\nimstickdist,-1*\nimstickline-\nimstickheight);
\end{tikzpicture}
&
bleu gagne
\end{tabular}

\bigskip

$(1,3,5,7) \penalty0\mathrel{\textcolor{blue}{\rightsquigarrow}}\penalty0 (1,3,5,5)
\penalty0\mathrel{\textcolor{red}{\rightsquigarrow}}\penalty0 (1,3,3,5)
\penalty0\mathrel{\textcolor{blue}{\rightsquigarrow}}\penalty0 (1,3,3,1)
\penalty0\mathrel{\textcolor{red}{\rightsquigarrow}}\penalty0 (0,3,3,1)
\penalty0\mathrel{\textcolor{blue}{\rightsquigarrow}}\penalty0 (0,3,3,0)
\penalty0\mathrel{\textcolor{red}{\rightsquigarrow}}\penalty0 (0,3,0,0)
\penalty0\mathrel{\textcolor{blue}{\rightsquigarrow}}\penalty0 (0,0,0,0)$

\bigskip

Quel coup était « mauvais » ?

\end{frame}
%
\subsection{Stratégie gagnante et somme de nim}
\begin{frame}
\frametitle{Notion de stratégie gagnante}

\textbf{Cadre théorique :} la théorie « combinatoire » des jeux
\begin{itemize}
\item à deux joueurs,
\item à information parfaite (= sans hasard ni état caché),
\item terminant toujours en temps fini,
\item impartiaux (= les coups possibles sont les mêmes pour les deux
  joueurs).
\end{itemize}

\smallskip

\textbf{Stratégie :} fonction de l'état du jeu déterminant un coup à
jouer.  \textbf{Stratégie gagnante :} stratégie assurant de gagner à
coup sûr.

\smallskip

\textbf{Théorème} (E. Zermelo, 1913) : dans tout jeu combinatoire
comme ci-dessus, soit le premier joueur possède une stratégie gagnante
soit le second joueur en possède une.

\smallskip

{\footnotesize En général, on ne peut pas la décrire simplement.\par}

\medskip

$\Rightarrow$ Toute position [de nim] est gagnante pour le joueur qui va
jouer (\textcolor{blue}{N}ext) ou bien pour celui qui vient de jouer
(\textcolor{red}{P}revious).

\end{frame}
%
\begin{frame}
\frametitle{Positions évidentes au nim}

Dans une position $(n,n)$, le \textbf{second joueur} a une stratégie
gagnante, consistant à jouer en « \textbf{miroir} » :
\begin{center}
\begin{tikzpicture}
\draw[draw=none, use as bounding box](-4.5*\nimstickdist,-\nimstickline-\nimstickheight-0.1) rectangle (4.5*\nimstickdist,0.1);
\begin{scope}[nimstick]
\draw (-4*\nimstickdist,0) -- (-4*\nimstickdist,-\nimstickheight);
\draw (-3*\nimstickdist,0) -- (-3*\nimstickdist,-\nimstickheight);
\draw (-2*\nimstickdist,0) -- (-2*\nimstickdist,-\nimstickheight);
\draw (-\nimstickdist,0) -- (-\nimstickdist,-\nimstickheight);
\draw (0,0) -- (0,-\nimstickheight);
\draw (\nimstickdist,0) -- (\nimstickdist,-\nimstickheight);
\draw (2*\nimstickdist,0) -- (2*\nimstickdist,-\nimstickheight);
\draw (3*\nimstickdist,0) -- (3*\nimstickdist,-\nimstickheight);
\draw (4*\nimstickdist,0) -- (4*\nimstickdist,-\nimstickheight);
\draw (-4*\nimstickdist,-\nimstickline) -- (-4*\nimstickdist,-\nimstickline-\nimstickheight);
\draw (-3*\nimstickdist,-\nimstickline) -- (-3*\nimstickdist,-\nimstickline-\nimstickheight);
\draw (-2*\nimstickdist,-\nimstickline) -- (-2*\nimstickdist,-\nimstickline-\nimstickheight);
\draw (-\nimstickdist,-\nimstickline) -- (-\nimstickdist,-\nimstickline-\nimstickheight);
\draw (0,-\nimstickline) -- (0,-\nimstickline-\nimstickheight);
\draw (\nimstickdist,-\nimstickline) -- (\nimstickdist,-\nimstickline-\nimstickheight);
\draw (2*\nimstickdist,-\nimstickline) -- (2*\nimstickdist,-\nimstickline-\nimstickheight);
\draw (3*\nimstickdist,-\nimstickline) -- (3*\nimstickdist,-\nimstickline-\nimstickheight);
\draw (4*\nimstickdist,-\nimstickline) -- (4*\nimstickdist,-\nimstickline-\nimstickheight);
\end{scope}
\draw[nimstrikeblue] (1.5*\nimstickdist,0) -- (4.5*\nimstickdist,-\nimstickheight);
\draw[nimstrikered] (1.5*\nimstickdist,-\nimstickline) -- (4.5*\nimstickdist,-\nimstickline-\nimstickheight);
\draw[nimstrikeblue] (-0.5*\nimstickdist,-\nimstickline) -- (1.5*\nimstickdist,-\nimstickline-\nimstickheight);
\draw[nimstrikered] (-0.5*\nimstickdist,0) -- (1.5*\nimstickdist,-\nimstickheight);
\draw[nimstrikeblue] (-2.5*\nimstickdist,0) -- (-0.5*\nimstickdist,-\nimstickheight);
\draw[nimstrikered] (-2.5*\nimstickdist,-\nimstickline) -- (-0.5*\nimstickdist,-\nimstickline-\nimstickheight);
\draw[nimstrikeblue] (-4.5*\nimstickdist,0) -- (-2.5*\nimstickdist,-\nimstickheight);
\draw[nimstrikered] (-4.5*\nimstickdist,-\nimstickline) -- (-2.5*\nimstickdist,-\nimstickline-\nimstickheight);
\end{tikzpicture}
\end{center}
Quel que soit le coup $(n,n)
\mathrel{\textcolor{blue}{\rightsquigarrow}} (m,n)$ (ou $(n,n)
\mathrel{\textcolor{blue}{\rightsquigarrow}} (n,m)$), où $m<n$,
effectué par le premier joueur, le second réplique par
$\mathrel{\textcolor{red}{\rightsquigarrow}} (m,m)$.  Le second joueur
peut donc toujours jouer \textbf{donc il gagne} (car celui qui ne peut
plus jouer perd).

\bigskip

\begin{itemize}
\item Les $(n,n)$ sont des positions \textcolor{red}{P} (= gagnantes
  pour le second / précédent joueur).
\item Les $(n,m)$ où $m\neq n$ sont \textcolor{blue}{N}
  (= gagnantes pour le suivant).
\end{itemize}

\end{frame}
%
\begin{frame}
\frametitle{L'écriture binaire}

{\footnotesize L'écriture \textbf{binaire} des nombres fait des
  paquets de $2$, puis de $2\times 2$, etc., là où l'écriture
  \textbf{décimale} usuelle fait des paquets de $10$ (=dizaines), puis
  de $10\times 10$ (=centaines), etc. (ex. : $42 = \mathbf{4}\times
  10^1 + \mathbf{2} \times 10^0$).\par}

\smallskip

\textbf{Puissances de $2$ :} $2^0 = 1$,\quad $2^1 = 2$,\quad $2^2 =
4$,\quad $2^3 = 8$, etc.

\smallskip

\emph{Tout entier naturel s'écrit de façon unique comme somme de
  puissances de $2$ distinctes.}

\smallskip

{\footnotesize\textbf{Exemple :} $42 = 32 + 8 + 2 = 2^5 + 2^3 + 2^1 =
  \mathbf{1}\times 2^5 + \mathbf{0}\times 2^4 + \mathbf{1}\times 2^3 +
  \mathbf{0}\times 2^2 + \mathbf{1}\times 2^1 + \mathbf{0}\times
  2^0$\\On écrira simplement : $\mathtt{101010}_2$ (ou
  $\mathtt{00101010}_2$) pour $42$ en binaire.\par}

\bigskip

L'addition en binaire se calcule \emph{comme en décimal} avec une
table d'addition très simple !
\begin{center}
\begin{tabular}{r|rr}
$+$&$\mathtt{0}$&$\mathtt{1}$\\\hline
$\mathtt{0}$&$\mathtt{0}$&$\mathtt{1}$\\
$\mathtt{1}$&$\mathtt{1}$&$\mathtt{\textcolor{green!60!black}{1}0}$\\
\end{tabular}
\hskip0.2\textwidth
{\footnotesize
ex :
\begin{tabular}{rcr}
$\mathtt{101010}$&=&$42$\\
$\strut+\mathtt{100110}$&&$\strut+38$\\\hline
$\mathtt{1010000}$&=&$80$
\end{tabular}
}
\end{center}
Le $\mathtt{\textcolor{green!60!black}{1}}$ de
$\mathtt{1}+\mathtt{1}=\mathtt{\textcolor{green!60!black}{1}0}$ est
une \textbf{retenue} sur le chiffre à gauche.

\end{frame}
%
\begin{frame}
\frametitle{La somme de nim (« ou exclusif »)}

Une opération encore plus simple : \textbf{l'addition binaire sans
  retenue} :
\begin{center}
\begin{tabular}{r|rr}
$\oplus$&$\mathtt{0}$&$\mathtt{1}$\\\hline
$\mathtt{0}$&$\mathtt{0}$&$\mathtt{1}$\\
$\mathtt{1}$&$\mathtt{1}$&$\mathtt{0}$\\
\end{tabular}
\hskip0.2\textwidth
{\footnotesize
ex :
\begin{tabular}{rcr}
$\mathtt{101010}$&=&$42$\\
$\strut\oplus\mathtt{100110}$&&$\strut\oplus 38$\\\hline
$\mathtt{001100}$&=&$12$
\end{tabular}
}
\end{center}

\smallskip

On l'appelle \textbf{somme de nim} ou \textbf{ou exclusif} (en
informatique : XOR, souvent notée \texttt{\char`\^}).

\bigskip

Quelques propriétés :
\begin{itemize}
\item commutative : $a\oplus b = b\oplus a$ ;
\item associative : $a\oplus (b\oplus c) = (a\oplus b)\oplus c =: a\oplus b\oplus c$ ;
\item $0$ est « neutre » : $a\oplus 0 = 0\oplus a = a$ ;
\item\textbf{de $2$-torsion} : $a\oplus a = 0$.
\end{itemize}

\smallskip

\itempoint Retenir : $a\oplus b = c$ équivaut à $a \oplus b \oplus c =
0$ ou bien $a\oplus c = b$.

\end{frame}
%
\begin{frame}
\frametitle{La fonction de Grundy du nim}

La \textbf{valeur de Grundy} d'une position au nim est la somme de nim
des nombres de bâtonnets des différentes lignes.

\begin{center}
\begin{tikzpicture}[scale=0.75]
\begin{scope}[nimstick]
\draw (0,0) -- (0,-\nimstickheight);
\draw (-\nimstickdist,-\nimstickline) -- (-\nimstickdist,-\nimstickline-\nimstickheight);
\draw (0,-\nimstickline) -- (0,-\nimstickline-\nimstickheight);
\draw (\nimstickdist,-\nimstickline) -- (\nimstickdist,-\nimstickline-\nimstickheight);
\draw (-2*\nimstickdist,-2*\nimstickline) -- (-2*\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (-\nimstickdist,-2*\nimstickline) -- (-\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (0,-2*\nimstickline) -- (0,-2*\nimstickline-\nimstickheight);
\draw (\nimstickdist,-2*\nimstickline) -- (\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (2*\nimstickdist,-2*\nimstickline) -- (2*\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (-3*\nimstickdist,-3*\nimstickline) -- (-3*\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (-2*\nimstickdist,-3*\nimstickline) -- (-2*\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (-\nimstickdist,-3*\nimstickline) -- (-\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (0,-3*\nimstickline) -- (0,-3*\nimstickline-\nimstickheight);
\draw (\nimstickdist,-3*\nimstickline) -- (\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (2*\nimstickdist,-3*\nimstickline) -- (2*\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (3*\nimstickdist,-3*\nimstickline) -- (3*\nimstickdist,-3*\nimstickline-\nimstickheight);
\end{scope}
\node[anchor=east] at (7*\nimstickdist,-0.5*\nimstickheight) {$\mathtt{001}$};
\node[anchor=east] at (7*\nimstickdist,-\nimstickline-0.5*\nimstickheight) {$\strut\oplus\mathtt{011}$};
\node[anchor=east] at (7*\nimstickdist,-2*\nimstickline-0.5*\nimstickheight) {$\strut\oplus\mathtt{101}$};
\node[anchor=east] at (7*\nimstickdist,-3*\nimstickline-0.5*\nimstickheight) {$\strut\oplus\mathtt{111}$};
\node[anchor=east] at (7*\nimstickdist,-4.25*\nimstickline) {$\strut=\mathtt{000}$};
\node[anchor=west] at (7*\nimstickdist+1,-0.5*\nimstickheight) {\footnotesize $1 = \mathbf{0}\cdot 2^2 + \mathbf{0}\cdot 2^1 + \mathbf{1}\cdot 2^0$};
\node[anchor=west] at (7*\nimstickdist+1,-\nimstickline-0.5*\nimstickheight) {\footnotesize $3 = \mathbf{0}\cdot 2^2 + \mathbf{1}\cdot 2^1 + \mathbf{1}\cdot 2^0$};
\node[anchor=west] at (7*\nimstickdist+1,-2*\nimstickline-0.5*\nimstickheight) {\footnotesize $5 = \mathbf{1}\cdot 2^2 + \mathbf{0}\cdot 2^1 + \mathbf{1}\cdot 2^0$};
\node[anchor=west] at (7*\nimstickdist+1,-3*\nimstickline-0.5*\nimstickheight) {\footnotesize $7 = \mathbf{1}\cdot 2^2 + \mathbf{1}\cdot 2^1 + \mathbf{1}\cdot 2^0$};
\node[anchor=west] at (7*\nimstickdist+0.5,-4.25*\nimstickline) {$\leftarrow$ valeur de Grundy};
\end{tikzpicture}
\end{center}

\vskip-\baselineskip

{\footnotesize (Mettre un $\mathtt{0}$ quand il y a un nombre pair de
  $\mathtt{1}$ dans cette colonne de l'écriture binaire et un
  $\mathtt{1}$ quand il y a un nombre impair de $\mathtt{1}$.)\par}

\medskip

On va voir que pour gagner il s'agit de \alert{jouer pour annuler la
  valeur de Grundy}.  C'est la stratégie gagnante.

\end{frame}
%
\begin{frame}
\frametitle{La stratégie gagnante au nim}

Il faut voir deux choses :
\begin{itemize}
\item depuis une position où la valeur de Grundy est nulle,
  \alert{tous les coups} vont la rendre non-nulle,
\item depuis une position où la valeur de Grundy est non-nulle,
  \alert{il y a au moins un} coup (« gagnant ») qui la rend nulle.
\end{itemize}

\medskip

Alors, si je joue pour annuler Grundy, mon adversaire doit la rendre
non-nulle, je peux l'annuler, il doit la rendre non-nulle, etc.  Je
peux toujours jouer \textbf{donc je gagne} (car celui qui ne peut plus
jouer perd).

\medskip

$\Rightarrow$ Une position de Grundy nulle est gagnante pour le joueur
qui vient de jouer (\textcolor{red}{P}revious) ; sinon, pour le joueur
qui doit jouer (\textcolor{blue}{N}ext).

\medskip

{\footnotesize La position initiale $(1,3,5,7)$ est \textcolor{red}{P}
  car $\mathtt{001} \oplus \mathtt{011} \oplus \mathtt{101} \oplus
  \mathtt{111} = \mathtt{000}$ : le \underline{second} joueur a une
  stratégie gagnante.\par}

\end{frame}
%
\subsection{Démonstration}
\begin{frame}
\frametitle{Démonstration de la stratégie (1)}

\begin{beamercolorbox}[sep=.5em]{myhighlight}
Depuis une position où la valeur de Grundy est nulle, \alert{tous
  les coups} vont la rendre non-nulle.
\end{beamercolorbox}

\itempoint Soit $(n_1,\ldots,n_\ell)$ une position de nim (où $n_i$
= nombre de bâtonnets sur la ligne $i$).

\itempoint Supposons que sa valeur de Grundy $n_1\oplus \cdots \oplus
n_\ell$ vaut $0$.

\itempoint On fait un coup sur la ligne $j$ (où $1\leq j\leq\ell$) :
ceci remplace $n_j$ par $n' < n_j$.

\itempoint La somme de nim $m$ de tous les $n_i$ \underline{sauf}
$n_j$ vaut : $m = n_j$.

En effet, $m \oplus n_j = n_1\oplus \cdots \oplus n_\ell = 0$,\\...or
$m \oplus n_j = 0$ équivaut à $m = n_j$.

\itempoint La valeur de Grundy de la nouvelle position vaut donc : $m
\oplus n' = n_j \oplus n'$.

\itempoint Mais comme $n' \neq n_j$, on a $n_j \oplus n' \neq 0$,
cqfd.

\bigskip

\textbf{Bref :} changer une valeur dans une somme de nim change
forcément le résultat (qui ici était $0$).

\end{frame}
%
\begin{frame}
\frametitle{Démonstration de la stratégie (2)}

\begin{beamercolorbox}[sep=.5em]{myhighlight}
Depuis une position où la valeur de Grundy est non-nulle, \alert{il y
  a au moins un} coup qui la rend nulle.
\end{beamercolorbox}

\itempoint Soit $(n_1,\ldots,n_\ell)$ une position de nim où cette
fois $n_1\oplus \cdots \oplus n_\ell =: k \neq 0$.

\itempoint Comme avant, on remplace $n_j$ par $n' < n_j$.

\itempoint La somme de nim $m$ de tous les $n_i$ \underline{sauf}
$n_j$ vaut : $m = n_j \oplus k$.

En effet, $m \oplus n_j = k$ équivaut à $m = n_j \oplus k$.

\itempoint La valeur de Grundy de la nouvelle position vaut donc : $m
\oplus n' = n_j \oplus n' \oplus k$.

\itempoint On cherche à avoir $n_j \oplus n' \oplus k = 0$, ce qui
équivaut à : $n' = n_j \oplus k$.

\bigskip

\textbf{Bref :} ceci nous donne $n'$ mais il \alert{reste à assurer}
$n' < n_j$ en choisissant $j$.

\end{frame}
%
\begin{frame}
\frametitle{Démonstration de la stratégie (3)}

Reste seulement à prouver le lemme :

\begin{beamercolorbox}[sep=.5em]{myhighlight}
Si $k = n_1\oplus \cdots \oplus n_\ell$ n'est pas $0$, alors il existe
(au moins) un $j$ tel que $n_j \oplus k < n_j$.
\end{beamercolorbox}

\itempoint Soit $2^v$ la plus grande puissance de $2$ qui soit $\leq
k$ : i.e., $v$ est l'indice du $\mathtt{1}$ le plus à gauche dans
l'écriture binaire de $k$.

\itempoint Puisque le $v$-ième chiffre binaire de $k$
vaut $\mathtt{1}$, il y a un nombre impair de $n_i$ qui ont cette
prop\rlap{.}\textsuperscript{té}.  Soit $n_j$ l'un d'eux.

\itempoint Alors $n_j \oplus k < n_j$ car le $v$-ième chiffre binaire
passe de $\mathtt{1}$ (dans $n_j$) à $\mathtt{0}$ (dans $n_j \oplus
k$) et tous ceux à gauche sont inchangés.

\bigskip

\textbf{Bref :} pour trouver le coup gagnant, on XORe la valeur de
Grundy $k$ au nombre $n_j$ de bâtonnets d'une ligne qui a un
$\mathtt{1}$ dans la colonne du $\mathtt{1}$ le plus à gauche de $k$
en binaire.

\end{frame}
%
\begin{frame}
\frametitle{Exemple (calcul d'un coup gagnant)}

\begin{center}
\begin{tikzpicture}[scale=0.75]
\begin{scope}[nimstick]
\draw (0,0) -- (0,-\nimstickheight);
\draw (-\nimstickdist,-\nimstickline) -- (-\nimstickdist,-\nimstickline-\nimstickheight);
\draw (0,-\nimstickline) -- (0,-\nimstickline-\nimstickheight);
\draw (\nimstickdist,-\nimstickline) -- (\nimstickdist,-\nimstickline-\nimstickheight);
\draw (-2*\nimstickdist,-2*\nimstickline) -- (-2*\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (-\nimstickdist,-2*\nimstickline) -- (-\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (0,-2*\nimstickline) -- (0,-2*\nimstickline-\nimstickheight);
\draw (\nimstickdist,-2*\nimstickline) -- (\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (2*\nimstickdist,-2*\nimstickline) -- (2*\nimstickdist,-2*\nimstickline-\nimstickheight);
\draw (-3*\nimstickdist,-3*\nimstickline) -- (-3*\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (-2*\nimstickdist,-3*\nimstickline) -- (-2*\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (-\nimstickdist,-3*\nimstickline) -- (-\nimstickdist,-3*\nimstickline-\nimstickheight);
\draw (0,-3*\nimstickline) -- (0,-3*\nimstickline-\nimstickheight);
\draw (\nimstickdist,-3*\nimstickline) -- (\nimstickdist,-3*\nimstickline-\nimstickheight);
\end{scope}
\node[anchor=east] at (7*\nimstickdist,-0.5*\nimstickheight) {$\mathtt{001}$};
\node[anchor=east] at (7*\nimstickdist,-\nimstickline-0.5*\nimstickheight) {$\strut\oplus\mathtt{011}$};
\node[anchor=east] at (7*\nimstickdist,-2*\nimstickline-0.5*\nimstickheight) {$\strut\oplus\mathtt{101}$};
\node[anchor=east] at (7*\nimstickdist,-3*\nimstickline-0.5*\nimstickheight) {$\strut\oplus\mathtt{101}$};
\node[anchor=east] at (7*\nimstickdist,-4.25*\nimstickline) {$\strut=\mathtt{010}$};
\end{tikzpicture}
\end{center}

\vskip-\baselineskip

{\footnotesize Ici $n_1 = 1 = \mathtt{001}_2$ et $n_2 = 3 =
  \mathtt{011}_2$ et $n_3 = 5 = \mathtt{101}_2$ et $n_4 = 5 =
  \mathtt{101}_2$.\par}

\itempoint Grundy $k = \mathtt{001} \oplus \mathtt{011} \oplus
\mathtt{101} \oplus \mathtt{101} = \mathtt{010}$ (soit $2$).

\itempoint Le $\mathtt{1}$ le plus à gauche de $k$ est pour $v=1$
(soit pour $2^1$).

\itempoint $n_2 = \mathtt{011}$ a un $\mathtt{1}$ à cet endroit.

\itempoint On joue sur la ligne $j=2$ et on passe de $n_2 =
\mathtt{011} = 3$ bâtonnets à $n' = \mathtt{011}\oplus\mathtt{010} =
\mathtt{001} = 1$ (on a bien $1<3$ : le coup est possible).

\end{frame}
%
\begin{frame}
\frametitle{Remarques diverses}

{\footnotesize Rappel : \textcolor{red}{P}-position = valeur de Grundy
  nulle = gagnante pour le joueur qui vient de
  jouer.\par}

\medskip

\itempoint Pour éviter les calculs en binaire, retenir les
\textcolor{red}{P}-positions : $(n,n)$, $(1,1,n,n)$ et $(1,2m,2m+1)$
(notamment $(1,2,3)$).

\medskip

\itempoint Le nombre total de bâtonnets dans une
\textcolor{red}{P}-position est toujours pair (exercice !) : on retire
donc un nombre de même parité que l'adversaire.

\medskip

\itempoint Si on doit jouer depuis une \textcolor{red}{P}-position,
pour perdre le plus lentement possible, retirer $1$ bâtonnet depuis
une ligne ayant un $\mathtt{1}$ le plus à \emph{droite} possible en
binaire.

\medskip

\itempoint Variante « misère » du nim (= qui-perd-gagne) : les
\textcolor{red}{P}-positions sont les mêmes qu'à la variante normale
sauf si toutes les lignes ont $\leq 1$ bâtonnet, auquel cas on
inverse.

\end{frame}
%
\section{...thème...}
\begin{frame}
\frametitle{Un jeu de nim déguisé}

\begin{center}
\begin{tikzpicture}
\draw[step=\squaresize] (0,0) grid (8*\squaresize,8*\squaresize);
\draw[fill=blue] (0.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw[fill=blue] (1.5*\squaresize,1.5*\squaresize) circle [radius=\coinradius];
\draw[fill=blue] (2.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw[fill=blue] (3.5*\squaresize,1.5*\squaresize) circle [radius=\coinradius];
\draw[fill=blue] (4.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw[fill=blue] (5.5*\squaresize,2.5*\squaresize) circle [radius=\coinradius];
\draw[fill=blue] (6.5*\squaresize,4.5*\squaresize) circle [radius=\coinradius];
\draw[fill=blue] (7.5*\squaresize,2.5*\squaresize) circle [radius=\coinradius];
\draw[fill=red] (0.5*\squaresize,7.5*\squaresize) circle [radius=\coinradius];
\draw[fill=red] (1.5*\squaresize,7.5*\squaresize) circle [radius=\coinradius];
\draw[fill=red] (2.5*\squaresize,6.5*\squaresize) circle [radius=\coinradius];
\draw[fill=red] (3.5*\squaresize,6.5*\squaresize) circle [radius=\coinradius];
\draw[fill=red] (4.5*\squaresize,5.5*\squaresize) circle [radius=\coinradius];
\draw[fill=red] (5.5*\squaresize,7.5*\squaresize) circle [radius=\coinradius];
\draw[fill=red] (6.5*\squaresize,6.5*\squaresize) circle [radius=\coinradius];
\draw[fill=red] (7.5*\squaresize,6.5*\squaresize) circle [radius=\coinradius];
\end{tikzpicture}
\end{center}

\itempoint Un joueur avance les pions bleus vers le haut, l'autre les
rouges vers le bas.

\itempoint Un pion peut avancer d'autant de cases qu'il veut, en
restant sur la même colonne ; pas de prise ni de saut.

\itempoint Celui qui ne peut plus jouer a perdu.

\medskip

\itempoint Seul importe l'\textbf{espace entre deux pions} sur la même
colonne, consommé sous forme de \textbf{jeu de nim déguisé}.

\end{frame}
%
\begin{frame}
\frametitle{Jeux plus généraux ?}

{\footnotesize\textbf{Jeux :} à deux joueurs, à information parfaite,
  terminant toujours en temps fini, impartiaux.\par}

Peuvent se voir théoriquement comme un \textbf{graphe orienté} (sans
cycle) : celui des \textbf{positions possibles} du jeu.

\begin{center}
\begin{tikzpicture}[>=stealth,line join=bevel,scale=0.5]
\node (q1) at (90bp,56bp) [draw,circle] {$\phantom{1}$};
\node (q0) at (18bp,79bp) [draw,circle] {$\phantom{0}$};
\node (q3) at (234bp,56bp) [draw,circle] {$\phantom{0}$};
\node (q2) at (162bp,102bp) [draw,circle] {$\phantom{2}$};
\node (q5) at (378bp,64bp) [draw,circle] {$\phantom{1}$};
\node (q4) at (306bp,18bp) [draw,circle] {$\phantom{2}$};
\node (q6) at (450bp,41bp) [draw,circle] {$\phantom{0}$};
\draw [->] (-25bp,79bp) -- (q0);
  \draw [->] (q2) -- (q3);
  \draw [->] (q0) -- (q2);
  \draw [->] (q3) -- (q4);
  \draw [->] (q4) -- (q6);
  \draw [->] (q4) -- (q5);
  \draw [->] (q1) -- (q3);
  \draw [->] (q5) -- (q6);
  \draw [->] (q3) -- (q5);
  \draw [->] (q0) -- (q1);
  \draw [->] (q2) -- (q5);
  \draw [->] (q1) -- (q2);
\end{tikzpicture}
\end{center}

\itempoint On part d'un nœud du graphe,

\itempoint chaque joueur choisit une arête sortante,

\itempoint celui qui ne peut pas jouer a perdu.

\bigskip

Peut-on encore définir une fonction de Grundy ?

\end{frame}
%
\begin{frame}
\frametitle{Fonction de Grundy générale}

Valeur de Grundy d'une position = \underline{plus petit} entier
naturel qui \underline{n'est pas} la valeur de Grundy d'une position
atteignable en un coup à partir de là.

{\footnotesize\textbf{Théorème} (« induction bien-fondée ») :
  cette définition a bien un sens.\par}

\begin{center}
\begin{tikzpicture}[>=stealth,line join=bevel,scale=0.5]
\node (q1) at (90bp,56bp) [draw,circle] {$1$};
\node (q0) at (18bp,79bp) [draw,circle] {$\textcolor{red}{0}$};
\node (q3) at (234bp,56bp) [draw,circle] {$\textcolor{red}{0}$};
\node (q2) at (162bp,102bp) [draw,circle] {$2$};
\node (q5) at (378bp,64bp) [draw,circle] {$1$};
\node (q4) at (306bp,18bp) [draw,circle] {$2$};
\node (q6) at (450bp,41bp) [draw,circle] {$\textcolor{red}{0}$};
\draw [->] (-25bp,79bp) -- (q0);
  \draw [->] (q2) -- (q3);
  \draw [->] (q0) -- (q2);
  \draw [->] (q3) -- (q4);
  \draw [->] (q4) -- (q6);
  \draw [->] (q4) -- (q5);
  \draw [->] (q1) -- (q3);
  \draw [->] (q5) -- (q6);
  \draw [->] (q3) -- (q5);
  \draw [->] (q0) -- (q1);
  \draw [->] (q2) -- (q5);
  \draw [->] (q1) -- (q2);
\end{tikzpicture}
\end{center}

\textbf{Stratégie universelle :} jouer vers une position de Grundy
nulle (= \textcolor{red}{P}-position).

\bigskip

Malheureusement, on sait très rarement calculer explicitement la
fonction de Grundy !

{\footnotesize Pour le \textbf{jeu de nim}, on peut montrer que
  c'est bien celle qu'on a décrite.\par}

\end{frame}
%
\begin{frame}
\frametitle{Retour sur la somme de nim}

\begin{beamercolorbox}[sep=.5em]{otherhighlight}
$a\oplus b$ est le \underline{plus petit} entier naturel qui
  \underline{n'est pas} de la forme $a'\oplus b$ pour $a'<a$ ni
  $a\oplus b'$ pour $b'<b$.
\end{beamercolorbox}

Symboliquement,
\vskip-2ex
\[
\begin{aligned}
a\oplus b = \mex(&\{a'\oplus b : 0\leq a'<a\}\\
\strut\cup\strut&\{a\oplus b' : 0\leq b'<b\})
\end{aligned}
\]
où $\mex S$ (« Minimum EXclu ») = plus petit qui n'est pas dans $S$.

{\footnotesize Exemple : $3\oplus 1 = \mex\{0\oplus 1, 1\oplus 1,
  2\oplus 1, 3\oplus 0\} = \mex\{1,0,3,3\} = 2$\par}

\bigskip

Définition « inductive » (= « récursive »), très inefficace à
calculer, mais sans référence au binaire !

\end{frame}
%
\begin{frame}
\frametitle{Encore un déguisement du nim}

\begin{center}
\begin{tikzpicture}
\draw[step=\squaresize] (0,0) grid (10*\squaresize,\squaresize);
\draw[fill] (0.5*\squaresize,0.5*\squaresize) circle [radius=0.15*\squaresize];
\draw[fill] (2.3*\squaresize,0.3*\squaresize) circle [radius=0.15*\squaresize];
\draw[fill] (2.7*\squaresize,0.7*\squaresize) circle [radius=0.15*\squaresize];
\draw[fill] (3.5*\squaresize,0.5*\squaresize) circle [radius=0.15*\squaresize];
\draw[fill] (5.5*\squaresize,0.5*\squaresize) circle [radius=0.15*\squaresize];
\draw[fill] (8.5*\squaresize,0.5*\squaresize) circle [radius=0.15*\squaresize];
\draw[fill] (9.5*\squaresize,0.75*\squaresize) circle [radius=0.15*\squaresize];
\draw[fill] (9.25*\squaresize,0.25*\squaresize) circle [radius=0.15*\squaresize];
\draw[fill] (9.75*\squaresize,0.25*\squaresize) circle [radius=0.15*\squaresize];
\node[anchor=north] at (0.5*\squaresize,0) {$1$};
\node[anchor=north] at (1.5*\squaresize,0) {$2$};
\node[anchor=north] at (2.5*\squaresize,0) {$3$};
\node[anchor=north] at (3.5*\squaresize,0) {$4$};
\node[anchor=north] at (4.5*\squaresize,0) {$5$};
\node[anchor=north] at (5.5*\squaresize,0) {$6$};
\node[anchor=north] at (6.5*\squaresize,0) {$7$};
\node[anchor=north] at (7.5*\squaresize,0) {$8$};
\node[anchor=north] at (8.5*\squaresize,0) {$9$};
\node[anchor=north] at (9.5*\squaresize,0) {$10$};
\end{tikzpicture}
\end{center}

\itempoint Des jetons sur des cases, pas de limite sur le nombre de
jetons par case.

\itempoint Chaque joueur à son tour doit :
\begin{itemize}
\item retirer un jeton, \emph{ou bien}
\item déplacer un jeton vers une case plus à gauche.
\end{itemize}

\itempoint Celui qui retire le dernier jeton gagne (= celui qui ne
peut pas jouer perd).

\bigskip

\itempoint Équivalent au jeu de nim avec autant de lignes que de
jetons, la position des jetons indique le nombre de bâtonnets.

\medskip

{\footnotesize\itempoint Si on peut seulement déplacer les jetons, pas
  les retirer, idem en comptant les cases à partir de $0$
  (= case-défausse).\par}

\end{frame}
%
\section{...et variations !}
\subsection{Retournements de pièces}
\begin{frame}
\frametitle{Jeux de retournements de pièces}

\begin{center}
\begin{tikzpicture}
\draw[step=\squaresize] (0,0) grid (10*\squaresize,\squaresize);
\draw[fill] (0.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (7.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (8.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (9.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\end{tikzpicture}
\end{center}

\itempoint Chaque case porte une pièce qui peut présenter soit le côté
noir (=face, =$1$), soit le côté blanc (=pile, =$0$).

\itempoint « Retourner » une pièce = échanger noir et blanc.

\itempoint Chaque joueur à son tour va retourner certaines pièces,
selon des règles variables.

\itempoint \underline{Règle commune} à tous ces jeux : la pièce
retournée \emph{la plus à droite} doit passer de noir à blanc
($1$ à $0$).

\itempoint Celui qui ne peut pas jouer perd.

\bigskip

\itempoint Le jeu termine en temps fini par la règle commune.

(Le nombre binaire représenté par les $0$ et $1$ lus de droite à
gauche décroît strictement à chaque coup.)

\end{frame}
%
\begin{frame}
\frametitle{Retournement de $\leq 2$ pièces}

{\footnotesize Le jeu « retourner $1$ pièce » est sans intérêt.\par}

\bigskip

\itempoint « Retourner $\leq 2$ pièces » + règle commune

= retourner $1$ pièce de noir à blanc + optionnellement $1$ autre
située plus à gauche.

\begin{center}
\begin{tikzpicture}
\draw[step=\squaresize] (0,0) grid (10*\squaresize,\squaresize);
\draw[fill] (0.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (7.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (8.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (9.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\node[anchor=north] at (0.5*\squaresize,0) {$1$};
\node[anchor=north] at (1.5*\squaresize,0) {$2$};
\node[anchor=north] at (2.5*\squaresize,0) {$3$};
\node[anchor=north] at (3.5*\squaresize,0) {$4$};
\node[anchor=north] at (4.5*\squaresize,0) {$5$};
\node[anchor=north] at (5.5*\squaresize,0) {$6$};
\node[anchor=north] at (6.5*\squaresize,0) {$7$};
\node[anchor=north] at (7.5*\squaresize,0) {$8$};
\node[anchor=north] at (8.5*\squaresize,0) {$9$};
\node[anchor=north] at (9.5*\squaresize,0) {$10$};
\end{tikzpicture}
\end{center}

\vskip-\baselineskip

Revient encore au jeu de nim !

\begin{itemize}
\item Une ligne de $n$ bâtonnets si pièce $n$ est noire.
\item Retourner la seule pièce $n$ = retirer toute la ligne.
\item Retourner la pièce $n$ et la pièce $n'<n$ = diminuer la ligne de
  $n$ à $n'$ bâtonnets.
\item Se rappeler que deux lignes de $m$ « s'annulent ».
\end{itemize}

\bigskip

{\footnotesize\itempoint « Retourner exactement $2$ pièces » : pareil
  en numérotant de $0$.\par}

\end{frame}
%
\begin{frame}
\frametitle{Le code de Hamming binaire}

\itempoint \textcolor{red}{P}-positions (= Grundy $0$) au
retour\rlap{.}\textsuperscript{t} de $\leq 2$ pièces $\cong$nim :

\vskip-\baselineskip

\begin{columns}
\begin{column}{0.3\textwidth}
\begin{center}
\begin{tikzpicture}[scale=0.7]
\node[anchor=south] at (0.5*\squaresize,0) {\tiny$1$};
\node[anchor=south] at (1.5*\squaresize,0) {\tiny$2$};
\node[anchor=south] at (2.5*\squaresize,0) {\tiny$3$};
\node[anchor=south] at (3.5*\squaresize,0) {\tiny$4$};
\node[anchor=south] at (4.5*\squaresize,0) {\tiny$5$};
\node[anchor=south] at (5.5*\squaresize,0) {\tiny$6$};
\node[anchor=south] at (6.5*\squaresize,0) {\tiny$7$};
\begin{scope}
\draw[step=\squaresize] (0,-\squaresize) grid (7*\squaresize,0);
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-1.2*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (7*\squaresize,0);
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-2.4*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (7*\squaresize,0);
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-3.6*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (7*\squaresize,0);
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-4.8*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (7*\squaresize,0);
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\end{tikzpicture}
\end{center}
\end{column}
\begin{column}{0.3\textwidth}
\begin{center}
\begin{tikzpicture}[scale=0.7]
\node[anchor=south] at (0.5*\squaresize,0) {\tiny$1$};
\node[anchor=south] at (1.5*\squaresize,0) {\tiny$2$};
\node[anchor=south] at (2.5*\squaresize,0) {\tiny$3$};
\node[anchor=south] at (3.5*\squaresize,0) {\tiny$4$};
\node[anchor=south] at (4.5*\squaresize,0) {\tiny$5$};
\node[anchor=south] at (5.5*\squaresize,0) {\tiny$6$};
\node[anchor=south] at (6.5*\squaresize,0) {\tiny$7$};
\begin{scope}
\draw[step=\squaresize] (0,-\squaresize) grid (7*\squaresize,0);
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-1.2*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (7*\squaresize,0);
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-2.4*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (7*\squaresize,0);
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-3.6*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (7*\squaresize,0);
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-4.8*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (7*\squaresize,0);
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\end{tikzpicture}
\end{center}
\end{column}
\begin{column}{0.3\textwidth}
\begin{center}
\begin{tikzpicture}[scale=0.7]
\node[anchor=south] at (0.5*\squaresize,0) {\tiny$1$};
\node[anchor=south] at (1.5*\squaresize,0) {\tiny$2$};
\node[anchor=south] at (2.5*\squaresize,0) {\tiny$3$};
\node[anchor=south] at (3.5*\squaresize,0) {\tiny$4$};
\node[anchor=south] at (4.5*\squaresize,0) {\tiny$5$};
\node[anchor=south] at (5.5*\squaresize,0) {\tiny$6$};
\node[anchor=south] at (6.5*\squaresize,0) {\tiny$7$};
\begin{scope}
\draw[step=\squaresize] (0,-\squaresize) grid (7*\squaresize,0);
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-1.2*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (7*\squaresize,0);
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-2.4*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (7*\squaresize,0);
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-3.6*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (7*\squaresize,0);
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-4.8*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (7*\squaresize,0);
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\end{tikzpicture}
\end{center}
\end{column}
\end{columns}

\medskip

\itempoint On ne peut pas passer d'une \textcolor{red}{P}-position à
une autre en tournant $1$ ni même $2$ pièces.

\itempoint Si on tourne $1$ pièce dans une
\textcolor{red}{P}-position, on peut retrouver laquelle grâce à
Grundy.

\bigskip

\itempoint Les \textcolor{red}{P}-positions fournissent un
\textbf{code correcteur} qui corrige $1$ erreur ou détecte $2$
erreurs, appelé \textbf{code de Hamming binaire}.

{\footnotesize\itempoint En longueur $2^v-1$ (ci-dessus $7$), il fait
  passer $2^v - v - 1$ bits d'information par « mot » (ci-dessus $4$ :
  il y a $16$ \textcolor{red}{P}-positions).\par}

\end{frame}
%
\begin{frame}
\frametitle{Retournement de $\leq r$ pièces}

\itempoint Règle du jeu : retourner $\leq r$ pièces + la règle commune
(la plus à droite passe de noir à blanc).

\itempoint Valeur de Grundy = somme de nim des $f_r(n)$ sur les
numéros $n$ des pièces noires (numérotées à partir de $1$).

{\footnotesize\itempoint Si $r=2$ (retourner $\leq 2$ pièces), on
  a $f_2(n) = n$ (jeu de nim déguisé).\par}

\itempoint Que vaut $f_r(n)$ en général ?

\begin{tabular}{r|rrrrrrrrrr}\hline
$n$&$1$&$2$&$3$&$4$&$5$&$6$&$7$&$8$&$9$&$10$\\\hline
$f_1(n)$&$1$&$1$&$1$&$1$&$1$&$1$&$1$&$1$&$1$&$1$\\\hline
$f_2(n)$&$1$&$2$&$3$&$4$&$5$&$6$&$7$&$8$&$9$&$10$\\\hline
$f_3(n)$&$1$&$2$&$4$&$7$&$8$&$11$&$13$&$14$&$16$&$19$\\\hline
$f_4(n)$&$1$&$2$&$4$&$8$&$15$&$16$&$32$&$51$&$64$&$85$\\\hline
$f_5(n)$&$1$&$2$&$4$&$8$&$16$&$31$&$32$&$64$&$103$&$128$\\\hline
$f_6(n)$&$1$&$2$&$4$&$8$&$16$&$32$&$63$&$64$&$128$&$256$\\\hline
$f_7(n)$&$1$&$2$&$4$&$8$&$16$&$32$&$64$&$127$&$128$&$256$\\\hline
$f_8(n)$&$1$&$2$&$4$&$8$&$16$&$32$&$64$&$128$&$255$&$256$\\\hline
$f_9(n)$&$1$&$2$&$4$&$8$&$16$&$32$&$64$&$128$&$256$&$511$\\\hline
\end{tabular}

\end{frame}
%
\begin{frame}
\frametitle{Retournement de $\leq r$ pièces (suite)}

{\footnotesize\itempoint Rappel : règle du jeu : retourner $\leq r$
  pièces + règle commune.

\itempoint $f_r(n)$ = valeur de Grundy d'une seule pièce noire en
position $n$.

\itempoint V. de Grundy gén\rlap{.}\textsuperscript{ale} = somme de
nim des $f_r(n)$ sur les pièces noires.\par}

\itempoint Que vaut $f_r(n)$ ?

\[
\begin{aligned}
f_r(n) = \mex\{&f_r(m_1)\oplus\cdots\oplus f_r(m_s)\\
:\;&m_1,\ldots,m_s<n\text{~et~}s<r\}
\end{aligned}
\]

C'est-à-dire : $f_r(n)$ est le plus petit entier naturel qui n'est pas
somme de nim $f_r(m_1)\oplus\cdots\oplus f_r(m_s)$ de $s<r$ valeurs de
$f_r$ en des $m<n$.

\medskip

{\footnotesize Exemple : $f_3(3) = \mex\{0, f_3(1), f_3(2),
  f_3(1)\oplus f_3(1), f_3(1)\oplus f_3(2), f_3(2)\oplus
  f_3(2)\}$

\medskip

\begin{tabular}{r|rrrrrrrrrr}\hline
$n$&$1$&$2$&$3$&$4$&$5$&$6$&$7$&$8$&$9$&$10$\\\hline
$f_3(n)$&$1$&$2$&$4$&$7$&$8$&$11$&$13$&$14$&$16$&$19$\\\hline
(bin.)&$\scriptstyle\mathtt{1}$&$\scriptstyle\mathtt{10}$&$\scriptstyle\mathtt{100}$&$\scriptstyle\mathtt{111}$&$\scriptstyle\mathtt{1000}$&$\scriptstyle\mathtt{1011}$&$\scriptstyle\mathtt{1101}$&$\scriptstyle\mathtt{1110}$&$\scriptstyle\mathtt{10000}$&$\scriptstyle\mathtt{10011}$\\\hline
\end{tabular}

\par}

\end{frame}
%
\begin{frame}
\frametitle{Retournement de $\leq 3$ pièces}

{\footnotesize
\begin{tabular}{r|rrrrrrrrrr}\hline
$n$&$1$&$2$&$3$&$4$&$5$&$6$&$7$&$8$&$9$&$10$\\\hline
$f_3(n)$&$\scriptstyle\mathtt{\textcolor{brown}{1}}$&$\scriptstyle\mathtt{1\textcolor{brown}{0}}$&$\scriptstyle\mathtt{10\textcolor{brown}{0}}$&$\scriptstyle\mathtt{11\textcolor{brown}{1}}$&$\scriptstyle\mathtt{100\textcolor{brown}{0}}$&$\scriptstyle\mathtt{101\textcolor{brown}{1}}$&$\scriptstyle\mathtt{110\textcolor{brown}{1}}$&$\scriptstyle\mathtt{111\textcolor{brown}{0}}$&$\scriptstyle\mathtt{1000\textcolor{brown}{0}}$&$\scriptstyle\mathtt{1001\textcolor{brown}{1}}$\\\hline
\end{tabular}
\par}

\medskip

\itempoint \textcolor{red}{P}-positions (= Grundy $0$) au
retourn\rlap{.}\textsuperscript{t} de $\leq 3$ pièces :

\vskip-0.5\baselineskip

\begin{columns}
\begin{column}{0.3\textwidth}
\begin{center}
\begin{tikzpicture}[scale=0.7]
\begin{scope}
\draw[step=\squaresize] (-\squaresize,-\squaresize) grid (7*\squaresize,0);
\draw[fill] (-0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-1.2*\squaresize)}]
\draw[step=\squaresize] (-\squaresize,-\squaresize) grid (7*\squaresize,0);
\draw[fill] (-0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-2.4*\squaresize)}]
\draw[step=\squaresize] (-\squaresize,-\squaresize) grid (7*\squaresize,0);
\draw (-0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-3.6*\squaresize)}]
\draw[step=\squaresize] (-\squaresize,-\squaresize) grid (7*\squaresize,0);
\draw[fill] (-0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-4.8*\squaresize)}]
\draw[step=\squaresize] (-\squaresize,-\squaresize) grid (7*\squaresize,0);
\draw (-0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\end{tikzpicture}
\end{center}
\end{column}
\begin{column}{0.3\textwidth}
\begin{center}
\begin{tikzpicture}[scale=0.7]
\begin{scope}
\draw[step=\squaresize] (-\squaresize,-\squaresize) grid (7*\squaresize,0);
\draw (-0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-1.2*\squaresize)}]
\draw[step=\squaresize] (-\squaresize,-\squaresize) grid (7*\squaresize,0);
\draw[fill] (-0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-2.4*\squaresize)}]
\draw[step=\squaresize] (-\squaresize,-\squaresize) grid (7*\squaresize,0);
\draw (-0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-3.6*\squaresize)}]
\draw[step=\squaresize] (-\squaresize,-\squaresize) grid (7*\squaresize,0);
\draw[fill] (-0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-4.8*\squaresize)}]
\draw[step=\squaresize] (-\squaresize,-\squaresize) grid (7*\squaresize,0);
\draw[fill] (-0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\end{tikzpicture}
\end{center}
\end{column}
\begin{column}{0.3\textwidth}
\begin{center}
\begin{tikzpicture}[scale=0.7]
\begin{scope}
\draw[step=\squaresize] (-\squaresize,-\squaresize) grid (7*\squaresize,0);
\draw (-0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-1.2*\squaresize)}]
\draw[step=\squaresize] (-\squaresize,-\squaresize) grid (7*\squaresize,0);
\draw[fill] (-0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-2.4*\squaresize)}]
\draw[step=\squaresize] (-\squaresize,-\squaresize) grid (7*\squaresize,0);
\draw (-0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-3.6*\squaresize)}]
\draw[step=\squaresize] (-\squaresize,-\squaresize) grid (7*\squaresize,0);
\draw (-0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-4.8*\squaresize)}]
\draw[step=\squaresize] (-\squaresize,-\squaresize) grid (7*\squaresize,0);
\draw[fill] (-0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\end{tikzpicture}
\end{center}
\end{column}
\end{columns}

\medskip

\itempoint Si on efface la pièce la plus à gauche, ce sont celles pour
le retournement de $\leq 2$ pièces ($\cong$nim).

\itempoint La pièce la plus à gauche est telle que le nombre total de
pièces noires est pair (« parité »).

\itempoint\textbf{Code de Hamming étendu}

{\tiny Ici, il aurait mieux valu numéroter à partir de $0$.\par}

\end{frame}
%
\begin{frame}
\frametitle{Le code de Golay binaire étendu}

Le cas $r=7$ est particulièrement remarquable pour $24$ pièces.

\medskip

« Base » des \textcolor{red}{P}-positions pour $24$ pièces,
retourn\rlap{.}\textsuperscript{t} de $\leq 7$ :

\begin{center}
\begin{tikzpicture}[scale=0.6]
\begin{scope}
\draw[step=\squaresize] (0,-\squaresize) grid (24*\squaresize,0);
%% 111111110000000000000000
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (7.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (8.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (9.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (10.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (11.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (12.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (13.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (14.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (15.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (16.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (17.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (18.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (19.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (20.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (21.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (22.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (23.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-1.2*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (24*\squaresize,0);
%% 111100001111000000000000
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (7.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (8.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (9.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (10.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (11.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (12.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (13.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (14.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (15.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (16.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (17.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (18.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (19.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (20.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (21.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (22.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (23.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-2.4*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (24*\squaresize,0);
%% 110011001100110000000000
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (7.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (8.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (9.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (10.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (11.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (12.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (13.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (14.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (15.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (16.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (17.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (18.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (19.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (20.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (21.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (22.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (23.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-3.6*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (24*\squaresize,0);
%% 101010101010101000000000
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (7.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (8.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (9.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (10.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (11.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (12.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (13.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (14.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (15.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (16.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (17.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (18.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (19.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (20.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (21.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (22.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (23.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-4.8*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (24*\squaresize,0);
%% 100101100110100100000000
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (7.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (8.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (9.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (10.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (11.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (12.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (13.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (14.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (15.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (16.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (17.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (18.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (19.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (20.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (21.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (22.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (23.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-6.0*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (24*\squaresize,0);
%% 011010101100000011000000
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (7.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (8.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (9.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (10.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (11.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (12.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (13.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (14.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (15.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (16.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (17.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (18.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (19.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (20.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (21.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (22.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (23.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-7.2*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (24*\squaresize,0);
%% 110001101010000010100000
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (7.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (8.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (9.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (10.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (11.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (12.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (13.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (14.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (15.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (16.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (17.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (18.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (19.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (20.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (21.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (22.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (23.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-8.4*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (24*\squaresize,0);
%% 010111000110000010010000
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (7.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (8.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (9.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (10.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (11.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (12.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (13.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (14.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (15.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (16.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (17.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (18.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (19.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (20.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (21.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (22.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (23.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-9.6*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (24*\squaresize,0);
%% 000111101000100010001000
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (7.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (8.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (9.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (10.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (11.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (12.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (13.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (14.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (15.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (16.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (17.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (18.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (19.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (20.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (21.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (22.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (23.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-10.8*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (24*\squaresize,0);
%% 101110000100100010000100
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (7.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (8.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (9.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (10.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (11.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (12.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (13.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (14.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (15.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (16.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (17.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (18.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (19.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (20.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (21.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (22.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (23.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-12.0*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (24*\squaresize,0);
%% 011100100010100010000010
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (7.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (8.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (9.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (10.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (11.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (12.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (13.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (14.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (15.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (16.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (17.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (18.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (19.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (20.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (21.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (22.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (23.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\begin{scope}[shift={(0,-13.2*\squaresize)}]
\draw[step=\squaresize] (0,-\squaresize) grid (24*\squaresize,0);
%% 001001001110100010000001
\draw (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (7.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (8.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (9.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (10.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (11.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (12.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (13.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (14.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (15.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (16.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (17.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (18.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (19.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (20.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (21.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (22.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (23.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\end{scope}
\end{tikzpicture}
\end{center}

(Toutes les $4096 = 2^{12}$ \textcolor{red}{P}-positions s'obtiennent
en combinant ces $12$ par XOR=retournement.)

\medskip

C'est le \textbf{code de Golay binaire étendu} de longueur $24$ : fait
passer $12$ bits, corrige $3$ erreurs (détecte $7$).

\end{frame}
%
\begin{frame}
\frametitle{Le code de Golay binaire étendu (suite)}

(Toujours $24$ pièces, retournement de $\leq 7$.)

Les $4096$ mots du code (:=\textcolor{red}{P}-positions) se
répartissent en :
\begin{itemize}
{\footnotesize\item $1$ position « toute blanche »,\par}
\item $759$ positions avec $8$ pièces (une \textbf{octade}) noires,
\item $2576$ positions avec $12$ pièces (une \textbf{dodécade}) noires,
{\footnotesize
\item $759$ positions avec $16$ pièces noires, une octade blanche,
\item $1$ position « toute noire ».
\par}
\end{itemize}

\medskip

\itempoint Cinq pièces quelconques appartiennent toujours à une unique
octade (\textbf{système de Steiner} $(5,8,24)$).

\medskip

\itempoint Il y a $244\,823\,040$ façons de permuter les $24$ pièces
qui préservent les octades / mots du code : c'est le \textbf{groupe de
  Mathieu} $M_{24}$ (l'un des groupes finis simples sporadiques).

\end{frame}
%
\begin{frame}
\frametitle{Un jeu plus facile}

\itempoint Retourner un \underline{intervalle} de pièces, la plus à
droite de noir à blanc (règle commune).

\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw[step=\squaresize] (0,0) grid (15*\squaresize,\squaresize);
\draw[fill] (0.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (7.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (8.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (9.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (10.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (11.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (12.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (13.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\draw (14.5*\squaresize,0.5*\squaresize) circle [radius=\coinradius];
\node[anchor=north] at (0.5*\squaresize,0) {\tiny$1$};
\node[anchor=north] at (1.5*\squaresize,0) {\tiny$2$};
\node[anchor=north] at (2.5*\squaresize,0) {\tiny$3$};
\node[anchor=north] at (3.5*\squaresize,0) {\tiny$4$};
\node[anchor=north] at (4.5*\squaresize,0) {\tiny$5$};
\node[anchor=north] at (5.5*\squaresize,0) {\tiny$6$};
\node[anchor=north] at (6.5*\squaresize,0) {\tiny$7$};
\node[anchor=north] at (7.5*\squaresize,0) {\tiny$8$};
\node[anchor=north] at (8.5*\squaresize,0) {\tiny$9$};
\node[anchor=north] at (9.5*\squaresize,0) {\tiny$10$};
\node[anchor=north] at (10.5*\squaresize,0) {\tiny$11$};
\node[anchor=north] at (11.5*\squaresize,0) {\tiny$12$};
\node[anchor=north] at (12.5*\squaresize,0) {\tiny$13$};
\node[anchor=north] at (13.5*\squaresize,0) {\tiny$14$};
\node[anchor=north] at (14.5*\squaresize,0) {\tiny$15$};
\end{tikzpicture}
\end{center}

\vskip-\baselineskip

{\footnotesize Exemple de coup : retourner les pièces de $7$ à $12$.\par}

\itempoint Valeur de Grundy = somme de nim des $g(n)$ sur les numéros
$n$ des pièces noires (comptées à partir de $1$).

\itempoint Cette fois, $g(n)$ = plus grande puissance de $2$
divisant $n$.

\medskip

\itempoint Autrement dit, une \textcolor{red}{P}-position a un nombre
\underline{pair} de :
\begin{itemize}
\item pièces noires de numéro impair,
\item pièces noires de n\rlap{.}\textsuperscript{o} multiple de $2$ mais pas $4$,
\item pièces noires de n\rlap{.}\textsuperscript{o} multiple de $4$ mais pas $8$,
\item pièces noires de n\rlap{.}\textsuperscript{o} multiple de $8$ mais pas $16$, etc.
\end{itemize}

{\footnotesize Stratégie : jouer vers une telle position.
  Vérification faisable « à l'œil ».\par}

\bigskip

\textbf{Exercice :} démontrer directement cette stratégie !

\end{frame}
%
\subsection{Le produit de nim}
\begin{frame}
\frametitle{Un jeu bidimensionnel : nim$\otimes$nim}

\itempoint Cette fois, on joue sur une \underline{grille
  rectangulaire} de pièces :

\begin{center}\vskip-\baselineskip
\begin{tikzpicture}[scale=0.7]
\draw[step=\squaresize] (0,0) grid (7*\squaresize,-7*\squaresize);
\draw[fill] (0.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-0.5*\squaresize) circle [radius=\coinradius];
\draw (0.5*\squaresize,-1.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (1.5*\squaresize,-1.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-1.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-1.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-1.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-1.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-1.5*\squaresize) circle [radius=\coinradius];
\draw (0.5*\squaresize,-2.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-2.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (2.5*\squaresize,-2.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-2.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-2.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-2.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-2.5*\squaresize) circle [radius=\coinradius];
\draw (0.5*\squaresize,-3.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-3.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-3.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (3.5*\squaresize,-3.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-3.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-3.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-3.5*\squaresize) circle [radius=\coinradius];
\draw (0.5*\squaresize,-4.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-4.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-4.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-4.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (4.5*\squaresize,-4.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-4.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-4.5*\squaresize) circle [radius=\coinradius];
\draw (0.5*\squaresize,-5.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-5.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-5.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-5.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-5.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (5.5*\squaresize,-5.5*\squaresize) circle [radius=\coinradius];
\draw (6.5*\squaresize,-5.5*\squaresize) circle [radius=\coinradius];
\draw (0.5*\squaresize,-6.5*\squaresize) circle [radius=\coinradius];
\draw (1.5*\squaresize,-6.5*\squaresize) circle [radius=\coinradius];
\draw (2.5*\squaresize,-6.5*\squaresize) circle [radius=\coinradius];
\draw (3.5*\squaresize,-6.5*\squaresize) circle [radius=\coinradius];
\draw (4.5*\squaresize,-6.5*\squaresize) circle [radius=\coinradius];
\draw (5.5*\squaresize,-6.5*\squaresize) circle [radius=\coinradius];
\draw[fill] (6.5*\squaresize,-6.5*\squaresize) circle [radius=\coinradius];
\node[anchor=south] at (0.5*\squaresize,0) {\tiny$1$};
\node[anchor=south] at (1.5*\squaresize,0) {\tiny$2$};
\node[anchor=south] at (2.5*\squaresize,0) {\tiny$3$};
\node[anchor=south] at (3.5*\squaresize,0) {\tiny$4$};
\node[anchor=south] at (4.5*\squaresize,0) {\tiny$5$};
\node[anchor=south] at (5.5*\squaresize,0) {\tiny$6$};
\node[anchor=south] at (6.5*\squaresize,0) {\tiny$7$};
\node[anchor=east] at (0,-0.5*\squaresize) {\tiny$1$};
\node[anchor=east] at (0,-1.5*\squaresize) {\tiny$2$};
\node[anchor=east] at (0,-2.5*\squaresize) {\tiny$3$};
\node[anchor=east] at (0,-3.5*\squaresize) {\tiny$4$};
\node[anchor=east] at (0,-4.5*\squaresize) {\tiny$5$};
\node[anchor=east] at (0,-5.5*\squaresize) {\tiny$6$};
\node[anchor=east] at (0,-6.5*\squaresize) {\tiny$7$};
\end{tikzpicture}
\end{center}

\vskip-\baselineskip

\itempoint Retourner \emph{soit} une pièce, \emph{soit} deux sur une
ligne, \emph{soit} deux sur une colonne, \emph{soit} quatre sommets
d'un rectangle.

\itempoint La plus en bas à droite doit passer de noir à blanc.

{\footnotesize Exemple de coup : retourner les pièces $(2,4)$, $(2,6)$,
  $(6,4)$ et $(6,6)$.\par}

\itempoint Celui qui ne peut plus jouer a perdu.

\bigskip

\itempoint Le jeu termine en temps fini (exercice !).

\itempoint Valeur de Grundy : somme de nim des $a\otimes b$ où $(a,b)$
sont les pièces noires et $\otimes$ est une \underline{nouvelle}
opération, le \textbf{produit de nim}.

\end{frame}
%
\begin{frame}
\frametitle{Le produit de nim}

\begin{beamercolorbox}[sep=.5em]{otherhighlight}
$a\otimes b$ est le \underline{plus petit} entier naturel qui
  \underline{n'est pas} de la forme $(a'\otimes b) \oplus (a\otimes
  b') \oplus (a'\otimes b')$ pour $a'<a$ et $b'<b$
\end{beamercolorbox}

Symboliquement,
\vskip-2ex
\[
\begin{aligned}
a\otimes b = \mex\{&(a'\otimes b) \oplus (a\otimes b') \oplus (a'\otimes b')\\
:\;&0\leq a'<a\,,\; 0\leq b'<b\}
\end{aligned}
\]

Quelques propriétés :
\begin{itemize}
\item commutative : $a\otimes b = b\otimes a$ ;
\item associative : $a\otimes (b\otimes c) = (a\otimes b)\otimes c =: a\otimes b\otimes c$ ;
\item distributive sur la somme de nim : $a\otimes (b\oplus c) = (a\otimes b) \oplus (a\otimes c)$ ;
\item $0$ est « absorbant » : $a\otimes 0 = 0\otimes a = 0$ (mex vide) ;
\item $1$ est « neutre » : $a\otimes 1 = 1\otimes a = a$ ;
\item existence d'\textbf{inverses de nim} : si $a\neq 0$, il existe
  $b$ (entier naturel !) unique tel que $a\otimes b = 1$.
\end{itemize}

\end{frame}
%
\begin{frame}
\frametitle{Calcul du produit de nim}

{\footnotesize\itempoint Note : $2^m \oplus 2^n = 2^m + 2^n$ si $m\neq n$.\par}

\itempoint Comme $\otimes$ distribue sur $\oplus$, il suffit de
calculer $2^m \otimes 2^n$.

\smallskip

\itempoint On a $2^{2^u} \otimes 2^{2^v} = 2^{2^u + 2^v}$ si $u\neq v$
(c'est aussi $2^{2^u} \times 2^{2^v}$).

{\footnotesize Ainsi, si $n = 2^{u_1} + \cdots + 2^{u_s}$ alors $2^n =
  2^{2^{u_1}} \otimes \cdots \otimes 2^{2^{u_s}}$.

Exemple : $4\otimes 2 = 2^2\otimes 2^1 = 8$\par}

\smallskip

\itempoint Seul cas restant : « carré de nim » $2^{2^u} \otimes
2^{2^u} = \frac{3}{2}\cdot 2^{2^u}$ (s'écrit aussi $2^{2^u} + 2^{2^u -
  1} = 2^{2^u} \oplus 2^{2^u - 1}$).

{\footnotesize Exemple : $4\otimes 4 = 2^2 \otimes 2^2 = 6$\par}

\begin{center}
\footnotesize
\begin{tabular}{r|rrrrrrrrrrrrrrrr}
$\otimes$&$0$&$1$&$2$&$3$&$4$&$5$&$6$&$7$\\\hline
$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$\\
$1$&$0$&$1$&$2$&$3$&$4$&$5$&$6$&$7$\\
$2$&$0$&$2$&$3$&$1$&$8$&$10$&$11$&$9$\\
$3$&$0$&$3$&$1$&$2$&$12$&$15$&$13$&$14$\\
$4$&$0$&$4$&$8$&$12$&$6$&$2$&$14$&$10$\\
$5$&$0$&$5$&$10$&$15$&$2$&$7$&$8$&$13$\\
$6$&$0$&$6$&$11$&$13$&$14$&$8$&$5$&$3$\\
$7$&$0$&$7$&$9$&$14$&$10$&$13$&$3$&$4$\\
\end{tabular}
\end{center}

\end{frame}
%
\begin{frame}
\frametitle{Remarques diverses}

\itempoint On peut faire un jeu tridimensionnel : utiliser les
$a\otimes b\otimes c$.

\smallskip

\itempoint Produit de jeux de retournements de pièces : (règle
commune : la pièce en bas à droite passe de noir à blanc).

\begin{itemize}
\item « Retourner $\leq r$ lignes »$\otimes$« retourner $\leq s$
  colonnes » : Grundy est somme de nim des $f_r(a) \otimes f_s(b)$.
\item « Retourner un rectangle » : idem $g(a) \otimes g(b)$.
\item « Retourner un ensemble de lignes et colonnes » : idem $2^{a-1}
  \otimes 2^{b-1}$.  {\tiny (C'est $a-1$ car numérotation à partir
    de $1$.)}
\end{itemize}

\bigskip

\itempoint Les entiers $0\leq n<2^{2^u}$ sont stables par $\oplus$ et
$\otimes$ et sont un « \textbf{corps fini} » pour ces opérations.

\smallskip

{\footnotesize\itempoint Si $n < 2^{2^u}$, l'inverse de nim de $n$ est
  sa $(2^u-1)$\textsuperscript{ème} puissance de nim.\par}

\end{frame}
%
\end{document}