Le jeu des bâtonnets de Fort Boyard
Ce billet a été écrit à l'aide d'un notebook Jupyter. Son contenu est sous licence BSD. Une vue statique de ce notebook peut être consultée et téléchargée ici : 20170731_batonnetsFortBoyard.ipynb.
Dans ce billet, nous allons nous intéresser au jeu desbâtonnets de Fort Boyard.
Voici l'énoncé du jeu (adapté d'après http://www.fan-fortboyard.fr/pages/emission/conseil/batonnets.html) :
Dans ce duel, le candidat et le Maître se retrouvent à jouer avec un alignement de dix-huit bâtonnets (20 jusqu’en 2008).
Chacun leur tour, ils peuvent en retirer soit un, soit deux, soit trois. Celui qui retirera le dernier bâtonnet de la pile perd le duel.
Raisonnement à l'aide de quelques exemples¶
D'après l'énoncé, on sait que la configuration avec un seul bâtonnet est perdante :
losing = [1]
Que se passe-t-il pour deux bâtonnets ? En en enlevant un, on met l'adversaire dans la position perdante. Donc 2 est gagnante.
winning = [2]
Pour 3, c'est pareil, car en retirant deux bâtonnets, l'adversaire est en position perdante.
winning.append(3)
Et idem pour 4 : en enlevant 3 bâtonnets, on fait perdre l'adversaire.
winning.append(4)
Que se passe-t-il pour 5 ? Les possibilités que nous avons peuvent se calculer avec la fonction suivante :
def possible_outcomes(number_of_sticks):
return number_of_sticks - 1, number_of_sticks - 2, number_of_sticks - 3
possible_outcomes(5)
(4, 3, 2)
Il s'avère que toutes les configurations atteignables depuis 5 sont gagnantes. Donc la position 5 est perdante ! On peut écrire une fonction qui teste ceci :
all_winning = lambda candidates: all(candidate in winning for candidate in candidates)
On vérifie que la fonctionne donne le résultat attendu :
all_winning(possible_outcomes(5))
True
On ajoute 5 aux positions perdantes :
losing.append(5)
Généralisons cette démarche d'induction à l'aide d'une boucle sur les configurations possibles.
Généralisation de la démarche¶
On définit d'abord le nombre maximal de bâtonnets.
max_sticks = 18
L'algorithme est le même que celui que nous venons d'appliquer plus haut :
- soit une configuration permet d'aboutir à une configuration qui fait perdre l'autre (c'est le cas de 2->1, 3->1 ou 4->1 par exemple) et donc elle est gagnante
- soit une configuration ne permet d'aboutir qu'à des positions qui font gagner l'autre et donc elle est perdante
A priori, il peut y avoir d'autre positions (qui font accéder à des positions gagnantes et perdantes), mais nous constaterons expérimentalement que ce cas n'est pas possible.
losing = [1]
winning = [2, 3, 4]
for sticks in range(5, max_sticks + 1):
candidates = possible_outcomes(sticks)
# configuration gagnante car elle permet d'accéder
# à une config qui fait perdre l'autre joueur
for candidate in candidates:
if candidate in losing:
winning.append(sticks)
break
# configuration perdante car l'autre joueur gagne
# à tous les coups
if all_winning(candidates):
losing.append(sticks)
Vérifions les résultats :
winning
[2, 3, 4, 6, 7, 8, 10, 11, 12, 14, 15, 16, 18]
losing
[1, 5, 9, 13, 17]
Vérifions que nous avons couvert tous les nombres de bâtonnets entre 1 et max_sticks :
set(losing + winning) - set(range(1, max_sticks + 1))
set()
Conclusions¶
Les résultats de l'algorithme ci-dessus montrent que si l'on arrive à placer l'adversaire dans la position où le nombre de bâtonnet qu'il voit est de la forme $n = 4 k + 1, k \in \mathbb{N}$, alors on gagne à coup sûr. Donc, si l'on commence à 18 et que l'on connaît le jeu, on peut facilement remporter la partie (en commençant par retirer un bâtonnet puis en s'assurant d'enlever 4 bâtonnets entre son propre tour et le tour de l'adversaire). Idem pour la variante à 20 bâtonnets.
