Mots-clés : théorie des nombres, graphe, combinatoire, convergence, simulation, modélisation, grand nombre.
Ce problème est tiré d’un article intitulé On Jargon, Hercules and the Hydra écrit par Michael E. Mytilinaios du département de mathématiques de l’Université de Crète. Le texte explicatif est tiré du livre La Mythologie d’Edith Hamilton. Pour commencer, il est intéressant de relire la mythologie grecque :
« Hercule était l’homme le plus fort de la terre et il possédait cette suprême confiance en soi que donne une magnifique vigueur physique. Il s’estimait l’égal des dieux — et non sans quelque raison.
» Il naquit à Thèbes et longtemps on le crut fils d’Amphitryon, un stratège fort distingué. Il fut d’abord appelé Alcide ou descendant d’Alcée, père d’Amphitryon. Mais en réalité il était le fils de Zeus, qui vint trouver Alcmène, femme d’Amphitryon sous la forme de son mari alors que le stratège était à la guerre. Elle mit au monde deux enfants, Hercule, fils de Zeus et Iphiclès, fils d’Amphitryon. L’origine différente des jumeaux se manifesta clairement dans leur réaction devant un grand danger qui les menaça, alors qu’ils n’avaient pas atteint leur première année. Héra, comme toujours, était furieusement jalouse et elle avait résolu de tuer Hercule.
» Un soir, Alcmène baigna les enfants, les nourrit et les déposa dans leur berceau ; elle les caressa, leur murmura de tendres mots : « Dormez, mes tout-petits, âmes de mon âme. Que votre sommeil soit heureux et votre réveil aussi. » Elle balança le berceau et les bébés s’endormirent. Mais au plus sombre de la nuit, alors que tout était silencieux dans la maison, deux grands serpents se glissèrent dans la chambre des enfants ; une lumière y brillait, les deux reptiles se coulèrent dans le berceau, têtes et langues oscillantes, et les enfants se réveillèrent. Iphiclès cria et tenta de fuir le berceau, mais Hercule se dressa et saisit les deux mortelles créatures par le cou. Elles se contorsionnèrent, enroulèrent leurs anneaux autour de son corps mais il ne lâchait pas prise. La mère entendit les cris d’Iphiclès et appelant son époux, elle se précipita dans la chambre. Elle y trouva Hercule, assis et riant aux éclats, tenant dans chacune de ses mains un long corps flasque et mou. Joyeusement, il les tendit à Amphitryon. Ils étaient morts. Tous comprirent alors que l’enfant était destiné à de grandes choses. (...)
» On prit grand soin de son éducation, mais lui enseigner ce qu’il refusait d’apprendre était tâche dangereuse. Il paraît ne pas avoir aimé la musique qui cependant tenait une grande place dans l’éducation d’un adolescent grec — ou peut-être n’éprouvait-il qu’antipathie pour son professeur en cet art. Il se mit un jour en colère contre lui et lui fracassa la tête avec son luth. C’était la première fois qu’il donnait un coup fatal sans en avoir l’intention. Jamais il n’avait eu le dessein de tuer l’infortuné musicien ; sous l’impulsion du moment, il frappa sans réfléchir, à peine conscient de sa force. Il en fut sincèrement désolé, ce qui ne l’empêcha pas de recommencer encore et encore. (...)
» Combattre et vaincre les Myniens qui taxaient les Thébains d’un lourd tribut fut son exploit suivant. Les citoyens reconnaissants lui offrirent en récompense la main de la princesse Mégarée. Il lui fut fort attaché ainsi qu’aux enfants qu’il en eut, et cependant il dut à ce mariage le plus grand chagrin de sa vie, sans compter une suite de dangers et d’épreuves comme personne n’en connut avant ou après lui.
» Quand Mégarée lui eut donné trois fils, il devint fou. Héra, qui n’oubliait jamais une offense, le frappa de démence. Il tua ses enfants ainsi que Mégarée qui tentait de protéger le plus jeune. Puis la raison lui revint. Il se retrouva dans une salle de sa demeure tout éclaboussée de sang, et autour de lui gisaient les cadavres de ses fils et de sa femme. De ce qui s’était passé, comment ils étaient tous morts, il n’avait aucune idée. Il croyait se souvenir qu’un moment plus tôt, ils parlaient tous ensemble. Terrifiés, les témoins du drame qui observaient son trouble à distance, virent que la crise était passée et Amphitryon osa s’en approcher. On ne pouvait cacher la vérité à Hercule, il devait l’apprendre, si atroce fût-elle et Amphitryon se chargea de la lui dire. Hercule l’écouta ; puis il dit : « Ainsi je suis moi-même le meurtrier de ceux que j’aimais le plus au monde. » (...)
» Il avait tué sa famille ; il était donc souillé et souillait les autres ; il méritait d’être pour tous un objet d’horreur. A Delphes où il se rendit pour consulter l’oracle, la prêtresse le confirma dans ce sentiment. Il devait se purifier, lui dit-elle, et il ne pourrait y parvenir qu’en faisant sévèrement pénitence. Elle lui ordonna donc de se rendre chez son cousin Eurystée, Roi de Mycènes et de se soumettre à tout ce que celui-ci exigerait de lui. Hercule prêt à tout ce qui lui rendrait les mains nettes, partit docilement. Il appert clairement du reste de l’histoire que la Pythie connaissait Eurystée et savait qu’il se chargerait sans la moindre faiblesse de purifier Hercule.
» Cet Eurystée n’était certes pas stupide mais il témoignait d’un esprit fort inventif ; lorsque l’homme le plus fort de la terre se présenta devant lui et lui proposa humblement d’être son esclave, il imagina une série de pénitences qui, du point de vue du danger et de la difficulté, n’auraient pu être plus ingénieuses. A sa décharge, il doit être dit qu’Héra l’aidait et l’exhortait ; jusqu’à la fin de la vie d’Hercule, elle en voulut à celui-ci d’être le fils de Zeus. Les tâches imposées par Eurysthée au héros sont appelées les « Travaux d’Hercule ». On en compte douze, dont aucun ne paraît réalisable.
» Le premier fut de tuer le lion de Némée (...) Le second fut de se rendre à Lerne pour y tuer un monstre à neuf têtes appelé l’Hydre, qui vivait dans une mare des alentours. C’était une entreprise des plus difficiles car l’une des têtes était immortelle et les autres terrifiantes : lorsqu’on en coupait une, deux autres naissaient à sa place. Hercule fut aidé par son neveu Iolas, qui lui apporta un tison enflammé avec lequel il cautérisa les cous au fur et à mesure qu’il tranchait les têtes, empêchant ainsi celles-ci de repousser. Quand toutes furent abattues, il se défit sûrement de celle qui était immortelle en l’enfouissant sous une grande roche. »
Une autre version donne l’explication suivante :
« Comme le lion de Némée, l’Hydre de Lerne est un monstre, fils d’Eschidna, mais elle a pour père Typhon. Elle fut élevée par Héra pour servir d’épreuve à Héraclès. La déesse l’éleva, précise-t-on sous un platane, près de la source Amymoné. Cette hydre est représentée comme un serpent à plusieurs têtes. Le nombre de celles-ci varie, de cinq ou six jusqu’à cent, selon les auteurs. Parfois même ces têtes passaient pour être des têtes humaines. L’haleine qu’elle soufflait par ses gueules était si mortelle que quiconque l’approchait, même pendant son sommeil, mourait infailliblement. Elle exerçait aussi ses ravages sur les récoltes et les troupeaux du pays. Pour la combattre, Héraclès eut recours à des flèches enflammées. On dit aussi qu’il coupa ses têtes avec une harpé (sorte de sabre courbe). Il fut aidé dans son exploit par son neveu Iolaos. Aide d’autant plus nécessaire que chaque tête coupée repoussait. Pour empêcher les têtes de repousser, Héraclès demanda à Iolaos de mettre le feu à la forêt voisine, et, à l’aide des brandons, brûlait chaque fois la blessure, rendant ainsi les chairs incapables de renaître. La tête du milieu, disait-on parfois, était immortelle. Héraclès la coupa cependant, et l’enterra ; puis il plaça par-dessus un énorme rocher. Enfin, il trempa ses flèches dans le venin de l’hydre (ou dans son sang), et ainsi les empoisonna.
» Dans sa lutte contre Héraclès, Héra avait envoyé un allié à l’hydre, sous la forme d’une écrevisse géante qui mordit le héros au talon ; mais celui-ci l’écrasa.
» Les mythographes ont présenté une interprétation evhémériste (evhémérisme : conception selon laquelle les personnages de la mythologie sont des êtres humains divinisés après leur mort) du mythe de l’hydre de Lerne. Ils disent que l’hydre aux têtes renaissantes est en réalité le marais de Lerne, asséché par Héraclès. Les têtes sont les sources qui réussissaient toujours à filtrer et rendaient les efforts de celui-ci inutiles. Une autre interprétation prétend que Lernos était en réalité un roi du pays, dont la ville s’appelait Hydra. Lernos était entouré de cinquante archers. Quand l’un de ceux-ci tombait, un autre le remplaçait aussitôt. Et c’est là ce qui aurait donné naissance à la légende des têtes renaissantes. »
On désire modéliser mathématiquement la bataille avec l’hydre. L’intérêt ultime est toutefois assez éloigné des applications des batailles de la mythologie — il réside dans la théorie des nombres. Une hydre est un arbre fini, qui est un ensemble d’arcs joignant chacun deux nœuds, de sorte que chaque nœud est connecté par un chemin unique d’arcs à un nœud fixe appelé racine. Une feuille de l’arbre est un nœud avec un seul arc (et qui n’est pas la racine). Une tête de l’hydre est une feuille de l’arbre avec son arc.
Une bataille entre Hercule et une hydre (ou plusieurs) donnée(s) peut se décrire par les étapes suivantes : l’hydre a la possibilité de se régénérer de façon de plus en plus forte à chaque fois qu’une tête est coupée. Lors du premier coup, l’hydre perd une tête et une copie de l’hydre restante apparaît. Lors du deuxième coup, une hydre perd une tête et deux copies de l’hydre restante apparaissent. Au dixième coup, une hydre perd une tête, alors dix copies apparaissent et ceci continue. De plus, les coups sont comptés et valables pour toutes les hydres. Lorsqu’une hydre à une tête reçoit un coup, elle disparaît.
Pour compliquer l’histoire, la jalouse Héra force Hercule à couper les têtes dans l’ordre le pire possible, de sorte qu’il mette le plus de temps pour détruire les hydres.
Le problème consiste à modéliser l’Hydre de Lerne et à utiliser l’ordinateur pour simuler la bataille. En considérant qu’Hercule soit capable de couper une tête à chaque seconde, combien de temps lui sera nécessaire pour venir à bout d’une hydre à quatre têtes ?
Utilisez une matrice pour représenter la situation à chaque étape : chaque élément de la matrice représente le nombre de têtes de l’hydre.
A chaque étape, il suffit de rechercher la valeur minimale puis d’ôter une tête.
Attention, les nombres viennent vite très grands. Pour éviter d’allonger les temps de calcul, il faut user d’astuce (par exemple, simplifier lorsque les hydres n’ont qu’une seule tête).
La solution actuellement proposée est donnée par les fichiers MatLab : hydre.m et hydreDemo.m.