Le problème du producteur de banane

[Pharaon]

Bonjour à tous,

Voilà, pour une fois, je connais la réponse mais j'aimerais comprendre le développement en utilisant les maths de cette énigme très connue :

"Un producteur de bananes est confronté a un problème délicat : Il a produit 3000 bananes et doit les vendre sur un marché situé à 1000 km. Il dispose pour cela d’un éléphant qui peut porter 1000 bananes au maximum mais qui consomme en continu 1 banane au km (c’est-à-dire, qu’en par exemple 3/7 km, cet éléphant consomme 3/7 de banane) Quel est le nombre maximum de bananes que peut amener ce producteur au marché, sachant qu’il peut disposer des tas intermédiaires sur le chemin?"

Voici le raisonnement sans utiliser les maths:

* L'éléphant part avec 1000 bananes, et fait 200 km il pose 600 bananes et refait le trajet inverse avec les 200 bananes qui lui reste
* il reprend 1000 bananes et refait les 200 km et pose 600 bananes (il en a donc 1200 par terre) et refait le trajet inverse avec les 200 bananes restantes
* il prend les 1000 bananes restantes fait les 200 km prend 200 bananes par terre et fait 333 km de plus, il pose 334 bananes et repart en sens inverse avec les 333 bananes restantes
* il prend alors les 1000 bananes restantes et repart, arriver au kilometre 533 il mange une banane et ramasse les 333 bananes restantes (et en porte alors 1000).
* Grâce à la banane qu'il vient de manger il peut faire 1 km de plus, et se retrouve au kilomètre 534 avec 1000 bananes.
* Il peut alors faire les 466 km restant et arrive donc à destination avec 534 bananes !

Voici le développement en utilisant les math (je ne comprends rien à cette méthodes pouvez-vous me l'expliquer?surtout la où j'ai mis des ???? entre parenthèse et la formule en gras):

Traduction mathématique:
=====================
On peut montrer qu'une stratégie optimale pour porter le maximum de bananes sur (n+1) Km est de porter d'abord un max de bananes au nième Km, puis de porter ces bananes du Km n au Km (n+1) (par plusieurs aller-retours). On peut alors trouver la relation entre U(n+1) et U(n). Nous allons utiliser "les suites définies par une relation de récurrence" pour résoudre cette énigme.

Si Un est le nombre de bananes ainsi transportées au km n, on a:
U0 = 3000
U(n+1) = Un-2*ceil((Un-1001.)/(1002.))-1 (?????????)
(ceil désigne l'entier immédiatement supérieur)

Avec une calculette ou Excel on trouve U1000 = 534 bananes.

Pouvez-vous également me dire comment on calcule cette suite sur Excel?

Et si vous avez une autre méthodes mathématique sur cette énigmes, n'hésiter pas à la mettre en justifiant toutes vos étapes, svp.

Un tout grand merci d'avance de bien vouloir m'aider.

[nodjim]

voir ici http://www.maths-forum.com/showthread.php?t=12183&highlight=banane

[Pharaon]

Bonjour, merci pour ton aide mais la solution optimale est 534 et pas 533 (voir plus haut). Pouvez-vous m'aidez à comprendre ce calcule qui donne la solution optimale:

Si Un est le nombre de bananes ainsi transportées au km n, on a:
U0 = 3000
U(n+1) = Un-2*ceil((Un-1001.)/(1002.))-1
(ceil désigne l'entier immédiatement supérieur)

Un tout grand merci d'avance

[nodjim]

Pas vraiment, je n'ai pas regardé ça de près perso, tant de gens s'y sont intéressés. J'espère que quelqu'un va t'éclaircir tout ça.

[Pharaon]

Bonjour, y-a-il quelqu'un qui arrivera a m'expliquer la formule pour trouver la réponse de cette énigmes en utilisant les suites et en me disant également comment la calculer sur Excel :

Si Un est le nombre de bananes ainsi transportées au km n, on a:
U0 = 3000
U(n+1) = Un-2*ceil((Un-1001.)/(1002.))-1
(ceil désigne l'entier immédiatement supérieur)

Merci d'avance

[nodjim]

Bon, j'ai réfléchi un peu sur le problème, et j'obtiens bien le résultat annoncé.
La stratégie est la suivante: transporter les 3000 kgs jusqu'à une distance telle que, à la fin de l'opération, il reste juste 2000 kgs. Ensuite transporter ces 2000 kgs jusqu'à une distance telle que, à la fin de cette opération, il reste juste 1000 kgs. Finir le voyage avec ce seul chargement.

[Pharaon]

Bonjour, dans ton raisonnement que veut dire kgs? Sinon je suis d'accord.

En fait j'aimerais juste comprendre ce développement mathématique qui donne la solution optimale: U(n+1) = Un-2*ceil((Un-1001.)/(1002.))-1
Parce que j'arrive à la résoudre sans les maths mais mon but est d'arriver à la résoudre en les utilisant car j'adore les maths. Ce qui m'énerve c'est que je n'arrive pas à traduire cette énigme en langage mathématique (équation,...). C'est pour ça que je vous demande de l'aide.

Pouvez-vous m'aider? Encore merci d'avance

[Pharaon]

Bonjour à tous,

J'ai trouvé dans d'autres sites ce qui a permis de trouver la formule mais je comprend pas comment on est passé de:

"Conditions:
1) si U(n)<=1001 , alors un seul voyage suffit pour transporter le stock restant ( grace à l'astuce de la banane mangée avant de partir )
et donc
U(n+1)=U(n)-1 ( une banane perdue par km parcouru )

2) si 1001et on retrouve donc
U(n+1)=U(n)-3 ( une banane perdue à chaque km sur deux aller et un retour )

3) enfin si 2002U(n+1)=U(n)-5 ( trois allers et 2 retours )"

à cette formule qui permet de satisfaire ces trois conditions en une seule écriture "U(n+1)=U(n)-2*ceil((Un-1001.)/(1002.))-1"

Ensuite pouvez-vous me dire comment on calcule cette formule:
"U(n+1)=U(n)-2*ceil((Un-1001.)/(1002.))-1"
si possible avec excel sinon par calcule écrit?

Un tout grand merci d'avance.

[Pharaon]

Bonjour à tous,

On m'a enfin donné une réponse par mail et la formule précédente est fausse, je vous explique comment on a trouvé la nouvelle formule:

Voici une formule qui généralise toutes les conditions:

1001*i > ou = U(n) (=) i > OU = U(n)/1001 (ici on ne change pas le signe de l'inéquation car 1001 est positif)

Or i appartient à l'ensemble des naturels {0,1,2,3...., (i-2),(i-1),i} et indique le nombre de voyages pour transporter le plus de bananes au km n.

Donc on peut réécrire ces conditions par la formule suivantes:
i = ceil(U(n)/1001) = arrondi.sup(U(n)/1001;0)
(le ";0" indique qu'on demande un nombre appartenant à l'ensemble des naturels)

Maintenant pour résoudre cette énigme on va utiliser la formule suivante:
U(n+1)= U(n)-2*i+1

Or nous connaissons la valeur de i.

Il suffit de la remplacer dans l'équation: U(n+1) = U(n)-2*ceil(U(n)/1001)+1
On peut aussi l'écrire: U(n+1) = U(n)-2*arrondi.sup(U(n)/1001)+1

Pour vous montrer qu'elle est vraie essayons de répondre aux questions suivantes:

1)combien de bananes au maximum le planteur pourra t-il placer sur le marché avec 5000 bananes?
2)reprendre la même question avec 3000, 10000 bananes, 15000 bananes et 25000 bananes
3) calculer le coefficient de perdition pour chaque cas. Après ça, que peut-on conclure quant au coefficient de perdition lorsque le nombre de bananes augmente?

Réponse:
1) Si nous avons 5000 bananes = U(0) et que nous calculons cette suite sur excel ou sur une calculette vous obtiendrez, U(1000)= 788

Avec Excel vous mettez dans la case A1, la valeurs de U(0)
Puis dans la case A2 vous mettez: =A1-2*arrondi.sup(A1/1001;0)+1
Ensuite, vous allez en bas à droite de la case A2, ça se transforme en petite croix noir, et vous faites un cliquer-glisser jusqu'à A1001

2) A) avec 3000= U(0), on aura U(1000)=534
B) avec 10000, on aura U(1000)= 1400
C) avec 15000, on aura U(1000)= 2012
D) avec 25000 bananes, on aura U(1000)= 3406

3) D'abord le coefficient de perdition (CP) c'est le nombres de bananes consommées par l'éléphant sur le nombre de bananes produites:

A) avec 5000 bananes: CP = 5000-788/ 5000 (=) CP = 4212/5000
B) avec 3000 bananes: CP = 3000-534/ 3000 (=) CP = 2466/3000
C) avec 10000 bananes: CP = 10000-1400/ 10000 (=) CP = 8600/10000
D) avec 15000 bananes: CP = 15000-2012/ 15000 (=) CP = 12988/15000
E) avec 25000 bananes: CP = 25000-3406/ 25000 (=) CP = 21594/25000

Par contre est-ce que quelqu'un a une idées pour la conclusion du CP? Êtes-vous d'accord avec ce que j'ai mis?

Un tout grand merci d'avance

[Doraki]

C) avec 15000, on aura U(1000)= 2012

Je suis pas d'accord : on peut apporter 2013 bananes avec seulement 14989 bananes au départ :

On part de 14989 bananes.
On fait 29 voyages de 34 km pour apporter 14003 bananes au kilomètre 34
On fait 27 voyages de 37 km pour apporter 13004 bananes au kilomètre 71
On fait 25 voyages de 40 km pour apporter 12004 bananes au kilomètre 111
On fait 23 voyages de 44 km pour apporter 10992 bananes au kilomètre 155
On fait 21 voyages de 47 km pour apporter 10005 bananes au kilomètre 202
On fait 19 voyages de 53 km pour apporter 8998 bananes au kilomètre 255
On fait 17 voyages de 59 km pour apporter 7995 bananes au kilomètre 314
On fait 15 voyages de 66 km pour apporter 7005 bananes au kilomètre 380
On fait 13 voyages de 77 km pour apporter 6004 bananes au kilomètre 457
On fait 11 voyages de 91 km pour apporter 5003 bananes au kilomètre 548
On fait 9 voyages de 111 km pour apporter 4004 bananes au kilomètre 659
On fait 7 voyages de 143 km pour apporter 3003 bananes au kilomètre 802
On fait 5 voyages de 198 km pour apporter 2013 bananes au kilomètre 1000

Si C est la capacité de l'éléphant (en bananes),L est la distance (en km),
et K est la consommation (en bananes par km),

On peut montrer qu'asymptotiquement, le rendement est e^-(2KL/C)
(bananes apportées / bananes initiales)

[Ben314]

Perso, façe à l'énoncé, une question me "titille" :
Visiblement, on considère que l'éléphant, si son estomac est vide, peut manger une banane "au départ" d'un trajet en plus des 1000 qu'il a sur le dos.
Mais, s'il lui reste 1/3 de banane dans son estomac, peut-il en manger 2/3 pour faire "le plein" et en laisser 1/3 sur la route qu'il mangera plus tard ?

Si la réponse est oui, alors la soluce proposée n'est pas optimale, car elle présupose que l'éléphant ne fait des arrêts que lorsqu'il a parcouru un nombre entier de kilomètres or, l'optimum consiste à faire des arrêts à des nombres non entiers de kilomètres...

[Ben314]

Bon, je donne ma réponse (en supposant qu'il peut manger des bouts de bananes et que son extomac à une contenance de une banane) :

Départ : Il charge 1000 bananes (reste 2000 par terre) fait 199.6Km (il a bouffé 200 bananes et il lui reste 0.4 dans l'estomac), pose 600 bananes (il lui en reste 200 sur le dos) et revient au départ (il a bouffé les 200 bananes et il lui reste 0.8 dans l'estomac)

Il recharge 1000 bananes (reste 1000 par tere) fait 199.6Km (il en a bouffé 199 et il lui reste 0.2 dans l'estomac), pose 601 bananes (1201 par terre et il lui en reste 200 sur le dos) et revient au départ (il a bouffé les 200 bananes et il lui reste 0.6 dans l'estomac)

Il charge les dernières 1000 bananes et fait 199.6Km (il en a bouffé 199 et il a l'estomac vide)

Il complète son stock en chargant 199 bananes et il en bouffe une (il en reste 1001 par terre), fait 333+2/3Km (il a bouffé 333 bananes de plus et il lui reste 1/3 dans l'estomac), il bouffe 1/3 de banane et en pose 333+2/3 par terre (il en a 333 sur le dos et 2/3 dans l'estomac) et retourne au tas de 1001 banane (à 333+2/3Km donc il arrive l'estomac vide)

Il bouffe une banane, charge les 1000 autres et refait 333+2/3Km pour retomber sur le tas de 333+2/3 bananes (il a bouffé 333 bananes de plus et il lui reste 1/3 dans l'estomac), il bouffe les 2/3 de banane (estomac plein) et charge les 333 restantes (donc 1000 sur le dos)

A ce stade, il a fait 199.6+333+2/3=533+4/15Km et il lui reste 466+11/15Km à faire et il va bouffer 465+11/15 bananes de plus (évidement, pour les dernier 11/15Km , il ne mange que 11/15 de banane !!!)
Il pose donc 1000-(465+11/15)=534+4/15 bananes au marché, ç'est à dire un enooooorme exédent de 4/15 banane par rapport à son copain qui c'est obstiné à ne s'arrêter qu'à des kilomètres entiers.

[carzou]

Oui, à l'évidence il y a une petite imprécision dans l'énoncé.
Si l'on considère que l'éléphant ne peut porter que 1000 bananes, il ne peut en avoir 1000 sur le dos et une dans l'estomac ... Si N est le nb de bananes restantes, il consomme donc pour porter le tout
5 bananes au km si N > 2000 (cas 1)
3 bananes au km si N > 1000 (cas 2)
1 banane au km si N <= 1000 (cas 3)
Il parcourt donc (3000-2000)/5=200 km dans le cas 1 et (2000-1000)/3=333 km 1/3 dans le cas 2, il arrive donc au bout avec 533 1/3.

La solution de Ben implique que l'éléphant peut en fait porter 1001 bananes, les consommations sont alors
5 bananes au km si N > 2002
3 bananes au km si N > 1001
1 banane au km si N <= 1001
Il parcourt donc (3000-2002)/5=199.6 km dans le cas 1 et (2002-1001)/3=333 km 2/3 dans le cas 2, il arrive donc au bout avec 534 4/15

[Ben314]

Tout à fait d'accord : mon interprétation du problème peut être considérée comme éronée, mais alors celle là :

...
* il prend alors les 1000 bananes restantes et repart, arrivé au kilomètre 533 il mange une banane et ramasse les 333 bananes restantes (et en porte alors 1000)
...

et tout aussi éronée...

Il y a aussi une deuxième ambiguité dans l'énoncé, c'est de savoir si l'éléphant peut manger un morceau de banane et poser le reste par terre (pour le manger plus tard).
Si oui, cela donne comme optimum le 533+1/3 de la soluce 2 que tu propose

[beagle]

"Si l'on considère que l'éléphant ne peut porter que 1000 bananes, il ne peut en avoir 1000 sur le dos et une dans l'estomac ... "

porter c'est porter
apporter d'un endroit à un autre,
avec conservation de la masse.


et manger , digérer n'est pas porter.
On va pas faire un cours de digestion, et savoir combien l'éléphant ch.. de bananes digérées au km non plus.

[Ben314]

O.K., mais de toute façon, il y a un problème "d'estomac" : s'il avait un énorme estomac, il en boufferait 2000 au départ, en chargerait 1000 et arriverais avec 1000 au marché (et en plus, il pourrait revenir à la maison...)
Sauf que le "il consomme en continu 1 banane au km" dit clairement que... c'est pas comme ça que ça marche...
Par contre, (en ce qui me concerne), je trouve que c'est pas super clair la façon dont il consome les bananes...

[beagle]

"c’est-à-dire, qu’en par exemple 3/7 km, cet éléphant consomme 3/7 de banane"
Pour moi c'est clair la façon dont il bouffe la banane.
c'est un gourmet qui bouffe une banane en 1 km, en quasi perfusion puisque c'est continu.Donc les fractions marchent.

Ce qui est effectivement ambigüe, je n'avais pas vu effectivement, c'est de savoir si la partie de banane non encore consommée est portée ou non.
assurément elle est portée à la bouche,mais il la tient avec sa trompe?
et on considère qu'il peut avoir 1000 bananes seulement sur le dos?

[carzou]

Pour moi c'est comme si on avait une voiture avec un réservoir d'1 litre (que l'on peut remplir partiellement), et un jerrican de 1000 litres, et que la voiture ne puisse avoir plus de 1000 litres à bord (réservoir + jerrican)

[beagle]

Pour moi c'est comme si on avait une voiture avec un réservoir d'1 litre (que l'on peut remplir partiellement), et un jerrican de 1000 litres, et que la voiture ne puisse avoir plus de 1000 litres à bord (réservoir + jerrican)

finalement oui,t'as raison,c'est encore le mieux.
1000 bananes au départ sur le dos, mais pour démarrer faut déjà entamer une des 1000 bananes,OK.

[Ben314]

Et est-ce que l'on peut posser des portion de bananes par terre ?