Optimisation : problème amusant de la traversé du pont

[.:Spip:.]

Bonjour,

C'est l'été , et autant se distraire un peu. je vien sde trouver ce probléme, je le propose (j'ai la solution, bien sur). ceux qui l'on deja fait, merci de ne pas donner la reponse à ceux qui cherche... C'est bien plus sympa.

Problème:
4 voyageurs V1 V2 V3 V4 doivent traverser un pont le plus rapidement possible.
V1 le fait en 1 min,
V2 : 2 mins
V3 : 5 mins
V4 : 10 mins

Le pont ne peut supporter que deux personnes maxi.

il fait nuit. il faut une lampe pour traverser. ils en ont qu'une. Elle doit donc etre ramené par quelqu'un pour que d'autres puissent traverser.

Quel doit etre l'organisation de la traversée ?
> vous devez trouver un temps de 17 mins.

Pour la petite histoire, ce probleme aurait été posé aux recrues de microsoft. la reponse devait etre donnée en - de 5 mins

Bon amusement !!!

Solution et source au moment venu...
-----

[invite19431173]

Mince, je trouve pas mieux que 19...

[invited697311a]

Réponse rapide

6 Minutes
V1 prend V2 sur ses épaules traverse et revient = 2 mn
Il fait de même avec V3 = 2 mn
Il fait de même avec V4 = 2 mn

Bon je vais quand même chercher une solution plus élégante

A+

[invited697311a]

Après reflexion

17 mn

V1 et V2 traservent = 2 mn
V1 revient = 1 mn
V3 et V4 traversent = 10 mn
V2 revient = 2 mn
V1 et V2 traversent = 2 mn

[A voir en vidéo sur Futura]

[invite19431173]

Grrrrrrr !!! J'y avais pas pensé, alors que c'est un problème classique !!!!!! Grrrrrr !!

Bravo en tout cas !

[.:Spip:.]

Après reflexion

17 mn

V1 et V2 traservent = 2 mn
V1 revient = 1 mn
V3 et V4 traversent = 10 mn
V2 revient = 2 mn
V1 et V2 traversent = 2 mn

C'est bien vu bravo !!!!

On peut proposer une démo ...

maintenant :

essayez :
V1 1
V2 3
V3 6
V4 8
V5 12 mins

>29 min.

le cas est interessant car il evite le cas un peu particulier plus haut.

[invited697311a]

V1 et V2 traversent = 3mn
V2 revient = 3 mn
V4 et V5 traversent = 12 mn
V1 revient = 1 mn
V1 et V3 traversent = 6 mn
V1 revient = 1mn
V1 et V2 traversent = 3 mn

Bonne soirée

[.:Spip:.]

V1 et V2 traversent = 3mn
V2 revient = 3 mn
V4 et V5 traversent = 12 mn
V1 revient = 1 mn
V1 et V3 traversent = 6 mn
V1 revient = 1mn
V1 et V2 traversent = 3 mn

Bonne soirée

c'est bien ca.

On s'apercit, que l'on applique dan sun premeir temps la technique pour trouver 17 min dans le premier probleme. Puis la technique de Benjy, ou l'on trouve 19 min.

Donc, pour le cas général, on doit marier les deux techniques.

si ca dit a quelqu'un, je donnerai la demo pour le premier cas, montrant que 17 min est le temsp optimal.
et l'explication du cas gal.


source : pour la science oct 2004 n°324.

[invite3d7be5ae]

Tu ne peux pas nous donner les techniques?
Ce serait amusant de résoudre le cas général...

[.:Spip:.]

voila, je viens de faire un pdf la dessus.