Jeu de dames-évasion
Le but de l'exercice est d'étudier avec des outils mathématiques, un jeu de dame légèrement modifié qui se joue seul, et dont nous présentons les règles :
Au départ, il y a un damier, des pions placés dans une zone "prison". Le but est de libérer tous les pions de la zone prison (de nouveaux pions peuvent apparaître).
Le déplacement des pions est particulier : lorsqu'un pion est déplacé, il se dédouble en créant un pion à sa droite et un pion en dessous de sa position de départ. Il n'est pas possible de réculer et on ne peut pas 'sauter' par dessus un autre pion.
Avant de commencer les maths, essayez différentes stratégies au crayon, en utilisant les cases d'une feuille quadrillée. Sinon, une version jouable sur windows est disponible ici .
Les notions de cours utilisées dans cet exercice sont les suivantes :

Afin d'étudier mathématiquement ce jeu, nous attribuons un poids à chacun des pions. A chaque fois qu'un pion est déplacé, le poids est divisé en deux et réparti dans les deux pions créés.

Par exemple, si on déplace un pion qui pèse $1$, les deux pions crées pèseront $\frac{1}{2}$et ainsi de suite :

En fait, il est vain de s'entêter trop longtemps à jouer à ce jeu car, avec cette situation de départ (3 pions dans la prison), il est impossible de gagner. Le but de cet exercice est de le prouver. Expliquer pourquoi à n'importe quel tour de jeu, le poids cumulé des pions présents sur le damier vaut 2. Placer sur chaque case du damier ci-dessous (après l'énoncé) le poids que devrait avoir un pion sur celle-ci. On suppose un damier infini à droite et vers le bas. On définit $(a_n)$ la suite des poids que peut accueillir chaque case sur la ligne $a$ : $a_0 = 1, a_1 = 2,$ etc. Exprimer $a_{n+1}$ en fonction de $a_n$. Justifier que $(a_n)$ est géométrique puis précisez sa raison $q$ et son premier terme. On place 5 pions sur les premières cases de la ligne $a$. Calculer le poids cumulé des 5 cases sur la ligne. Justifier que pour les $n$ premiers pions, le poids cumulé vaut $2 (1 - \frac{1}{2^{n}})$ Quelle est le poids limite que peut accueillir la ligne $a$ ? (on considère qu'une infinité de pions est posée.) Les lignes suivantes sont assez similaires à la première. Justifier que le poids limite que peut accueillir la ligne $b$ vaut 1. Quels sont les poids limites que peuvent accueillir les lignes $c$, $d$, $e$ et $f$ ? Compléter la figure On pose $(p_n)$ la suite des poids limites de chaque ligne : $p_0$ est le poids de la ligne $a$, $p_1$ celui de la ligne $b$, etc. Quelle est la nature de la suite $(p_n)$ ? Justifier que les $n$ premières lignes peuvent accueillir ensemble un poids limite de $4 - \frac{1}{2^{n}}$. En déduire le poids limite que peut accueillir le damier entier. On admet ici que le damier peut accueillir un poids limite de $4$. Quel poids limite peuvent accueillir la zone prison, et la zone libre ? Pourquoi est-il impossible de gagner ? La conclusion reste-t-elle la même pour toute situatuin de départ ? Justifier.
Ce problème est inspiré de travaux de recherches présentés par la chaîne de vulgarisation mathématique Numberphile :