À l’occasion d’un très joli colloque à Alger, un collègue mathématicien m’a lancé il y a quelques mois un défi dont je n’imaginais pas qu’il m’emmènerait aussi loin. Il s’agit des tours de Hanoï, un jeu ainsi nommé au XIXè siècle par son inventeur facétieux, le mathématicien français Édouard Lucas. Ce jeu n’a rien à voir avec la ville de Hanoï, mais plutôt avec la façon dont nous écrivons les nombres entiers.
Dans le jeu des tours de Hanoï, n disques de tailles décroissantes et percés en leur milieu sont disposés sur un piquet A. Il s’agit de les amener sur un piquet C en s’aidant du piquet intermédiaire B, en déplaçant un disque d’un piquet à un autre à chaque étape, sans jamais qu’un disque soit posé sur un disque plus petit. Dans le dernier numéro de l’excellente revue québécoise Accromath (en ligne et gratuite) de l’université du Québec à Montréal, vous trouverez (outre un article d’André Ross sur Lucas) un article de votre serviteur qui s’intéresse aux liens entre les tours de Hanoï et la représentation des nombres en base deux et en base trois.
En un mot, pour la base deux : dans le jeu classique, le nombre minimal de configurations rencontrées pour parvenir à la solution est de 2 à la puissance n, ce qui permet de numéroter naturellement les configurations successives en base deux. Cette partie sur la base deux est classique. Celle sur la base trois (où l’on modifie les règles du jeu en interdisant aux disques d’aller directement de A à C ou de C à A, ce qui fait que le nombre de configurations rencontrées devient égal à 3 à la puissance n, d’où l’apparition de la base trois) l’est moins, même si elle n’a rien de révolutionnaire.
Dans une revue de vulgarisation, il n’était pas possible d’aller plus loin, mais il y a en réalité d’autres choses à faire, liées à des systèmes de numération plus exotiques qui ne semblent pas avoir été remarqués jusqu’à présent. Si tout va bien, j’aurai dans quelques mois des résultats nouveaux à présenter sur le sujet, dont l’intérêt tiendra moins au jeu des tours de Hanoï lui-même (dont on peut considérer que l’intérêt scientifique est limité) qu’aux outils utilisés. C’est là quelque chose de typique du fonctionnement des mathématiques théoriques : bien souvent, un énoncé a moins d’importance que les méthodes mises en œuvre pour le démontrer.
Mythes, Mancies & Mathématiques 