Jeu du baguenaudier

Édouard Lucas, l'inventeur des tours de Hanoï, a proposé une solution basée sur le système binaire et le code de Gray qui se formule comme son casse-tête[6]. Le nombre minimum de déplacements pour résoudre un problème à ${\displaystyle n}$ anneaux est donné par la suite (référencée A000975 dans l'OEIS) :

${\displaystyle a(n)=\left\lceil {\tfrac {2^{n+1}-2}{3}}\right\rceil ={\begin{cases}{\frac {2^{n+1}-2}{3}},&{\text{quand }}n{\text{ est pair,}}\\{\frac {2^{n+1}-1}{3}},&{\text{quand }}n{\text{ est impair.}}\end{cases}}}$[7]

où ${\displaystyle \lceil x\rceil }$ est la partie entière par excès (plafond) de ${\displaystyle x}$.

Considérons une représentation binaire du jeu. Résoudre le jeu signifie mettre toutes les cases à 1 (ou l'inverse les remettre toutes à 0).

Avec un baguenaudier physique, "remplir" ou "vider" les cases consiste à passer (dans le bon ordre) un arceau principal ou une cordelette dans ou hors d'un des petits anneaux du jeu pour, soit libérer la cordelette ou l'arceau principal de tous les petits anneaux, soit à l'inverse emprisonner la cordelette ou l'arceau par tous les petits anneaux: les "cases" représentent l'état de chacun des petits anneaux (c'est-à-dire si le grand arceau ou la cordelette passe ou pas au travers de chaque petit anneau).

Cependant le jeu avec la cordelette flexible nécessite des manipulations plus simples pour passer d'un état à l'autre ; le jeu avec l'arceau inflexible demande de plus de dextérité pour faire passer les petits anneaux les uns dans les autres, même si l'arceau passe ou pas en leur centre (qui sont alors soit de diamètres différents soit déformables de façon élastique, ou alors inflexibles mais de forme ovoïdale, ce qui nécessite alors de contrôler leur rotation de manière précise surtout si les ovales sont très faiblement aplanis, avec juste l'aplanissement nécessaire pour pouvoir passer un des petits anneaux dans un autre).

Dans la version chinoise du baguenaudier, la difficulté manipulatoire est augmentée par le fait que chacun des petits anneaux sont tous inflexibles et de même taille (de même que l'arceau) mais les petits anneaux sont tenus chacun par un crochet (pouvant pivoter librement) au bout d'une courte tige inflexible, les tiges (toutes de même longueur) étant maintenus parallèles avec une espacement régulier dans un support inflexible, mais pouvant coulisser longitudinalement au travers de ce support : au lieu d'orienter les anneaux, on peut les déplacer vers l'avant ou l'arrière en coulissant dans le support la tige où chaque anneau est lié pour ensuite pouvoir effectuer les rotations des anneaux à la position du crochet. Cette disposition est perturbante pour l'expérimentateur du jeu qui ne perçoit pas bien comment le problème est en fait plus simple qu'il ne semble, mais il nécessite une grande dextérité pour le résoudre car il faut orienter convenablement les anneaux (qui pivotent très librement autour de leur crochet) et ajuster le coulissement des tiges (qui lui aussi se fait librement) : on ne peut pas résoudre ce problème si les tiges ne sont pas à l'horizontale (pour qu'elles ne coulissent pas d'elles-mêmes dans le support à cause de la gravité, ce qui a pour effet aussi de réorienter chacun des anneaux mais pas de la façon voulue par l'opérateur).

Mais pour un expérimentateur qui connait la technique de manipulation, la version inflexible du baguenaudier permet une manipulation bien plus rapide (au moins un changement ou "coup" par seconde) qu'avec une navette flexible (ou chaque changement peut demander plusieurs secondes en prenant garde à conserver les boucles flexibles de la navette pour qu'elles restent dans chaque anneau, mais l'élasticité de la flexion de la navette peut lui faire changer sa place si le manipulateur ne retient pas les boucle extrêmes en maintenant une tension longitudinale suffisante sur celle-ci, mais souvent cette navette est plus longue que nécessaire et ne reste pas tendue, une des boucles peut donc s'échapper facilement librement de l'anneau où le manipulateur l'avait placée).

Mais algorithmiquement les problèmes à résoudre pour sur ces baguenaudiers physiques (dont il existe de nombreuses variantes dans le monde, depuis plusieurs millénaires pour certaines) sont équivalents au problème mathématique à "cases" binaires (qui lui ne demande aucune dextérité de manipulation mais seulement la réflexion logique).

def remplir(n) :
   if n == 1 :
      poser(1)
   elif n > 1 :
      remplir(n-1)
      vider(n-2)
      poser(n)
      remplir(n-2)
def vider(n) :
   if n == 1 :
      enlever(1)
   elif n > 1 :
      vider(n-2)
      enlever(n)
      remplir(n-2)
      vider(n-1)

Le baguenaudier binaire a été autrefois utilisé comme pseudo-serrure élémentaire par les paysans français. Cependant cela ne peut pas constituer une vraie sécurité, car quel que soit l'état de l'objet (hormis celui où il est totalement fermé ou totalement ouvert), on ne peut le manipuler que dans deux directions : le graphe complet du jeu se réduit à un seul segment qui joint l'état d'ouverture complète et celui de fermeture complète. Si on a compris comment manipuler l'objet, et même si on ne sait pas dans quelle direction commencer, on peut en choisir une des deux et faire les manipulations sans jamais revenir en arrière, et on aboutira soit à la situation où l'objet est totalement ouvert ou celle où il est totalement fermé ; si ce n'est pas la situation que l'on voulait obtenir, il suffit de reprendre les manipulations en sens inverse pour obtenir l'état final voulu. La seule sécurité obtenue (puisqu'on est certain de trouver une solution facilement) est celle du temps nécessaire à la manipulation pour ouvrir une telle serrure, ce temps ne dépendant que du nombre d'anneaux.

D'autres jeux plus complexes basés sur l'entrelacement existent, dont la résolution algorithmique obéit à une logique non binaire : il est alors bien plus compliqué d'explorer les différentes possibilités possibles à chacun des coups. Par exemple au lieu d'avoir une seule navette, il suffit simplement d'en ajouter au moins une deuxième qui va s'entrelacer aussi avec les anneaux et avec l'autre navette. À chaque étape, on doit donc déterminer quelle navette manipuler (on peut appeler ce jeu un « sac de nœuds », on le trouve communément dans problème connu du stockage des câbles, qu'il est particulièrement difficile de démêler une fois qu'ils se sont entrelacés dans un conteneur manipulés sans précaution) et le jeu offre toujours des possibilités inexplorées ou pas faciles à déterminer comme déjà explorées (car l’entrelacs masque une partie de ses états internes auxquels le manipulateur n'a pas accès ou dont il a causé la fermeture sans le savoir). Cependant il existe des jeux d'entrelacement à logique non binaire, utilisant des pièces dont aucun des états ne sont masqués à l'utilisateur, et offrant toujours plus de deux coups possibles à chaque étape : pour les résoudre, l'utilisateur doit faire appel à sa mémoire pour se souvenir des combinaisons déjà explorées, mais leur nombre explose vite de façon combinatoire ou exponentielle, ce jeu devient alors très difficile voire impossible à résoudre par un humain, qui ne sait alors pas s'il est sur la bonne voie vers la solution désirée. En revanche si l'utilisateur connait ou dispose de la combinaison (la clé) menant à l'ouverture, il peut franchir rapidement un nombre prédéfini et limité d'étapes et trouver la solution (ouvrir ou fermer la serrure) facilement sans perdre trop de temps (ce qui n'est pas le cas avec le baguenaudier classique).

Le graphe de tels jeux forme non pas une ligne mais des arbres orientés avec de nombreuses branches, avec éventuellement des boucles interne potentiellement alors infinies (qui peuvent être indétectables si le jeu cache volontairement au joueur une partie de ses états internes dans une boîte noire et n'interagit avec le joueur que comme un « oracle » donnant des réponses volontairement limitées). De tels jeux peuvent servir ensuite à constituer de véritables outils de sécurité (et donc utilisables comme « serrures » : il en existe justement qui s'appuient sur des ensembles internes complexes de roues dentées, de ressorts de rappels et de crans de blocages qui remplacent la simple navette, où toute erreur de manipulation oblige à reprendre les manipulations depuis le début à l'état totalement fermé, les retours en arrière étant bloqués par le matériel afin de ralentir considérablement l'exploration systématique des possibilités ; une difficulté supplémentaire est que même l'utilisateur, qui ne connait pas la séquence correcte d'ouverture, ne sait pas quand le matériel revient automatiquement à une configuration de fermeture totale, car les mêmes déplacements mécaniques internes font partie de la séquence correcte d'ouverture).

La version modernisée (et modélisée mathématiquement) de tels jeux complexes est constituée des algorithmes de chiffrement utilisés par l'informatique (par exemple basés sur la décomposition des entiers en facteurs premiers) et basés sur des combinatoires arithmétiques non binaires (où à chaque étape il existe plus de deux coups possibles et où il n'est pas facile de déterminer lequel est celui aboutissant à la solution désirée sans devoir explorer toutes les voies possibles, avec de nombreux retours en arrière ou reprises depuis le début en cas d'échec).

• Luc-Agathon-Louis Gros, Théorie du baguenodier par un clerc de notaire lyonnais, Lyon, Aimé Vingtrinier, 1872 (lire en ligne)
• Édouard Lucas, Récréations mathématiques, vol. 1, Paris, Gauthier-Villars, 1882, « Septième récréation : Le jeu du baguenaudier », p. 161–186
• Auguste Héraud, Jeux et récréations scientifiques : Applications faciles des mathématiques, de la physique, de la chimie et de l'histoire naturelle, Paris, Jean-Baptiste Baillière et fils, 1884, chap. XVI (« Jeux mathématiques et jeux de hasard : Jeu du Baguenaudier »), p. 604–609
• Franck Jeannot, « Histoire du Baguenaudier », périodique inconnu, Montréal,‎ décembre 2006 (lire en ligne)
• Jean Lefort, « Le baguenaudier et ses variantes », Dossier Pour la Science, n^o 59,‎ 30 novembre 1999 (lire en ligne)