Histoire

Pour son deuxième travail, Eurysthée demanda à Hercule de tuer l'Hydre, une sorte de dragon possédant plusieurs têtes et qui hantait les marais de Lerne.

Pour mener à bien sa mission, Hercule, muni de sa seule épée, décida de trancher les têtes de l'Hydre.

La tâche n'était pas si facile et les têtes repoussaient parfois lorsqu'il les coupait. Toutefois, la repousse des têtes de l'Hydre suivait une règle simple, ainsi que la stratégie d'Hercule :

• À chaque coup d'épée, Hercule coupait la moitié des têtes restantes.
• Si après une coupe, il restait un nombre impair de têtes, alors le nombre de têtes restantes triplait instantanément, et une tête supplémentaire repoussait encore.
• Si à un moment l'Hydre ne possédait plus qu'une seule tête, Hercule pouvait l'achever d'un coup d'épée supplémentaire.

Exemple

Si l'Hydre a 6 têtes, Hercule en coupe la moitié au premier coup d'épée. Il en reste 3. Instantanément, le nombre de têtes triple et il en pousse une autre. Il y a maintenant 10 têtes.

Au second coup d'épée, Hercule en coupe 5. Des têtes repoussent, il y en a maintenant 16.

Au 3^e coup d'épée, Hercule coupe 8 têtes. Il en reste 8. Rien ne repousse.

Au 4^e coup d'épée, Hercule coupe 4 têtes, il en reste 4. Rien ne repousse.

Au 5^e coup d'épée, Hercule coupe 2 têtes, il en reste 2. Rien ne repousse.

Au 6^e coup d'épée, Hercule coupe une tête. Il n'en reste plus qu'une.

Le 7^e et dernier coup d'épée permet d'achever l'Hydre.

Si l'Hydre a 6 têtes, Hercule doit donc donner 7 coups d'épée pour la vaincre.

Défi

Le nombre réel de têtes de l'Hydre est donné en entrée. Combien de coups d'épée seront nécessaires pour venir à bout du monstre ?