Héraclès ne pouvait pas perdre!

I. Introduction

Après avoir terrassé le lion de Némée, Héraclès reçoit d’Eurysthée son deuxième travail : purger les marais de Lerne d’une créature terrifiante engendrée par Typhon et Échidna : l’Hydre.

Lorsqu’il arrive dans le marécage, le héros fait face à un monstre dont la structure dépasse tout ce qu’il a pu imaginer. L’Hydre n’est pas un simple serpent à plusieurs têtes : c’est un véritable arbre vivant dont les cous se bifurquent, formant des nœuds complexes avant d’aboutir à des têtes menaçantes.

Armé de son glaive, Héraclès s’élance. Mais à chaque tête tranchée, d’autres repoussent. Voyant le monstre se démultiplier sous ses yeux à une vitesse vertigineuse, Héraclès se demande: peut-il se battre éternellement, ou bien finira-t-il obligatoirement par terrasser le monstre?
Héraclès et l'Hydre de Lerne, 1875-76, Gustave Moreau

II. Modélisation du combat

On modélise le combat de la manière suivante:

On considère une Hydre constituée d’un corps sur lequel poussent plusieurs cous. Chaque cou mène soit à une tête, soit à un nœud qui mène lui même à un ou plusieurs autres cous.
Héraclès combat l’Hydre. À chaque attaque, Héraclès décapite une tête de l’Hydre.
Si cette tête est sur le corps, alors elle meurt et rien d’autre ne se passe. Sinon, $n$ nouvelles têtes repoussent, où $n$ est le nombre de têtes déjà décapitées. Les têtes repoussent en suivant les règles suivantes :

Les têtes ne peuvent repousser que sur le corps ou sur l’un des nœuds qui mènent à la tête décapitée.
Aucune tête ne peut repousser sur le nœud directement lié à la tête décapitée.
Enfin, les cous ne menant à aucune tête meurent.

Montrer que quelle que soit la stratégie adoptée par Héraclès, il vaincra l’Hydre de Lerne.

I solved itMark it done Add to my listKeep it in your list

I like this problem0 likes

Solutions

Reveal solutionsAre you sure? Give it a try first.

Solution by Uettechat

Discussions0 useful votes

Supposons par l’absurde que le combat ne se termine pas.

Considérons $(w_n)_{n\in\mathbb{N}}$ la suite du nombre de nœuds internes après la $n$ -ième attaque. D’après la modélisation, aucun nœud interne n’est jamais créé, donc $(w_n)_{n\in\mathbb{N}}$ est décroissante. Or toute suite décroissante d’entiers naturels est stationnaire. Il suffit donc de montrer que $(w_n)_{n\in\mathbb{N}}$ ne peut pas être stationnaire pour obtenir une contradiction.

Soit $q$ un nœud interne de profondeur maximale. Lorsqu’Héraclès coupe une tête enfant de $q$ , les nouvelles têtes repoussent strictement plus près du corps et en particulier aucune ne repousse sur $q$ . Ainsi le nombre de têtes enfants de $q$ ne peut que décroître. Puisque les têtes repoussent toujours à profondeur strictement inférieure à celle de la tête coupée, et que la profondeur est bornée inférieurement par $0$ (le corps), toute lignée de repousses finissent nécessairement par repousser sur le corps. Or une tête sur le corps est coupée sans repousse, donc toute lignée de repousses s’éteint en un nombre fini d’étapes. Il ne peut donc y avoir qu’un nombre fini d’attaques consécutives n’impliquant pas les têtes de $q$ . Puisque le combat est supposé infini, ce processus se répète indéfiniment, mais le nombre de têtes de $q$ étant fini et ne pouvant que décroître, Héraclès finit par couper toutes les têtes de $q$ , qui est alors élagué : $(w_n)_{n\in\mathbb{N}}$ a strictement décru à partir d’un certain rang. Donc $(w_n)_{n\in\mathbb{N}}$ ne peut pas être stationnaire, ce qui est absurde.

Donc le combat se termine.

Report