\documentclass[a4paper,11pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[french]{babel}
\usepackage[a4paper,top=3.2cm,bottom=2cm,left=2cm,right=2cm]{geometry}
\usepackage{graphicx}
\usepackage[export]{adjustbox}
\usepackage{fancyhdr}
\usepackage{qrcode}
\usepackage[table]{xcolor}
\usepackage{amsmath,amssymb}
\usepackage{enumitem}
% Puces nettes (babel-french remplace sinon la puce par un tiret « – » peu pro).
% Vaut pour TOUTES les fiches qui importent ce module. AtBeginDocument pour
% passer après la personnalisation des listes faite par babel-french.
\AtBeginDocument{%
  \setlist[itemize]{leftmargin=1.8em,itemsep=0.5ex,topsep=0.4ex,parsep=0pt}%
  \setlist[itemize,1]{label=\textcolor{red!75!black}{\small\textbullet}}%
  \setlist[itemize,2]{label=\textcolor{red!75!black}{\scriptsize\textbullet}}%
}
% Titres compacts (gain de place vertical, fiches plus denses) — vaut pour tous.
\usepackage{titlesec}
\titlespacing*{\section}{0pt}{1.4ex}{0.6ex}
\titlespacing*{\subsection}{0pt}{1.0ex}{0.3ex}
% multicol : listes denses (calcul mental) sur 2 colonnes — neutre tant qu'il
% n'est pas utilisé, dispo pour tous les générateurs.
\usepackage{multicol}
\setlength{\columnsep}{1.5em}
% needspace : empêche un titre d'exercice de rester orphelin en bas de page
% (réserve quelques lignes ; sinon le titre passe à la page suivante avec sa
% liste). Neutre tant qu'il n'est pas appelé — dispo pour tous les générateurs.
\usepackage{needspace}
\usepackage{tikz}
\usetikzlibrary{decorations.text}

\usepackage{tgheros}
\pagestyle{fancy}
\fancyhf{}
\setlength{\headheight}{75pt}
\setlength{\headsep}{10pt}

\newcommand{\logowouf}{%
\begin{tikzpicture}[baseline={(current bounding box.center)},scale=0.55,
                    line cap=round,line join=round]
    \path[use as bounding box] (-2.20,-1.45) rectangle (2.20,2.20);
    \path[
        postaction={decorate},
        decoration={
            text along path,
            text={|\fontfamily{qhv}\bfseries\fontsize{9}{9}\selectfont|site2wouf.fr},
            text align={center},
            raise=0.03ex
        }
    ] (-1.29,0.48) arc[start angle=160,end angle=20,radius=1.29];
    \begin{scope}[xshift=-0.06cm]
        \fill[black] (-0.66,0.14) ellipse (0.21 and 0.31);
        \fill[black] ( 0.66,0.14) ellipse (0.21 and 0.31);
        \fill[black] (-0.23,0.49) ellipse (0.22 and 0.35);
        \fill[black] ( 0.23,0.49) ellipse (0.22 and 0.35);
        \fill[black]
            (0,-0.10)
            .. controls (-0.36,-0.02) and (-0.63,-0.24) .. (-0.58,-0.58)
            .. controls (-0.52,-0.93) and (-0.16,-1.12) .. (0,-0.90)
            .. controls (0.16,-1.12) and (0.52,-0.93) .. (0.58,-0.58)
            .. controls (0.63,-0.24) and (0.36,-0.02) .. (0,-0.10)
            -- cycle;
    \end{scope}
\end{tikzpicture}%
}

\newcommand{\titre}{Le jeu des allumettes}
\newcommand{\soustitre}{Probl\`eme --- Fiche n\textdegree 157}

\fancyhead[C]{%
\raisebox{4pt}{%
\begin{minipage}[c]{0.15\textwidth}
    \centering
    \logowouf
\end{minipage}
\begin{minipage}[c]{0.62\textwidth}
    \centering
    {\Large\bfseries \titre\par}
    {\small\color{gray} \soustitre}
\end{minipage}
\begin{minipage}[c]{0.21\textwidth}
    \centering
    \qrcode[height=1.5cm]{https://site2wouf.fr/allumettes.php?x=157}\\[2pt]
    {\small\ttfamily\bfseries\color{red} ALLU0157}
\end{minipage}%
}
}

\begin{document}

\begin{center}
    \small Deux joueurs, un tas d'allumettes, et une règle très simple. Pourtant, l'un des deux peut gagner à coup sûr — quoi que fasse l'autre — à condition de savoir où sont les positions perdantes. Les découvrir demande de raisonner à l'envers, en partant de la fin de la partie.
\end{center}
\vspace{0.5em}
\sloppy
\needspace{5\baselineskip}
\subsection*{\textcolor{red}{Le jeu des allumettes}}
\noindent Deux joueurs, \textbf{Alice et Bruno}, disposent d'un tas d'allumettes. Ils jouent \textbf{chacun leur tour}, Alice commence. À son tour, un joueur doit retirer \textbf{1, 2, 3 ou 4} allumette(s) — pas le choix de passer.\par\addvspace{0.35em}
\noindent \textbf{Celui qui prend la }dernière\textbf{ allumette }perd\textbf{.}\par\addvspace{0.35em}
\noindent Voici le tas de départ, \textbf{36 allumettes} :\par\addvspace{0.35em}
\needspace{3\baselineskip}
\begin{center}
\begin{tikzpicture}[scale=1.0714, line join=round, line cap=round]
\draw[line width=0.5pt] (0.71,5.1) -- (0.71,6.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (0.6,6.1) -- (0.82,6.1) -- (0.82,6.32) -- (0.6,6.32) -- cycle;
\draw[line width=0.5pt] (1.26,5.1) -- (1.26,6.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (1.15,6.1) -- (1.37,6.1) -- (1.37,6.32) -- (1.15,6.32) -- cycle;
\draw[line width=0.5pt] (1.81,5.1) -- (1.81,6.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (1.7,6.1) -- (1.92,6.1) -- (1.92,6.32) -- (1.7,6.32) -- cycle;
\draw[line width=0.5pt] (2.36,5.1) -- (2.36,6.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (2.25,6.1) -- (2.47,6.1) -- (2.47,6.32) -- (2.25,6.32) -- cycle;
\draw[line width=0.5pt] (2.91,5.1) -- (2.91,6.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (2.8,6.1) -- (3.02,6.1) -- (3.02,6.32) -- (2.8,6.32) -- cycle;
\draw[line width=0.5pt] (3.81,5.1) -- (3.81,6.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (3.7,6.1) -- (3.92,6.1) -- (3.92,6.32) -- (3.7,6.32) -- cycle;
\draw[line width=0.5pt] (4.36,5.1) -- (4.36,6.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (4.25,6.1) -- (4.47,6.1) -- (4.47,6.32) -- (4.25,6.32) -- cycle;
\draw[line width=0.5pt] (4.91,5.1) -- (4.91,6.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (4.8,6.1) -- (5.02,6.1) -- (5.02,6.32) -- (4.8,6.32) -- cycle;
\draw[line width=0.5pt] (5.46,5.1) -- (5.46,6.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (5.35,6.1) -- (5.57,6.1) -- (5.57,6.32) -- (5.35,6.32) -- cycle;
\draw[line width=0.5pt] (6.01,5.1) -- (6.01,6.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (5.9,6.1) -- (6.12,6.1) -- (6.12,6.32) -- (5.9,6.32) -- cycle;
\draw[line width=0.5pt] (0.71,3.6) -- (0.71,4.6);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (0.6,4.6) -- (0.82,4.6) -- (0.82,4.82) -- (0.6,4.82) -- cycle;
\draw[line width=0.5pt] (1.26,3.6) -- (1.26,4.6);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (1.15,4.6) -- (1.37,4.6) -- (1.37,4.82) -- (1.15,4.82) -- cycle;
\draw[line width=0.5pt] (1.81,3.6) -- (1.81,4.6);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (1.7,4.6) -- (1.92,4.6) -- (1.92,4.82) -- (1.7,4.82) -- cycle;
\draw[line width=0.5pt] (2.36,3.6) -- (2.36,4.6);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (2.25,4.6) -- (2.47,4.6) -- (2.47,4.82) -- (2.25,4.82) -- cycle;
\draw[line width=0.5pt] (2.91,3.6) -- (2.91,4.6);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (2.8,4.6) -- (3.02,4.6) -- (3.02,4.82) -- (2.8,4.82) -- cycle;
\draw[line width=0.5pt] (3.81,3.6) -- (3.81,4.6);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (3.7,4.6) -- (3.92,4.6) -- (3.92,4.82) -- (3.7,4.82) -- cycle;
\draw[line width=0.5pt] (4.36,3.6) -- (4.36,4.6);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (4.25,4.6) -- (4.47,4.6) -- (4.47,4.82) -- (4.25,4.82) -- cycle;
\draw[line width=0.5pt] (4.91,3.6) -- (4.91,4.6);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (4.8,4.6) -- (5.02,4.6) -- (5.02,4.82) -- (4.8,4.82) -- cycle;
\draw[line width=0.5pt] (5.46,3.6) -- (5.46,4.6);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (5.35,4.6) -- (5.57,4.6) -- (5.57,4.82) -- (5.35,4.82) -- cycle;
\draw[line width=0.5pt] (6.01,3.6) -- (6.01,4.6);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (5.9,4.6) -- (6.12,4.6) -- (6.12,4.82) -- (5.9,4.82) -- cycle;
\draw[line width=0.5pt] (0.71,2.1) -- (0.71,3.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (0.6,3.1) -- (0.82,3.1) -- (0.82,3.32) -- (0.6,3.32) -- cycle;
\draw[line width=0.5pt] (1.26,2.1) -- (1.26,3.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (1.15,3.1) -- (1.37,3.1) -- (1.37,3.32) -- (1.15,3.32) -- cycle;
\draw[line width=0.5pt] (1.81,2.1) -- (1.81,3.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (1.7,3.1) -- (1.92,3.1) -- (1.92,3.32) -- (1.7,3.32) -- cycle;
\draw[line width=0.5pt] (2.36,2.1) -- (2.36,3.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (2.25,3.1) -- (2.47,3.1) -- (2.47,3.32) -- (2.25,3.32) -- cycle;
\draw[line width=0.5pt] (2.91,2.1) -- (2.91,3.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (2.8,3.1) -- (3.02,3.1) -- (3.02,3.32) -- (2.8,3.32) -- cycle;
\draw[line width=0.5pt] (3.81,2.1) -- (3.81,3.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (3.7,3.1) -- (3.92,3.1) -- (3.92,3.32) -- (3.7,3.32) -- cycle;
\draw[line width=0.5pt] (4.36,2.1) -- (4.36,3.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (4.25,3.1) -- (4.47,3.1) -- (4.47,3.32) -- (4.25,3.32) -- cycle;
\draw[line width=0.5pt] (4.91,2.1) -- (4.91,3.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (4.8,3.1) -- (5.02,3.1) -- (5.02,3.32) -- (4.8,3.32) -- cycle;
\draw[line width=0.5pt] (5.46,2.1) -- (5.46,3.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (5.35,3.1) -- (5.57,3.1) -- (5.57,3.32) -- (5.35,3.32) -- cycle;
\draw[line width=0.5pt] (6.01,2.1) -- (6.01,3.1);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (5.9,3.1) -- (6.12,3.1) -- (6.12,3.32) -- (5.9,3.32) -- cycle;
\draw[line width=0.5pt] (0.71,0.6) -- (0.71,1.6);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (0.6,1.6) -- (0.82,1.6) -- (0.82,1.82) -- (0.6,1.82) -- cycle;
\draw[line width=0.5pt] (1.26,0.6) -- (1.26,1.6);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (1.15,1.6) -- (1.37,1.6) -- (1.37,1.82) -- (1.15,1.82) -- cycle;
\draw[line width=0.5pt] (1.81,0.6) -- (1.81,1.6);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (1.7,1.6) -- (1.92,1.6) -- (1.92,1.82) -- (1.7,1.82) -- cycle;
\draw[line width=0.5pt] (2.36,0.6) -- (2.36,1.6);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (2.25,1.6) -- (2.47,1.6) -- (2.47,1.82) -- (2.25,1.82) -- cycle;
\draw[line width=0.5pt] (2.91,0.6) -- (2.91,1.6);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (2.8,1.6) -- (3.02,1.6) -- (3.02,1.82) -- (2.8,1.82) -- cycle;
\draw[line width=0.5pt] (3.81,0.6) -- (3.81,1.6);
\filldraw[fill=red!16, draw=black, line width=0.5pt] (3.7,1.6) -- (3.92,1.6) -- (3.92,1.82) -- (3.7,1.82) -- cycle;
\end{tikzpicture}
\end{center}
\noindent Les questions montent en difficulté : la première se traite à la main, la dernière demande une règle générale et sa justification.\par\addvspace{0.45em}
\begin{enumerate}
  \item \textbf{Pour commencer}, on joue avec un petit tas de \textbf{8 allumettes}. Alice a-t-elle une façon de gagner à coup sûr ? On pourra examiner les situations une par une, en partant de 0 allumette.
  \item Revenons au tas de \textbf{36 allumettes}. \textbf{Qui gagne}, si les deux joueurs jouent parfaitement ? Si c'est Alice, quel est son \textbf{premier coup} ?
  \item \textbf{Décrire toutes les positions perdantes} — celles où le joueur qui doit jouer est condamné, quoi qu'il fasse. Justifier la règle trouvée.
\end{enumerate}
\newpage
\section*{\textcolor{red}{Correction}}
\needspace{5\baselineskip}
\subsection*{\textcolor{red}{Le jeu des allumettes — Correction}}
\noindent{\color{green!45!black}\textbf{Le bon point de vue.} Ne cherchons pas « quel coup jouer », mais classons chaque \textbf{position} (le nombre d'allumettes restantes) en deux catégories, du point de vue du joueur qui \textbf{doit jouer} :}\par\addvspace{0.4em}
\begin{itemize}
  \item une position est \textbf{perdante} si \textbf{tous} les coups possibles offrent à l'adversaire une position gagnante ;
  \item une position est \textbf{gagnante} s'il \textbf{existe} au moins un coup donnant à l'adversaire une position perdante.
\end{itemize}
\noindent{\color{green!45!black}On construit ce classement \textbf{à partir de la fin}, en partant de 0 allumette. Se retrouver devant 0 allumette signifie que l'adversaire vient de prendre la dernière : il a \textbf{perdu}, donc \textbf{0 est une position gagnante} pour celui qui la reçoit.}\par\addvspace{0.4em}
\noindent \textbf{1.} Construisons le tableau jusqu'à 8 :\par\addvspace{0.35em}
\begin{center}
\renewcommand{\arraystretch}{1.35}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
\hline
\cellcolor{blue!7}\bfseries Allumettes restantes & \cellcolor{blue!7}\bfseries 0 & \cellcolor{blue!7}\bfseries 1 & \cellcolor{blue!7}\bfseries 2 & \cellcolor{blue!7}\bfseries 3 & \cellcolor{blue!7}\bfseries 4 & \cellcolor{blue!7}\bfseries 5 & \cellcolor{blue!7}\bfseries 6 & \cellcolor{blue!7}\bfseries 7 & \cellcolor{blue!7}\bfseries 8 \\ \hline
Le joueur qui doit jouer & gagne & \textbf{perd} & gagne & gagne & gagne & gagne & \textbf{perd} & gagne & gagne \\ \hline
\end{tabular}
\end{center}
\noindent{\color{red!80!black}\bfseries Avec 8 allumettes, la position de départ est \textbf{gagnante} : Alice a une façon de l'emporter à coup sûr.}\par\addvspace{0.4em}
\noindent\hspace{1.2em}Son coup : retirer \textbf{2} allumette(s), ce qui laisse 6 — une position perdante pour Bruno.\par\addvspace{0.3em}
\noindent \textbf{2.} Poursuivons le même tableau jusqu'à 36. Les positions perdantes rencontrées sont :\par\addvspace{0.35em}
\noindent{\color{red!80!black}\bfseries 1, 6, 11, 16, 21, 26, \dots{}}\par\addvspace{0.4em}
\noindent{\color{red!80!black}\bfseries 36 \textbf{est une position perdante}. Alice, qui commence, est donc \textbf{condamnée} : quoi qu'elle joue, Bruno peut toujours lui rendre une position perdante.}\par\addvspace{0.4em}
\noindent{\color{red!80!black}\bfseries \textbf{C'est Bruno qui gagne}, à condition de jouer correctement.}\par\addvspace{0.4em}
\noindent \textbf{3.}\par\addvspace{0.35em}
\noindent{\color{red!80!black}\bfseries Les positions perdantes sont les nombres de la forme \textbf{5q + 1} : 1, 6, 11, 16, \dots{}}\par\addvspace{0.4em}
\noindent{\color{green!45!black}\textbf{Pourquoi ce décalage ?} Le but a changé : prendre la dernière allumette fait \textbf{perdre}. Tout se passe donc comme si l'on jouait au jeu ordinaire sur un tas amputé de la dernière allumette — celle qu'il faut \textbf{laisser} à l'adversaire. D'où la règle décalée de 1.}\par\addvspace{0.4em}
\noindent{\color{green!45!black}\textbf{La stratégie.} Laisser toujours à l'adversaire un nombre d'allumettes de la forme 5q + 1 ; il finira nécessairement par devoir prendre la dernière.}\par\addvspace{0.4em}
\noindent{\color{red!80!black}\bfseries Ici 36 \(-\) 1 = 35, multiple de 5 : position perdante.}\par\addvspace{0.4em}
\noindent{\color{green!45!black}\textbf{À retenir, bien au-delà des allumettes.} Analyser un jeu à deux, c'est classer les positions en gagnantes et perdantes en remontant depuis la fin. La même méthode s'applique à quantité de jeux — et c'est exactement ce que fait un programme d'échecs, en beaucoup plus gros.}\par\addvspace{0.4em}
\end{document}
