Hercule 4 : Le sanglier d'Érymanthe

Histoire

Pour son 4e travail, Eurysthée demanda à Hercule de capturer vivant le sanglier d'Érymanthe. Gigantesque, celui-ci dévastait avec rage le nord-ouest de l'Arcadie.

La force du sanglier était telle qu'Hercule dût faire preuve de ruse. Il remarqua que tous les jours, le sanglier empruntait la même route, longue de 60 mètres, qu'il parcourait en faisant des bonds dont la longueur suivait une certaine logique : le premier bond du sanglier géant faisait toujours un mètre. Puis, chaque nouveau bond pouvait faire la même longueur que le précédent, deux mètres de plus, ou deux mètres de moins. Toutefois le sanglier ne revenait jamais sur ses pas (pas de bond de longueur négative), et tout au long de sa course, il se refusait à faire plus de deux bonds de la même longueur.

Un jour, par exemple, il fit des bonds de cette longueur :

(1, 1, 3, 5, 7, 5, 7, 9, 11, 11)

Hercule fit un schéma de la course du sanglier et divisa les 60 mètres à parcourir en 61 cases numérotées de 0 à 60. Il repéra les cases où le sanglier avait atterri. Il s'agissait des cases :

(0, 1, 2, 5, 10, 17, 22, 29, 38, 49, 60)

Quelle que soit la course du sanglier, elle commençait toujours par les cases 0, 1, et se terminait toujours exactement sur la case 60. Par contre, les cases empruntées en chemin variaient.

Défi

Hercule se mit alors en tête de creuser des trous aux endroits où le sanglier était obligé de passer, pour le piéger. Il lui aurait été très simple de creuser dans la case 1, ou dans la case 60, il était sûr que, quelle que soit la séquence de bonds effectuée par le sanglier, celui-ci allait nécessairement y passer. Mais tout n'est pas si simple et le sol du mont Lampéia n'est pas très meuble. Hercule se rendit vite compte qu'il ne pourrait creuser que dans la zone sablonneuse comprise entre les cases 20 et 40 incluses.

Mais où creuser ?

Quelle que soit la case choisie entre 20 et 40, Hercule réalisa que le sanglier avait la possibilité de ne pas tomber dans son piège. Même chose en creusant 2 trous. Où que ces deux trous soient placés, le sanglier aurait eu la possibilité de passer.

Aidez Hercule et indiquez-lui les numéros des cases où creuser de manière à ce que le sanglier tombe nécessairement dans un des trous. Les trous ne peuvent être situés que dans la zone sablonneuse située entre les cases 20 et 40 (incluses). Attention, creuser est un travail difficile (même pour Hercule) et vous devez indiquer une solution qui fonctionne avec le moins de trous possible !

Ce problème est tiré de c0d1ng UP 2015

Type de retour

une séquence de nombres entiers

Entrée du problème

Pas de donnée d'entrée

Formulaire de réponse

Vous devez être connecté pour pouvoir répondre aux défis

Tags : cup15 combinatoire récursivité