La tour de Hanoï, entre jeu, algorithmes et fractals

par Benoît Rittaud

Proposée par le mathématicien Édouard Lucas au XIXe siècle, la tour de Hanoï est beaucoup plus qu’un simple jeu. C’est un objet d’étude, auquel chacun peut s’intéresser quelles que soient ses connaissances mathématiques préalables. Benoit Rittaud s’intéresse à ses aspects algorithmiques, en montrant comment des points de vue différents conduisent à des algorithmes différents (itératif ou récursif), qui ont chacun ses forces et ses faiblesses. Il aborde ensuite la variante dans laquelle il s’agit de résoudre le jeu le plus lentement possible. Enfin, il présente le lien inattendu entre la tour de Hanoï et un objet fractal.

Benoît Rittaud est maître de conférences à l’université Paris 13.

Pour aller plus loin :

  • A. Hinz, S. Klavžar, U. Milutinović & C. Petr (2013), The Tower of Hanoï – Myths and Maths, Springer Basel.
  •  A. Hinz (1992), « Pascal’s Triangle and the Tower of Hanoi », Am. Math. Mon. 99, n°6, 538-544.
  •  B. Rittaud (2017), « A Numeration System and a Gray Code Given by a Variant of the Tower of Hanoi », Numeration 2017, 5-10. http://logica.uniroma3.it/jn17/numeration2017.pdf
  •  B. Rittaud (2016), « Les tours de Hanoï et la base 3 », Accromath 11.1, http://accromath.uqam.ca/2016/02/les-tours-de-hanoi-et-la-base-trois/
  •  W. Sierpiński (1915), « Sur une courbe dont tout point est un point de ramification », CRAS 160, 302-305.

Commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

N’hésitez pas à suggérer des ressources complémentaires et éventuellement les envoyer par mail pour qu’elles soient partagées sur le site.

dix-neuf + 4 =