Bravo

Solution du défi

Réponse : 3282

Explications

On va regarder ce qui se passe quand il y a moins d'arbres intermédiaires (les acajous).

Quand il n'y a aucun acajou intermédiaire, on n'a qu'un espace inter-arbres à franchir. S'il y a 1 acajou, il y a 2 espaces et pour 2 acajous, 3 espaces. Dans les trois cas, le singe peut prendre un nombre de bananes identique au nombre d'espaces et filer tout droit à destination.

Par contre avec n = 3 acajous, ça ne marche pas car il faudrait prendre 4 bananes. Or le singe ne peut en porter que 3. Il faut donc commencer à créer une réserve. Avec 3 bananes comme capacité d'emport, il n'y a pas le choix : il faut prendre 3 bananes, aller sur l'acajou numéro 1, poser une des bananes, puis revenir. Ensuite il suffit de prendre 3 bananes d'aller sur l'acajou 1, de récupérer la banane déposée, on en a alors 3, et de filer vers l'objectif. Consommation totale : 6 bananes. On peut avec un peu de patience voir que toute tentative de dévier de cette suite d'opérations se soldera par une consommation plus grande.

À partir de n = 4 acajous, la solution optimale (en nombre de bananes mangées) n'est plus unique. Cependant on va distinguer une des solutions optimales. Pour cela on va démontrer qu'il y en toujours une solution qui, en plus d'être optimale, procède par une série d'allers-retours (et d'un aller) entre le bananier et le premier acajou, suivie d'une série d'allers-retours (et d'un aller) entre le 1er et le 2e acajou, et ainsi de suite jusqu'au dernier arbre.

Développer la démonstration

On va s'intéresser à tout moment au nombre de bananes disponibles pour le singe, qui est le nombre de bananes qu'il a en main, plus le nombre qui sont posées dans l'arbre.
Pour la démonstration, partons d'abord d'une solution optimale quelconque et supposons qu'elle ne satisfait pas la condition C suivante : tous les allers et tous les retours entre le bananier de départ et le premier acajou se font intialement, avant les voyages entre les autres arbres.
Démontrons d'abord qu'il existe une solution optimale vérifiant la condition C.
Pour plus de clarté numérotons les différent moments où le singe a changé d'arbre lors de son voyage :

moment 0 : bananier,
moment 1 : acajou numéro 1,

etc. Soit A le moment où le singe est pour la première fois au delà du premier acajou. Soit B le premier moment, après A, où le singe est revenu au bananier. En position B−1 et B+1 le singe est sur le 1er acajou, il a donc fait un aller-retour. Soit b le nombre de bananes disponibles au moment B−1. Lors de l'aller-retour, il consomme 2 bananes. On voudrait comparer le nombre de bananes disponibles avant et après cet aller-retour. Ce nombre a forcément augmenté, sinon la solution ne serait pas optimale: on pourrait supprimer l'aller retour et on gagnerait 2 bananes non consommées. Mais la seule façon de revenir avec plus de bananes est de partir de l'acajou numéro 1 banane, prendre 3 bananes au bananier, puis revenir à l'acajou numéro 1 (on a alors gagné 1 banane de disponible sur l'acajou numéro 1).
On peut alors considérer un autre chemin pour lequel on retire cet aller retour entre le moment B−1 et B+1 pour l'effectuer au moment A, tout en laissant le reste identique. La banane ajoutée par l'aller retour se retrouve alors disponible tout le temps jusqu'au moment B+1. Il n'y a donc pas de problème et on a bien toujours une solution.
On recommence alors la manipulation jusqu'à ce que la condition C soit vérifiée.
Soit une solution vérifiant C et considérons son moment A. Il y a un segment initial entre les moments 0 et A où le singe transfère des bananes du bananier à l'acajou numéro 1. Le reste de la solution à partir du moment A est alors nécessairement une solution optimale du problème à n−1 arbres intermédiaires. C'est une solution car le singe ne revient plus sur le bananier et on peut donner au premier acajou le rôle d'un bananier à réserve limitée, mais suffisante. C'est une solution optimale car toute solution plus économe permettrait en la précédent du segment initial de construire une solution plus économe pour le problème à n acajous, or on est parti d'une solution optimale de ce dernier.
On peut donc recommencer avec cette solution du problème à n−1 acajous et la remplacer par une solution optimale vérifiant C. Et on réitère le processus. À la fin on se retrouve avec une solution optimale qui, en plus, vérifie les conditions voulues.

Maintenant que l'on sait cela, on peut déduire la consommation optimale V pour n acajous intermédiaires de la consommation optimale U pour n−1 acajous. Il suffit en effet d'amener U bananes disponibles sur l'acajou numéro 1. Si U est 2 ou moins, le singe prend U+1 bananes au bananier va à l'arbre 1. Consommation de la manip: 1 banane. Consommation totale : U+1. Si U est plus grand que 2, le singe doit faire U−2 allers-retours entre le bananier et l'acajou numéro 1, puis finir par un aller. À chaque fois il doit prendre 3 bananes au bananier. Consommation : 2×(U−2)+1 bananes. Consommation totale : 3×U−3 = 3(U−1).

Pour résumer : si on appelle U(n) l'optimum pour n acajous intermédiaires on a

quand U(n) vaut 2 ou moins alors U(n+1) = U(n)+1 et
quand U(n) vaut 3 ou plus alors U(n+1) = 3×(U(n)−1).

À partir de là, on peut déduire la réponse pour les valeurs successives de n.

n	0	1	2	3	4	5	6	7	8	9
optimum	1	2	3	6	15	42	123	366	1095	3282

La réponse est donc que le singe devra manger au minumun 3282 bananes. Ça fait quand même un sacré paquet.

Retour au calendrier.