Résumé : il est parfois étonnant de constater que ce qui peut apparaître comme sérieux est utile également à des domaines plus futiles comme les jeux ou les casse-tête. Ainsi, le code de Gros-Grey utilisé dans le domaine des télécommunications et pour résoudre le problème du voyageur de commerce sur un hyper-cube est utile également pour résoudre le poblème du baguenaudier, des anneaux chinois et un casse-tête plus récent : le «Spin-out».
Mots-clés : chemin optimal, code, cube, hypercube, fractal, jeu.
L’exercice s’inspire du jeu Spin-out inventé par Wiliam Keister, ingénieur retraité des laboratoires Bell et diffusé par Binary Arts Corporation, 5601 Vine Street Alexandria, VA 22310. Il est également décrit dans l’article Voyageurs et baguenaudiers de Jean-Paul Delahaye, Pour la science, No 238, août 1997.
L’inventeur, William Keister, était un pionnier de la théorie de la communication aux laboratoires Bell. Dans les années cinquante, il a écrit un livre considéré comme la bible dans ce domaine. M. Keister est resté impliqué dans les systèmes de communication et les ordinateurs tout au long de sa carrière aux laboratoires Bell, jusqu’en 1972, date à laquelle il s’est retiré. M. Keister s’est intéressé assez tôt à la théorie des puzzles. Dans les années 30-40, les ingénieurs et les scientifiques commençaient à apprécier la logique des systèmes qui furent, par la suite, la base même des ordinateurs. A cette époque, il disait que les machines étaient capables d’additionner, de multiplier, de diviser, mais il n’était pas si évident qu’elles pourraient être programmées pour de la logique. Il était continuellement intéressé par la création de problèmes de logique, spécifiquement des problèmes qui n’avaient pas été mentionnés précédemment et d’essayer de les résoudre par diverses méthodes. Parmi ces exercices, M. Keister a travaillé à temps perdu sur des problèmes de puzzles et de jeux pour illustrer la possibilité de les résoudre par des systèmes logiques. Aux laboratoires Bell, en utilisant des boutons pression, des relais électromagnétiques et des ampoules électriques, il a essayé de résoudre le problème des anneaux chinois. M. Keister avait mal câblé son puzzle. En étudiant ce qu’il avait fait alors, il réalisa toutefois qu’il était tombé sur une série générale de codes binaires dans la séquence de ces puzzles, dont les anneaux chinois pouvaient être une variation. En utilisant cette idée, il définit alors un ensemble de séquences de codes sur papier et il fut capable de résoudre mathématiquement le problème en utilisant l’algèbre de Boole, un précurseur des langages de progammation des ordinateurs actuels. A sa retraite, M. Keister retourna à sa passion des puzzles, s’intéressant également à leur définition artistique et, dans les années 70-80, il en avait créé une série de permettant d’explorer toute une série de problèmes basés sur des codes binaires. Parmi ceux-ci, il a imaginé divers puzzles parmi lesquels celui intitulé Spin-out, qui est l’objet de cette description et le descendant le plus direct du travail original de Keister sur les anneaux chinois.
Un autre problème fait appel également à cette séquence, il s’agit du problème très classique du voyageur de commerce. La question qui est posée dans le problème dit du voyageur de commerce est la suivante : quel est le parcours le plus court passant par n villes et qui, de plus, évite de repasser plusieurs fois sur cette même ville ? Ce problème extrêmement simple n’a toujours pas trouvé de solution définitive mathématique et ne peut pas être généralisé. En revanche, si l’on s’intéresse au problème du voyageur de commerce dans un espace de dimension n, on est capable de le résoudre pour des cas particuliers comme les parallélépipèdes rectangles, ou, plus simplement, les cubes de dimension n. Un rectangle, en effet, a quatre sommets, un parallélépipède huit et, plus généralement, un parallélépipède à n dimensions en possède 2n sommets. On peut noter ces sommets par les suites OO…OO, OO…01, 00…10,…,11...1. Toutes les suites finies de n symboles 0 ou 1. Les longueurs des côtés du parallélépipède sont classées de la plus grande à la plus petite. Le problème est maintenant posé. En imposant de partir du sommet 0, ce qui n’enlève aucune généralité au problème, il faut trouver le chemin le plus court parcourant tous les sommets du parallélépipède et ne faisant passer qu’une seule fois par sommet. La solution est donnée par une suite de sommets qui constitue ce que l’on appelle le code de Gros-Gray, dont le nom provient de Louis Gros et de Frank Gray. Gros était clerc de notaire à Lyon, il publia en 1872 un opuscule où ce code était présenté pour la première fois en lien avec un casse-tête. Gray travaillait aux laboratoires Bell. Il réinventa ce code et en livra une étude détaillée dans les années 1930. Souvent, il se fait attribuer à lui seul cette invention.
On sait prouver que le code de Gros-Gray donne le plus court trajet du voyageur de commerce sur le parallélépipède rectangle. Ce trajet est représenté dans la figure ci-dessous. Le principe de déplacement du voyageur n’est complexe qu’au premier abord. Examiné attentivement, il exhibe des régularités fascinantes sur lesquelles nous allons nous attarder.
William Keister, ingénieur des laboratoires Bell est un ancien collègue de Franck Gray et c’est lui, comme on l’a vu plus haut, qui a inventé le casse-tête intitulé Spin-out. Il se présente sous la forme d’une règle avec une partie coulissante qu’il faut faire sortir, ce que des boutons pivotants semblent empêcher, car ils se bloquent les uns les autres et coincent le casse-tête. Au départ, tous les boutons sont verticaux et l’on comprend qu’il faudrait les placer tous à l’horizontale pour sortir la partie coulissante. Le bouton le plus à droite doit toujours être tourné ; lorsqu’on le pousse, la partie coulissante centrale le plus à gauche possible. Un peu d’attention montre que le bouton juste à gauche du bouton en position verticale le plus à droite peut, lui aussi, pivoter lorsqu’on pousse la partie coulissante centrale le plus à droite possible et qu’en fait c’est le seul qui puisse aussi l’être. Ces remarques étant faites, le casse-tête est résolu. En notant 1 les boutons verticaux et 0 les boutons horizontaux, nous venons de retrouver une des caractéristiques de la suite des codes de Gros-Gray.
Les connaisseurs de casse-tête mathématiques auront soupçonné une analogie entre le Spin-out de Keister et le très ancien baguenaudier appelé aussi meleda puzzle, Talamodspel ou anneaux chinois. Une légende en attribue l’invention au soldat Hung Min, (181-234) qui en aurait confié la résolution à son épouse, pendant qu’il était parti faire la guerre. La première mention du baguenaudier est faite au milieu du XIVe siècle sous la plume du mathématicien Jérôme Cardan, plus connu pour sa méthode de résolution des équations du 3e degré que pour son invention des cadrans, qui décrit le baguenaudier dans son De subtilitate libri XXI, paru à Nuremberg en 1550, où il précise : «cela de soi est inutile ; toutefois on peut le transférer aux serrures artificieuses de coffres.» Et effectivement, en Norvège, des sacs de voyages ont été équipés d’une fermeture utilisant le baguenaudier. On peut craindre que ces serrures se soient révélées agaçantes, par exemple lorsque le propriétaire, pris d’une soudaine envie d’éternuer, désirait y saisir un mouchoir. Pour résoudre le baguenaudier, l’analyse proposée pour le Spin-out s’applique presque mot à mot. On constate d’abord que le dernier anneau doit toujours être abaissé ou levé, et que le seul autre anneau qui accepte de se déplacer, celui qui précède l’anneau levé le plus à droite, et cela à condition d’avoir tiré la double tringle centrale le plus à gauche possible. Cela suggère de coder la position du baguenaudier en associant un 1 à tout anneau levé et un 0 à tout anneau baissé. La position de départ dans le cas d’un baguenaudier à 7 anneaux est donc 1111111 qui est le code de Gros-Gray de l’entier qui, en binaire, s’écrit 1010101 qui est 85. La suite est la même que pour le Spin-out, à condition de partir dans la bonne direction. Vous aboutirez en 85 étapes, et aucune méthode ne peut raccourcir les manipulations nécessaires, à la libération de la double tringle centrale. Si vous partez dans la mauvaise direction, vous aboutirez à une impasse. Notons deux avantages du Spin-out sur le baguenaudier, la commodité des manipulations et la facilité à en imaginer les variantes.
La suite de Gros-Gray donne d’ailleurs une solution à un autre casse-tête célèbre et ancien, les tours de Hanoï. Il s’agit de déplacer une pile de disques de taille croissante en n’utilisant que trois emplacements, A, B, C, formant un triangle équilatéral et en s’imposant à chaque étape de ne jamais poser un disque que sur un disque plus grand. La solution optimale, qui demande 2n - 1 une étape, consiste à déplacer alternativement le disque de taille 1, le plus petit, dans le sens des aiguilles d’une montre, puis celui de taille 2, le second en taille, puis le premier dans le sens des aiguilles d’une montre, puis le troisième etc. en suivant le schémas indiqué par la suite copie augmentée 1213121412131215... etc. Ceux qui trouvent que la suite de la copie augmentée est trop compliquée peuvent retenir la solution suivante encore plus courte et plus simple : déplacer alternativement le disque le plus petit dans le sens des aiguilles d’une montre, puis le seul disque disponible d’après les règles.
Pour résoudre les problèmes mentionnés plus haut, il faut définir le code de Gros-Gray. On peut le définir de plusieurs façons. A chaque entier n on peut associer sa notation binaire b(n) et son code de Gros-Gray que nous noterons g(n). On trouvera un tableau des premiers entiers ci-dessous.
La suite des codes Gros-Gray peut être définie de bien des façons, dont on prouve qu’elles sont équivalentes. Chacune de ces caractérisations sera utile. La première définition indique comment passer d’un code de Gros-Gray au suivant : on change un seul chiffre 1 en 0, 0 en 1, qui est : le dernier, si le nombre de «1» est pair ou celui à gauche du «1», le plus à droite, sinon. En appliquant cette règle, 110 est suivit de 111, qui a pour suivants 101, 100 puis, 1100. Cette règle permet au voyageur d’organiser sa tournée. Il n’a d’ailleurs même pas besoin de se souvenir de ce qu’il a fait auparavant, sa position seule lui donnant toutes les informations sur le prochain point où il doit se rendre. Qu’un seul chiffre soit changé à chaque étape explique partiellement que le code de Gros-Gray donne la solution du voyageur de commerce en dimension n. Ne changer qu’un seul chiffre signifie que les trajets qu’emprunte le voyageur de commerce sont les arêtes du parallélépipède. Il convient donc d’emprunter les diagonales d’un rectangle, qui, on le sait, sont plus longues que les côtés. Qu’un seul chiffre soit changé à chaque étape est aussi ce qui fait l’intérêt du code en électronique et en informatique où il est utilisé pour la conception de certains circuits et pour l’exploitation des ordinateurs parallèles. On place les unités de calculs de la machine sur un réseau correspondant à un hypercube, et le code de Gros-Gray fournit une numérotation des sommets de cet hypercube permettant le contrôle et l’optimisation des communications.
La deuxième caractérisation procède par récurrence. Le code de Gros-Gray de 0 est «0», ce qui, pour nous, est équivalent à «00», «000» ou «000» etc. D’une manière générale, nous ne tenons pas compte des «0» les plus à gauche du code. Si nous connaissons le code de Gros-Gray des 2n premiers entiers, celui 2n suivant est obtenu en le reprenant en ordre inverse et en le faisant précéder des codes d’un «1». mple : à partir des 4 premiers codes 00, 01, 11, 10, on obtient les quatre suivants en inversant l’ordre : 10, 11, 01, 00 et en ajoutant un «1» avant chaque code : 110, 111, 101, 100. A cause de ces propriétés, on dit que le code de Gros-Gray est un code réfléchi. Cette caractérisation donne un air fractal au parcours du voyageur de commerce. Le chemin qu’il suit à la seconde moitié du trajet est à l’envers et translaté le même que celui qu’il a parcouru à la première moitié du trajet, mais dans le second quart, le chemin parcouru est aussi à l’envers et translaté, le même que celui parcouru dans le premier quart, etc. D’ailleurs sur un parallélépipède, dans un espace à une infinité de dimensions dont les côtés seraient de longueur 1∕2n, le trajet du voyageur de commerce serait effectivement une courbe fractale.
La troisième caractérisation indique comment connaître le numéro du chiffre qui change quand on passe d’un code au suivant. Le code de Gros-Gray de n ne change du précédent que par un seul chiffre, dont le numéro est fixé par la suite : 1213121412131215... Cette suite que l’on dénomme, suite de la copie augmentée, s’obtient de la façon suivante, en parlant de la suite «1» : on la prolonge en la recopiant exactement, sauf le dernier élément qu’on augmente de 1 et on recommence, de «1» on passe à «12», puis à «1213», puis à «12131214», etc.
La quatrième caractérisation indique la description explicite de tous les chiffres. Les derniers chiffres des codes de Gros-Gray suivent le motif 01100110011, etc. Les avant-derniers chiffres des codes de Gros-Gray suivent le motif 0011110000111100000, etc. Les chiffres numéro i suivent en partant de la fin le motif 2i fois «0» puis, périodiquement 2i+1 le chiffre «1», 2i+1 le chiffre «0». Cette définition est la plus commode pour généraliser dans d’autres bases que deux les codes de Gros-Gray. En base trois, on fait varier les derniers chiffres selon le motif 0122100122100... l’avant-dernier, en reprenant le même motif, où l’on répète trois fois chacun des chiffres soit : 000111222222111000000111 etc. Les codes de Gros-Gray en base p donnent là aussi la solution au problème du voyageur de commerce, sur un réseau de parallélépipédique comportant p points dans chaque direction.
Les deux dernières caractérisations sont les plus intéressantes en pratique car, elles indiquent comment passer de la notation binaire au code de Gros-Gray et inversement. La règle de passage de la notation binaire au code de Gros-Gray est amusante. Le code de Gros-Gray de l’entier n s’obtient en prenant le code binaire de n, et en le dérivant. Les deux notations ont le même premier «1» ensuite, le digit numéro i en partant de la gauche est 0, si les chiffres numéro i - 1 et i du code binaire sont égaux, sinon c’est 1 (il s’agit bien de l’opération analogue à la dérivation lorsqu’on travaille uniquement avec des 0 et des I). Exemple : l’entier 14 s’écrit 1110 en notation binaire. Ce qui, en dérivant, donne le code de Gros-Gray de 14 : 1001 (Le 2e chiffre est un 0, car le premier et le second chiffre de l’écriture binaire de 14 sont égaux ; le 4e chiffre est un «1», car le 3e et 4e chiffre de l’écriture binaire de 14 sont différents.)
Cette méthode de calcul est très utile au voyageur de commerce qui, ne sachant pas où il est, mais se souvenant du nombre n de points qu’il a visités, se demande où il doit aller. Il écrit n en base 2, le dérive et sait alors où il est et donc, où il doit se rendre. La règle de passage de Gros-Gray à la notation binaire utilise, bien sûr, le procédé inverse de la dérivation : l’intégration. La notation binaire b de l’entier n s’obtient en intégrant le code de Gros-Gray g de l’entier n ; ce qui, précisément, signifie que le chiffre numéro i de b, en comptant à partir de la gauche, est la somme, modulo 2, des chiffres de g jusqu’au chiffre numéro i. Exemple : g = 101100 et le code de Gros-Gray de b = 110111, qui est l’écriture binaire de 32 + 16 + 4 + 2 + 1 = 55. Le 4e chiffre de b est un «1», car les 4 premiers chiffres de g sont 1011, dont la somme est 3 ou 1 modulo 2.
Pour résoudre les casse-tête mentionnés dans l’énoncé, il suffit d’utiliser le code de Gros-Gray. Si, au départ, on a la position 1111111, dont le numéro en binaire est par intégration 10101, c’est-à-dire 85, notre trajet, si nous nous y prenons mieux, comportera donc 85 mouvements qui consisteront à passer au code de Gros-Gray 84, puis 83 etc. Il est conseillé, pour résoudre ce problème, de prendre un Spin-out avec 4 disques uniquement au départ, et d’essayer de comprendre le principe de fonctionnement sur cette configuration plus simple avant de se lancer dans la résolution du Spin-out final.
La solution actuellement proposée est donnée par les fichiers MatLab : spinout.m, grosgrey.m et voyageur.m.