Jeu du baguenaudier

Un baguenaudier artisanal à 5 anneaux montés « en escalier » avec une cordelette comme navette. Pour l'ouvrir ou le fermer, il faut au moins 21 manipulations en formant des boucles de la cordelette à passer dans les anneaux.

Le baguenaudier ou baguenodier (étymologiquement « nœud de bagues » ; en anglais Chinese Rings, Cardan's Suspension, Cardano's Rings, Devil's needle ou five pillars puzzle) est un casse-tête mécanique composé d'une navette mobile formant une boucle fermée (éventuellement flexible) et d'anneaux rigides (mobiles si la navette est rigide) retenus chacun par une tige liée à un même support^[1]^,^[2].

Le jeu est peut-être d'origine chinoise. Il est expliqué dans le problème 107 du livre De viribus quantitatis de Luca Pacioli^[3] et il a été étudié dans leurs ouvrages par John Wallis^[4] et par Jérôme Cardan^[5].

Histoire[modifier | modifier le code]

Solution mathématique[modifier | modifier le code]

É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 à $n$ anneaux est donné par la suite (référencée A000975 dans l'OEIS) :

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ù $\lceil x\rceil$ est la partie entière par excès (plafond) de $x$ .

Version algorithmique[modifier | modifier le code]

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 maintenues parallèles avec un 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 (où 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).

Règles[modifier | modifier le code]

On peut toujours inverser (passer de 1 à 0 ou vice-versa) la case 1.
On ne peut inverser ("vider" ou "poser") la case $j$ $j$ , $j\in [2,n]$ $j\in [2,n]$ que :
- si la case $j-1$ est à 1 et toutes les cases précédentes sont à 0, ou
- si la case $j-1$ est à 0 et toutes les cases précédentes sont à 1.

Ces règles sont totalement symétriques, on obtient une solution en sens inverse si on inverse les valeurs 1 et 0 dans toutes les cases simultanément. Ce qui donne aussi une solution équivalente au problème inverse (libérer la cordelette ou l'arceau des petits anneaux, ou parvenir à le faire passer dans tous les petits anneaux).

De même le problème purement binaire utilise une numérotation (un ordre) préétablie des cases mais somme toute arbitraire (on peut tout autant permuter les cases). Le jeu physique impose en revanche un ordre, imposé par sa construction, mais cet ordre n'ajoute aucune difficulté à la résolution algorithmique du problème qui fournit une solution quel que soit cet ordre imposé au départ.

Solution pour $n = 4$ [modifier | modifier le code]

Il faut au minimum 10 coups (et moins de 10 secondes) pour résoudre le baguenaudier pour $n=4$ . Tous les 2 coups, c'est la case 1 qui est inversée, tous les 4 coups c'est la case 2 qui est inversée, les cases dans la dernière moitié ne sont inversées chacune qu'une seule fois dans des coups séparés (avec 4 coups d'écart entre ces coups). Plusieurs solutions sont possibles (de façon combinatoire en raison de la symétrie du problème et de l'ordre initial arbitraire des cases), il y a donc $n!=24$ solutions minimales en 10 coups, dont en voici une (qui représente aussi une solution du problème inverse, en la lisant soit de gauche à droite soit de droite à gauche, ou bien en permutant l'interprétation des états 1 ou 0 de chaque case ; si on effectue ces deux changements d'interprétation simultanément, on obtient aussi une deuxième solution du même problème initial car cela revient à simplement inverser l'ordre des cases et donc donne une autre des 24 permutations possibles). :

Case 1 :	1		1	⬌	0		0	⬌	1		1	⬌	0		0	⬌	1		1	⬌
Case 2 :	1	⬌	0		0		0		0	⬌	1		1		1		1	⬌	0
Case 3 :	1		1		1		1		1		1		1	⬌	0		0		0
Case 4 :	1		1		1	⬌	0		0		0		0		0		0		0

Les baguenaudiers sont traditionnellement construits avec un nombre impair d'anneaux : les modèles les plus courants avec 5 anneaux demandent 21 coups (et ils peuvent donc s'ouvrir et se fermer facilement en moins de 20 secondes avec des composants inflexibles). Des modèles à 7 anneaux existent, qui demandent au minimum 85 coups et donc un peu plus d'une minute pour les ouvrir ou les fermer en un minimum de coups. Un modèle rigide à 9 anneaux demande au minimum 341 coups, et donc presque 6 minutes de manipulations continues (au moins un coup par seconde) pour l'ouvrir ou le fermer complètement sans erreur.

Algorithme[modifier | modifier le code]

vider(n) fait passer les n cases du baguenaudier de 1 à 0, remplir(n) fait passer les n cases du baguenaudier de 0 à 1. poser(i) rend la case i égale à 1, enlever(i) rend la case i égale à 0.

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)

Sécurité[modifier | modifier le code]

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 le 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é 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 internes 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 rappel et de crans de blocage 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).

Bibliographie[modifier | modifier le code]

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)

Références[modifier | modifier le code]

↑ Lucas 1882, p. 177 [lire en ligne].
↑ Héraud 1884, p. 604 [lire en ligne].
↑ Version scannée du la page en italien du livre De viribus quantitatis.
↑ Gros 1872, « Algèbre de Wallis », p. 8–11.
↑ Gros 1872, « Subtilité de Cardan », p. 5–8.
↑ (en) David Darling, « Chinese rings », Encyclopedia of Science, sur The Worlds of David Darling.
↑ (en) Eric W. Weisstein, « Baguenaudier », sur MathWorld.

[1] Lucas 1882, p. 177 [lire en ligne].

[2] Héraud 1884, p. 604 [lire en ligne].

[3] Version scannée du la page en italien du livre De viribus quantitatis.

[4] Gros 1872, « Algèbre de Wallis », p. 8–11.

[5] Gros 1872, « Subtilité de Cardan », p. 5–8.

[DD-6] (en) David Darling, « Chinese rings », Encyclopedia of Science, sur The Worlds of David Darling.

[7] (en) Eric W. Weisstein, « Baguenaudier », sur MathWorld.

[1]

[2]

[3]

[4]

[5]

[6]

[7]