L'éléphant et les bananes
Un planteur de bananes se trouve confronté à un problème bien difficile. Comme moyen de transport, il ne dispose que d'un vieil éléphant qui consomme une banane au kilomètre et n'accepte de porter que 1000 bananes au plus sur son dos. Le plus proche marché se trouve à 1000 km de la plantation. Sa production s'élève à 3000 bananes.
Combien de bananes le planteur pourra-t-il porter au maximum au marché?
"Plus les choses changent et plus elles restent les mêmes..." Snake Plisskein
environ 466
je demontre pas
mon prof de math disait toujours ca suffit de donner un resultat faut demontrer
Peut-il en deposer en chemin ?
--Yankel Scialom
bien sur c est meme obligatoire
aller je trouve 416 mainenant et c est mon dernier mot
au passage une fois vendu je change d elaphant pour un plus economique non mais
salut, oui prgasp77,
il peut en déposer en chemin.....
Ben a mon avis le pauvre planteur de bananes est un peu marron…
Comment fait-il pour retourner à sa plantation ? s’il a vendu ses « x » bananes ? ?
en taxi ??
ps: mille kilometres a pied, ca use, ca uuuse....
Re : L'éléphant et les bananes
Il prend sa retraite avec son éléphant dans son nouveau pays d'adoption.
Comment tu fais pour 466, cricri ?
Il peut en déposer en chemin, les singes sont déjà bien nourris.
"Plus les choses changent et plus elles restent les mêmes..." Snake Plisskein
Salut,
alors moi, je dis : 533 !
Avec le raisonnement suivant : on avance de 1 km en déplaçant tout le tas de bananes, avant de s'attaquer au km suivant.
Selon la taille du tas, il faut plus ou moins d'aller-retours pour deplacer le tas d'un km.
3000 à 2001 : 2 aller-retour (1000 bananes à l'aller, on en pose 998, on en consomme une au retour) + 1 aller (avec celles qui restent) = 5 bananes consommées
2000 à 1001 : 3 bananes consommées
moins de 1000 : 1 banane consommée
pour les 200 premiers km :
consommation = 200*5=1000 bananes
pour les 334 suivants (2000 bananes à 998):
consommation = 334*3=1002 bananes
il reste alors 998 bananes et 1000-200-334 = 466 kilometres à parcourir
en arrivant au marché, il reste alors 998-466 = .....
..... 532 bananes !!!!!
532 ? mais j'ai annoncé 533 !
Ca, c'était l'idée de base. Place à la subtilité.
On peut grapiller une banane en passant du km 533 à 534 ! Il y a alors un tas de 1001 bananes. Partons avec 1000 bananes et ne revenons pas chercher celle qui est toute seule au kilometre 533 (certains diront que c'est gacher de la nourriture, mais on gagne une banane à la fin)
Du coup, on repart du kilometre 534 avec 999 bananes.
Et on arrive au bout avec 533 bananes !!
Maintenant, le raisonnement présente peut-être une faille que je n'ai pas vu.
Et il est peut-etre encore possible d'économiser sur d'autres bananes. A vous de voir !
gascof
Re : L'éléphant et les bananes
De facon generale, quelqu'un connait la maniere dont on resoud les problemes dont la solution est un algorithme plutot qu'un resultat?
Du type:
- Comment arriver avec le minimum de deplacements, de la case A a la case B d'un echiquier en utilisant le cavalier.
- comment deplacer 3000 bananes avec un chameau plutot qu'un elephant
D'accord avec toi Gascof,
sauf que je déplace les tas directement jusqu'à au deux centième kilomètre (2 aller-retour et un aller).
Puis je vais au kilomètre 533 en un aller-retour et un aller.
Je mange la banane - je ne gache pas la nourriture ,-) -.
Et je termine le trajet, ce qui me fait 533 bananes à vendre.
Reste à prouver que c'est l'optimum.
Azt
Re : L'éléphant et les bananes
À l'époque, j'avais trouvé comme azt, mais je pense que la méthode de Gascof peut donner un début d'explication.
On s'arrange pour que l'éléphant soit le plus rentable possible en transportant à chaque km le maximum possible de bananes.
Mais bon, ce n'est qu'une esquisse de compréhension.
"Plus les choses changent et plus elles restent les mêmes..." Snake Plisskein
on charge on fait 200 km on pose 600 on repart on fait ca 3x
donc on a 2000 au km 200
on charge on fait 333 km on pose 334 on repart on fait ca 2x
donc on a 1001 au km 533
on charge on repart on arrive avec 467
comme quoi avec mon 466 j etait pas loin meme si je me souvient plus comment j ai fait
j avais oublier hier qu au dernier voyage on a pas a repartir
eh cricri c'est l'inverse, si on a 1000 bananes après 533 km, on arrive avec 533 bananes à la fin....et non 467, comme tu le dis...
Erreur d'inattention...
arf oui suis hyper fatique la
j etait pourtant sur que la solution 533 etait fausse lol
He!! pourquoi vous vous êtes tous arrêtés?? personne n'a encore trouvé la meilleure solution!!!
il attend que le marche se deplace ?
Re : L'éléphant et les bananes
Je pense qu'on peut raisonnablement considéré que ceux qui ont trouvé 533 bananes ont résolus empiriquement le problème.
Après, on peut ruser pour en amener une 534 ème, Ixi voudra peut-être nous l'expliquer.
En attendant, je suis très intéressé par une preuve de ce résultat que ce soit par une méthode algorithmique ou non.
"Plus les choses changent et plus elles restent les mêmes..." Snake Plisskein
hum, c'est pas une ruse, c'est juste qu'on arrive au km533 avec 1001 bananes et non 1000...puisqu'on met du carburant avant de rouler, on donne la 1001ème banane à l'éléphant, après on parcourt 467km, ce qui fait 534 bananes au marché...
he, doryphore, tu ma laisses la priorité pour te faire pardonner des cordes qui brûlent...?
Pour la preuve, le premier constat est qu'on cherche à toujours faire des voyages à plein chargement, aux arrêts, on a successivement 3000, 2000, 1001 (avec l'astuce) bananes. C'est cette contrainte qui impose logiquement les valeurs 200 et 533km...
Bon, c'est "avec les mains", mais ça vaut ce que ça vaut....
je me lance pour la preuve mathématique...courage ixi!!
On sait qu'il faut déposer des bananes en cours de route.
On sait qu'on va faire 3 voyages puisqu'on a na=3000 bananes au départ (A).
donc au premier arrêt (B), on a nb=3000-5.AB bananes.
il y a alors 3 possibilités:
-il reste moins de 1000 bananes (ie AB>400), on fait le reste en un trajet, donc à l'arrivée (Z), il reste
nz=3000-5.AB-(1000-AB)=2000-4AB.
On optimise nz, on a alors AB=400. et nz=400.
-il reste entre 1000 et 2000 bananes (ie 200=<AB=<400), il faut obligatoirement 2 voyages. 2 possibilités:
on ne fait plus d'intermédiaire: on part au marché avec 1000
bananes, on y arrive avec 1000-AB=400 bananes.
nc=3000-5.AB-3.BC. Ici 2 possibilités:
marché et on vend
nz=3000-5.AB-3.BC-(1000-AB-BC)=2000-4.AB-2.BC
on optimise nz:
si AB augmente de 1, BC diminue de 5/3, donc nz est incrémenté de
(4-10/3)>0
donc il faut d'abord minimiser AB, donc AB=200 et BC =334.
D'où nz=532.
marché et on vend
nz=3000-5.AB-3.BC-(1000-AB-BC)=2000-4.AB-2.BC
on optimise nz:
si AB diminue de 1, BC augmente de 5/3, donc nz est incrémenté de
(-4+10/3)<0.
Donc on minimise AB, ainsi AB=200 et BC=333.
D'où nz=534.
-il reste plus de 3000 bananes en B. j'ai la flemme……
Re : L'éléphant et les bananes
A mon avis, il arrive toujours a la fin avec 0 ou encore moins de banane.
j'ai fait un test et a chaque fois c'est des pinuts.
il y a le retour qui consomme trop.
Re : L'éléphant et les bananes
J'ai rien dit, j eme suis planté:
j'arrive a 500 bananes avec
3 trajets sur 250km de 1000 bananes
puis 1 trajets de 1000 bananes et 1 de 750 sur 250km
et pour finir 1 trajet de 1000 bananes sur 500km.
reste = 500 bananes
Je suis dans le champs ou vous l'êtes tousEnvoyé par doryphore
S'il consomme 1 banane au km, pour faire 2000 km (aller-retour), ça prend pas un bac pour savoir qu'il va consommer 2000 bananes....
Bon maintenant l'énoncé pose une ambiguité : il porte au max 1000 bananes sur son dos, mais peut-être qu'avec un chariot il porte les 3000. Solution 1: Il porte au maximum 1000 bananes au marché.
Solution 2: L'éléphant n'est pas capable de transporter plus de 1000 bananes. Solution 2: 0 bananes
C'est quoi la pogne là-dedans? Ça me fait penser aux exam de mon bac ou j'imaginais l'examen super facile à que j'me ramassais avec 50%
L'astuce, c'est qu'il peut faire des étapes et entreposer des bananes sur son parcours, ça change tout.
"Plus les choses changent et plus elles restent les mêmes..." Snake Plisskein
Peut importe l'astuce, il va quand même consommer 2000 bananes pour faire 2000 kmÀ moins, de créer un trou noir entre son point de départ et d'arriver, mais là c'est un autre histoire. Vraiment, je ne comprend pas ce problème, je l'interprète mal.
Ouais sauf que là il a 3000 bananes et il ne doit faire que 1000 km.Peut importe l'astuce, il va quand même consommer 2000 bananes pour faire 2000 km
Ok, mais ça revient au même, il va donc consommer 1000 bananes.
ben non puisqu'il procède par étape
Voici une ébauche de solution "a priori" (sans utiliser d'astuce):
Pour transporter N bananes sur une distance D, l'éléphant a besoin de parcourir:
* 5 fois la distance D (2 A/R + 1 aller) si 3000 >= N > 2000
* 3 fois la distance D si 2000 >= N > 1000
* 1 fois D si N <= 1000.
L'éléphant consomme alors X.D bananes (X=5, 3 ou 1), et il reste à l'arrivée N-X.D bananes
Ceci étant dit, avec N = 3000 bananes, on se trouve forcément dans l'un de ces 3 cas, quelle que soit la distance parcourue.
La conséquence en est que, si on parcourt une distance D1, puis une distance D2, mais que le nombre de bananes reste dans la même fourchette (définie au-dessus), alors, tout se passe comme si on avait parcouru en une seule fois la distance D1 + D2. On peut donc parcourir les 1000km de trajets avec au plus 2 arrêts.
Il est clair qu'avec aucun arrêt, on ne peut pas parcourir les 1000 km.
On peut chercher dans le cas où on n'a qu'un seul arrêt:
Soit D1 la distance parcourue avant l'arrêt, et N1 le nombre de bananes disponibles au moment de l'arrêt:
N1 = 3000 - 5.D1
On sait déjà que N1 > 2000 n'est pas possible.
Si N1 > 1000, il faudra parcourir 3 fois la distance restante, soit 1000-D1, d'où, à l'arrivée:
NZ = 3000 - 5.D1 - 3(1000-D1) = -2.D1. Il n'y a pas assez de bananes.
Si N1 <= 1000, on doit parcourir 1 fois la distance restante, soit:
NZ = 3000 - 5.D1 - (1000-D1) = 2000 - 4.D1
On prend la valeur minimale de D1 qui respecte la condition N1 = 3000 - 5.D1 <= 1000, soit D1 = 400, et il reste 400 bananes. C'est une solution déjà mentionnée par ixi.
Si maintenant, on envisage 2 arrêts, on appelle D1 et D2 les distances parcourues, et N1 et N2 le nombre de bananes.
Pour les mêmes raisons que précédemment, on doit avoir:
N1 <= 2000 et N2 <= 1000, soit:
N1 = 3000 - 5.D1
N2 = N1 - 3.D2 = 3000 - 5.D1 - 3.D2
NZ = N2 - (1000 - D1 - D2) = 3000 - 5.D1 - 3.D2 - (1000 - D1 - D2) = 2000 - 4.D1 - 2.D2.
On retrouve alors l'optimum pour D1 = 200 et D2 = 334, soit 532 bananes à l'arrivée.
L'astuce de gascof fait le reste.
Geoffrey
:confused: C'est quoi l'affaire......
Si le réservoir de mon auto peut contenir 1000 litres d'essence et que mon auto consomme 1 litre au km. Je peux faire tant d'étape que je voudrai, mais je vais arriver le réservoir vide au marché (situé à 100km)
1000 km excusez
