Chameau, Bananes, Oasis

[Dilbert]

Deux oasis A et B sont distantes de 1000 km.

En A, on dispose de 3000 bananes que l'on cherche à transporter au point B à dos de chameau.

Le chameau a deux particularités :

- il ne peut pas porter plus de 1000 bananes à la fois ;

- pour faire 1 km, il doit manger 1 banane.

Combien de bananes au maximum pourra-t-on transporter en B ? (il y a un seul chameau, bien sûr)

Je précise que je n'ai pas la solution…

——————

Je précise aussi que ce problème est mentionné de façon anecdotique à la fin la conférence suivante d'A. Connes (sans la solution) :

http://www.canalu.fr/canalu/chainev2/utls/…onde_quantique/

[Sous-Commandant Marco]

Le chameau est un animal sobre et disposant de réserves (i.e. il peut manger 1000 bananes au début ou à la fin de son voyage). Un aller-retour coûte 2000 bananes mais permet de porter 1000 bananes. Je pense donc que la réponse est 1000.

Je vais de ce pas faire un Business Plan pour le transport de bananes à Dubai.

[Dilbert]

Non, pour chaque km parcouru, il doit manger une banane, sinon c'est trop facile.

[Calembredaine]

une banane. La dernière.

[Julien]

J'ai 400. Qui dit mieux ?

[Dilbert]

une banane. La dernière.

Ben non.

Il n'est pas obligé de faire les 1000 km d'un seul coup. Il peut très bien transporter un certain nombre de bananes à mi-chemin et revenir en A.

[Dilbert]

J'ai 400. Qui dit mieux ?

Moi je suis arrivé à 600 en découpant le trajet en 5 tronçons de 200 km, mais soit je me suis trompé, soit on peut faire mieux.

EDIT: je me suis trompé, ça doit être 400.

Je signale que Connes a trouvé 533 (mais lui, c'est un grand matheux)…

[pankkake]

Donc par exemple il peut faire 250 km, déposer 500 bananes, et revenir à A avec les 250 restantes.

Reste à voir si les 3000 bananes sont suffisantes et quels sont les meilleurs nombres.

[Fredo]

Oui, j'ai eu l'intuition d'un truc dans le genre.

[Calembredaine]

Je signale que Connes a trouvé 533 (mais lui, c'est un grand matheux)…

Ha mince, c'est juste un problème de maths? Pas d'astuce?

L'intérêt s'en trouve très réduit je trouve.

[Dilbert]

Ha mince, c'est juste un problème de maths? Pas d'astuce?

L'intérêt s'en trouve très réduit je trouve.

C'est un problème d'optimisation. Il y a des tas de solutions possibles faciles à trouver, il faut trouver la meilleure.

[Apollon]

416 pour moi

Edit : 500 tout rond

ps il y a un piège, attention aux calculs

[Julien]

Je signale que Connes a trouvé 533 (mais lui, c'est un grand matheux)…

Pour arriver avec 533 bananes :

faire deux aller-retours plus un aller jusqu'au point X, avec AX = 200 km. On a donc amené 2000 bananes en X. On va au point Y, avec AY = 533, en un AR + un aller, on a donc 1001 bananes en Y (1000 - 666 + 1000 - 333). Il ne reste que 467 km à parcourir, avec 1000 bananes.

Comment trouver le résultat :

x et y sont respectivement les distances AX et AY. L'unité pour tous les nombres est en bananes.

Xq et Yq sont les quantités de bananes que l'on amène aux points X et Y.

On se rend en X en 2 AR + 1 aller et de X en Y en 1 AR + 1 aller (pour Y ça n'a pas de sens de faire moins, et faire plus donne de mauvais résultats).

Xq = 3000 - 5x

Yq = Xq - 3 (y-x)

On choisit Yq = 1000, pour maximiser y.

D'où y = 2000-2x / 3 (*)

Donc 3(y-x) = 2000 - 5x --> le nombre de bananes consommées pour aller de X à Y.

Or, le chameau ne portera que 2000 bananes au maximum sur ce trajet et il doit en laisser 1000. On a donc 2000 - 5x <= 1000.

On cherche toujours à maximiser y, donc d'après (*) on doit choisir la plus petite valeur de x pour laquelle l'inéquation précédente est vraie. Ce qui donne x = 200.

Donc y = 533.

[Apollon]

belle mise en équation

[Invité jabial]

En 2 secondes et sans réfléchir, le chameau a besoin de consommer des bananes au retour aussi donc il ne peut en transporter aucune.

Imaginons 5 tronçons de 200km : il prend 1000 bananes, et revient à la case départ en en ayant déplace 600 (1000-200*2). En fait il le fait 3 fois sauf que la dernière fois il ne revient pas à la case départ : il en déplace en tout (1000*3-200*2*2) = 2200. Il a eu besoin de plus d'1/5 des bananes pour faire 1/5 du trajet, ça n'est pas soutenable.

Donc je pense aucune.

[Sous-Commandant Marco]

J'étais personnellement arrivé à 500 avec X = 250 et Y = 500 puis j'ai vainement tenté de démontrer que c'était le maximum.

[Marchange]

En 2 secondes et sans réfléchir, le chameau a besoin de consommer des bananes au retour aussi donc il ne peut en transporter aucune.

Imaginons 5 tronçons de 200km : il prend 1000 bananes, et revient à la case départ en en ayant déplace 600 (1000-200*2). En fait il le fait 3 fois sauf que la dernière fois il ne revient pas à la case départ : il en déplace en tout (1000*3-200*2*2) = 2200. Il a eu besoin de plus d'1/5 des bananes pour faire 1/5 du trajet, ça n'est pas soutenable.

Donc je pense aucune.

Tout pareil, je dirais aucune.

Il doit en consommer à l'aller et au retour…

[h16]

Deux oasis A et B sont distantes de 1000 km.

En A, on dispose de 3000 bananes que l'on cherche à transporter au point B à dos de chameau.

Le chameau a deux particularités :

- il ne peut pas porter plus de 1000 bananes à la fois ;

- pour faire 1 km, il doit manger 1 banane.

Combien de bananes au maximum pourra-t-on transporter en B ? (il y a un seul chameau, bien sûr)

Voici un problème d'optimisation bien adapté pour un algo génétique. Si j'avais le temps … (soupir).

[Apollon]

Julien a démontré que la solution était 533 au-dessus. Il faut lire

[Dilbert]

Bravo à Julien !

Je recopie aussi une réponse intéressante fournie il y a qques heures sur Yahoo Q/R :

On remarque tout d'abord que l'on a intérêt à ne passer que trois fois au point A et qu'à chaque fois, il vaut mieux faire partir le chameau à plein. Partant de là, on sait que le chameau passera 5 fois sur les premiers kilomètres du parcours.

D'où l'idée: faire faire au chameau un premier parcours pendant lequel il dépose 3 bananes à chaque kilomètre pour ses futurs allers-retours, mangeant le reste des bananes en route. On peut ainsi lui faire faire 200 kilomètres aller et retour. Pourquoi 200? Parce que si l'on ne consomme pas 1 000 bananes dans ce premier aller-retour (bananes mangées + réserves), il restera un reliquat au départ que l'on ne pourra pas transporter en deux fois.

Il reste donc 2000 bananes au point A et 3 bananes à chaque kilomètre entre le kilomètre 1 et le kilomètre 200 (inclus).

On peut alors transporter les 2000 bananes restantes au kilomètre 200 en deux voyages.

Pendant son parcours, le chameau aura bien consommé 5*200=1 000 bananes.

Il reste donc à transporter 2 000 bananes sur 800 kilomètres.

On suit le même raisonnement. On dépose 333 bananes aux kilomètres 201 à 533. Durant cet aller-retour, le chameau a consommé 666 bananes.

Il reste donc 1 001 bananes au kilomètre 200. On charge le chameau de 1 000 bananes et on lui fait manger la dernière pour rallier le kilomètre 201 sans entamer sa cargaison.

Le chameau arrive ainsi jusqu'au kilomètre 534 avant d'être obligé de puiser dans sa cargaison.

Il lui restera donc 534 bananes à l'arrivée.

[Apollon]

Bravo à Julien !

Je recopie aussi une réponse intéressante fournie il y a qques heures sur Yahoo Q/R :

Que de blabla pour cacher le vide, l'auteur de cette réponse a manifestement eu les résultats en premier et a vainement essayé de les retrouver : 3/20

[Librekom]

juste au une petite remarque au passage : 1001 - 467 ça fait 534 et non pas 533. mais la question est : est ce que le chameau doit manger une bananne avant de parcourir le premier Km ou pas.

[Etienne]

J'en profite pour poster ce petit problème - tombé à l'oral de l'X -, que j'ai vu sur deux forums différents, ici plutôt que de lancer un autre fil.

On dispose uniquement d'une règle non graduée d'environ 30cm et d'un crayon. On considère deux points distants d'environ 35cm. Comment faire pour tracer la droite qui les relie ? Si les points sont très éloignés, peut-on toujours s'en sortir ?

Dilbert connait peut-être déjà.

[Apollon]

On aligne le crayon à la règle (poser le crayon sur la fin de la règle) pour placer la règle puis on trace la droite.

[Etienne]

On aligne le crayon à la règle (poser le crayon sur la fin de la règle) pour placer la règle puis on trace la droite.

Avec un crayon de longueur inférieure à 5cm.

[WALDGANGER]

J'en profite pour poster ce petit problème - tombé à l'oral de l'X -, que j'ai vu sur deux forums différents, ici plutôt que de lancer un autre fil.

On dispose uniquement d'une règle non graduée d'environ 30cm et d'un crayon. On considère deux points distants d'environ 35cm. Comment faire pour tracer la droite qui les relie ? Si les points sont très éloignés, peut-on toujours s'en sortir ?

Dilbert connait peut-être déjà.

je ne comprends pas trop on ne peut pas tracer d'abaord les 30cms puis les 5 restant en déplançant la règle (ok c'est pas très propre)?

et sinon sur quoi on trace? si c'est du papier avec des pliages on peut le faire aussi

[Apollon]

Etienne tu triches ! bon je suppose qu'on n'a pas le droit de plier la feuille non plus…

Donc autre possibilité: se servir de la règle comme d'un compas pour tracer deux points équidistants des deux premiers points puis calculer la position du centre du nouveau segment grâce à la règle. Ce dernier point est aligné au deux premiers. Ne marche pas au dela de 60 cm d'écart.

[Etienne]

je ne comprends pas trop on ne peut pas tracer d'abaord les 30cms puis les 5 restant en déplançant la règle (ok c'est pas très propre)?

Non, non, il faut que ça fasse une droite proprement. Si on n'a pas le droit aux techniques de rafistolage, en revanche, on peut construire plein de choses jolies avec des paralléles, des points d'intersection, etc. L'idée est de construire un point C qui soit aligné avec A et B et tel que les longueurs des segments [AC] et [CB] soient inférieures (largement) à 30cm.

@ Apollon :

La régle est NON graduée.

[Apollon]

Avec des parallèles ? facile.

On prend un 3e point E au hasard plutot vers le centre puis on trace un 4e point F grace aux parallèles de façon à faire un parallèlogramme entre les 4 points : F est l'intersection de la parallèle à (AE) passant par B et à (BE) passant par A On trace la diagonale avec les deux nouveaux points.

On répète l'opération.

L'intersection des deux segments obtenus est alignée aux deux premiers.

[Coldstar]

Avec des parallèles ? facile.

On prend un 3e point E au hasard plutot vers le centre puis on trace un 4e point F grace aux parallèles de façon à faire un parallèlogramme entre les 4 points : F est l'intersection de la parallèle à (AE) passant par B et à (BE) passant par A On trace la diagonale avec les deux nouveaux points.

On répète l'opération.

L'intersection des deux segments obtenus est alignée aux deux premiers.

Techniquement c'est faisable, mais c'est une solution de tâtonnement. On doit faire mieux.