Toujours plus fort - Le jeu des bâtonnets

Vous sortez de la star Academy, votre single "Toi ma lova yeah" a fait un carton, on ne parle plus que de vous ! Pour votre image, vous acceptez de parrainer une association qui réalise les rêves d'enfants handicapés (nager avec les dauphins, toussa). Sans même savoir pourquoi, vous acceptez de participer à Fort Boyard pour défendre les couleurs de cette association. Pour votre réputation, c'est tout ou rien : vous remportez le jackpot, gagnez en sympathie auprès du public et rempilez tout de suite pour un nouvel album, ou bien, vous vous plantez monumentalement, et du jour au lendemain, vous redeviendrez serveur dans un bar.

Seulement 5 clé en votre possession, très peu d'indices, l'émission est mal partie. Pour espérer gagner un minimum, il faudra un maximum de temps dans la salle aux trésors. Tout va donc se jouer dans la salle du conseil... A votre tour de passer : votre défi contre le maître du temps sera le jeu des bâtonnets :

"Face à vous, 20 bâtonnets. Chacun votre tour, vous pourrez en retirer 1, 2 ou 3. Celui qui tire le dernier bâtonnet perd le duel, c'est à vous de commencer à jouer".

Le duel se déroule de la façon suivante :
(20) Vous en retirez : 1 - reste 19
(19) Le maître en retire : 2 - reste 17
(17) Vous : 1 - reste 16
(16) Le maître : 3 - reste 13
(13) Vous : 2 - reste 11
(11) Le maître : 2 - reste 9
(9) Vous : 3 - reste 6
(6) Le maître : 1 - reste 5
(5) Vous : 1 - reste 4 (Vous comprenez à ce moment là que vous êtes foutus)
(4) Le maître : 3 - reste 1
(1) Vous : 1 - reste 0 : vous avez perdu

Le duel est raté, votre équipe perd le moral, vous ne trouvez pas le mot-code, vous passez à côté du jackpot.... Les enfants handicapés vous en veulent, votre maigre réputation en prend un coup et votre carrière est ruinée. Le lendemain, vous pointez à l'ANPE. Fin.

Ce drame, pourtant, vous auriez pu l'éviter ! Il aurait suffit de réfléchir un peu... Pour le comprendre, essayons de remonter au coup que vous avez mal joué.

Configuration (1)

Configuration (1) : il y a un seul bâtonnet en jeu, et c'est à vous de jouer. Vous n'avez pas le choix, vous le prenez : vous avez perdu. La situation (1) est une configuration de perte.

Configuration (5) : 1+4

Configuration (5) : il y a 5 bâtonnets en jeu, et c'est à vous de jouer. Trois choix s'offrent à vous : prendre 1, 2 ou 3 bâtonnets. Dans tous les cas, votre adversaire pourra vous ramener à la configuration (1), en prenant respectivement 3, 2 ou 1 bâtonnet. La situation (5) est donc aussi une configuration de perte.

Configuration (9) : 1 + 2x4

Configuration (9) : de la même façon, peu importe le nombre de bâtonnet que vous prenez, votre adversaire vous ramènera à la configuration de perte (5), en faisant en sorte que 4 bâtonnets soit retirés. Plus généralement, toute configuration de la forme (4n+1) (des paquets de 4 plus une) est une configuration de perte : quiconque se retrouve dans cette situation sera amené à perdre.

Configuration (20) : 1+4x4+3

Configuration (20) : Vous commencez à jouer. Cette configuration n'est pas de la forme (4n+1), ce n'est donc pas une configuration de perte, mais vous pouvez amener votre adversaire dans une situation de perte. Quel est le plus petit nombre inférieur à 20 de la forme 4n+1 ? C'est 17 (1+4×4). Prenez donc 3 bâtonnets !
A partir de là, c'est vous qui contrôlez le jeu : s'il prend 1, 2 ou 3 bâtonnets, prenez en respectivement 3, 2 ou 1. Vous vous assurez que votre adversaire reste toujours dans une configuration de perte jusqu'à la fin du jeu.

De façon plus générale, si vous commencez à jouer avec un autre donné de bâtonnets (qui n'est pas de la forme 4n+1), il faut faire en sorte au premier coup qu'il en reste un nombre de la forme 4n+1 (en comptant les bâtonnets par paquets de 4).  Si vous commencez dans une situation perdante, il y a juste à espérer que votre adversaire ne connaisse pas le truc, et il faudra profiter d'un coup hasardeux pour que le jeu vous redevienne favorable.

Les jeux impartiaux
Le jeu des bâtonnets est un jeu que l'on classe dans la catégorie des jeux impartiaux : un jeu ne faisant pas intervenir le hasard (pas de lancé de dé, de cartes), qui ne peut pas se terminer en match nul (les échecs n'est pas un jeu impartial) et où le but est de placer l'adversaire dans une situation où il ne peut plus jouer. (Ou, dans le cas du jeu des bâtonnets, d'être le joueur qui ne peut plus jouer). Le jeu des bâtonnets est un jeu impartial, et de nombreuses techniques ont été développé pour gagner à coup sûr à ce genre de jeu.

Un jeu impartial est toujours équivalent à un jeu de déplacement sur un graphe. On place un pion sur la case initiale du graphe, le but étant de lui faire atteindre une position finale. Chacun leur tour, les joueur doivent déplacer le pion le long d'une arrête du graphe.
Prenons comme exemple le jeu des bâtonnets, avec 12  bâtonnets Les 12 sommets du graphe correspondent aux 12 configurations du jeu (de 12 à 1 bâtonnets restant). La case initiale sera la configuration (12), et la finale sera la configuration (1). Les déplacement sur le graphe correspondent à retirer 1, 2 ou 3 bâtonnets. Le but du jeu est d'amener le pion sur la position 1.

Graphe du jeu des bâtonnets

La stratégie pour gagner à ce type de jeu est de retrouver les positions gagnantes, que l'on appelle "noyau" du graphe. Ce noyau, ce sont les cases du graphe que l'on peut atteindre depuis n'importe quelle autre case, et jamais reliées l'une à l'autre. Dans le cas du jeu des bâtonnets, ce sont les cases correspondant aux positions (1), (5) et (9) (On peut vérifier facilement que l'on peut atteindre l'une de ces 3 cases depuis n'importe quelle autre case).

Pour son premier coup, le premier jouer a donc tout intérêt à retirer 3 bâtonnets, pour se retrouver en configuration (9). Peu importe le coup du deuxième joueur, on pourra atteindre la configuration (5), et donc la configuration (1) !

La prochaine fois que vous irez à Fort Boyard, vous saurez... A moins que vous inauguriez un nouveau type de duel, variante d'une jeu de Nim, et vous échouerez lamentablement, puisque je manque de temps pour les aborder dans mon article de cette semaine... La suite, la semaine prochaine !

---

Sources :
Interstices - Jeux de Nim (d'où proviennent les illustrations des graphes)

Comments

[Pyrrha]

Et si y'en a 21 battonet ???

[Tom Roud]

Manifestement, lui, il connaît le truc... C'est trop injuste : dès qu'un candidat se trompe dans la stratégie, il perd à coup sûr !

[@gor]

Très intéressant, en effet!
Je note aussi le soin particulier apporté à la forme de cet article, le début semble en effet inspiré par différentes publicités, la plus évidente serait celle pour le fameux remède miracle réparateur de la vitre avec un impact de 1€. :D

[Bigpzanda]

Intéressant, merci!