Cet énigme aura sans doute un air de déjà vu, c'est un grand classique qui a été proposé il n'y a pas longtemps, mais quand même, je prend le risque de me faire "asher" menu menu :
Quatre personnes veulent traverser un pont en pleine nuit. Ils ne disposent que d'une seule torche, et le pont est fragile, il ne peut supporter que le poids de deux personnes. Le pont est troué par endroit, et il serait suicidaire d'essayer de le traverser sans rien voir.
Parmi les quatre personnes il y a :
-Une jeune elfe très agile qui peut traverser le pont en 2 minutes. -Un mage endurant qui peut traverser le pont en 4 minutes. -Un guerrier qui, encombré par son armure, met 12 minutes pour traverser le pont. -Un nain bourru qui a le vertige, lui met 20 minutes à traverser.
Comment feront nos héros pour traverser ce pont en un minimum de temps ?
Certes c'est un classique, mais quelqu'un du forum (je n'ai pas retrouvé où ) a dit que de temps en temps, ça ne fait pas de mal de réviser ses classiques.
Tous le monde à dit que c'était trop facile, tous le monde connais, mais tous ceux qui ont donnés une réponse, ont donnés une réponse fausse.
Donc révisons nos classiques, le temps minimum n'est pas 40 minutes.
Question bonus 1 : Et puisque c'est un classique, allons-y pour le cas général où le temps des personnages est a, b, c, et d (avec a < b < c < d) ?
Question bonus 2 : Et si au lieu d'avoir 4 personnages, il y a [latex]n[/latex] personnages dont les temps respectifs sont [latex]a_1,\ldots, a_n[/latex] avec [latex]a_1 <\ldots < a_n[/latex] ??
2 et 4 font le trajet => 4 min 2 revient => 6min 12 et 20 font le trajet => 26 min 4 revient => 30 min 2 et 4 font le trajet => 34 min TOTAL = 34 min (j'espère avoir été clair dans l'explication)
1) elfe et mage traverse => 4 min l'elfe revient => 6 min 2) le nain et le guerrier traverse => 26 min le mage revient => 30 min 3) les deux derniers traversent => 34 min
Soit 34 minutes. Ou encore a+3b+d. Le résultat est indépendant de c !
Et sinon, pour n pair: [TeX]t = \sum\limits_{i=2}^\frac{n}{2}{(2a_2+a_1+a_{2i})}+a_2[/TeX] Et pour n impair: [TeX]t = \sum\limits_{i=2}^\frac{n-1}{2}{(2a_2+a_1+a_{2i+1})}+(a_1+a_2+a_3)[/TeX] En espérant ne pas avoir fait d'erreur.
Question 1 : C'est a et b qui traversent L'un des deux revient c et d traversent l'autre revient et a et b traversent
Question 2 : Cas paire : Les deux plus rapides traversent (a et b) l'un ramène la torche (a ou b) Les deux plus lents qui restent traversent l'autre ramène la torche (a ou b) et on recommence
Cas impair
Pareil que le cas pair jusqu’au moment où il reste 3 personnes Le plus rapide traverse avec l'un puis revient chercher l'autre.
La question 2 étant devenue ouverte, je vais y aller avec la 1 tout en continuant de réfléchir sur la 2:
1-) a et b vont l'allée et a ramène la torche: (b+a) min 2-) c et d font l'allée et b ramène la torche : (d+b) min 3-) a et b font l'allée pour finir: (b) min
Au total on aura mis: (d+3b+a) min soit 34min pour a=2,b=4,c=12etd=20
Une proposition pour le cas général 2 valable pour les cas où [latex]2*a_2 \leq a_1+a_x[/latex] pour tout x:
*** Pour [latex]n \leq 2[/latex]: [latex]temps=a_n[/latex]
*** Pour [latex]n \geq 3[/latex]: En appliquant le même principe que le cas particulier 1, [latex]a_1[/latex] et [latex]a_2[/latex] vont s'occuper des autres en faisant les aller/retour en constituant des pseudo-équipes de 4 personnes à chaque fois: [latex]a_1[/latex], [latex]a_2[/latex], [latex]a_x[/latex] et [latex]a_{x+1}[/latex], x>2 et x<n.
Après combinaison, on trouve les 2 formules suivantes; à confirmer ou à infirmer
1-) Si n est pair, on pose [latex]p=\frac{n}{2}[/latex] [TeX]temps=\sum_{i=2}^{p}a_{2i}+(p-1)*a_1+(n-1)*a_2[/TeX] 2-) Si n est impair, on pose [latex]p=\frac{n-1}{2}[/latex] [TeX]temps=\sum_{i=1}^{p}a_{2i+1}+p*a_1+(n-2)*a_2[/TeX] Voilà
si c > 2b-a (je parle de temps de parcours) , alors on emploie le trajet clasique de l'énigme. a et b passent, a revient, c et d passent b repart puis revient avec a.
si c< 2b-a , il est plus économique de faire faire les aller retour à a qui emméne chacun puis revient chercher le suivant.
Question 2 : Soient L le plus lent et L' le plus lent en second.
Tant que L' > 2b-a, on fait passer le couple L L' avec la première méthode.
Dès que L' < 2b-a , a fait passer tout le monde un par un.
Tout le monde a dit que c'était trop facile, tout le monde connait, mais tous ceux qui ont donné une réponse, ont donné une réponse fausse.
C'est très vrai, ça m'avait d'ailleurs choqué mais la discussion était fermée...
Pour le problème à 4, l'idée est de faire traverser les plus lents ensembles. Pour cela, les plus rapides se répartissent de part et d'autre du pont, puis les 2 lents traversent, puis un des 2 rapides ramène la torche pour revenir avec son collègue de l'autre côté du pont. Concrètement : a et b traversent. a ramène la torche. c et d traversent. b ramène la torche. a et b traversent. Durée du parcours : a + 3b + d = 34 minutes.
Mieux que si a fait tous les voyages (il traverse avec chacun et ramène la torche à chaque fois) : 2a + b + c + d = 40 minutes.
Question bonus 1 Si a, b, c et d inconnus, les durées des stratégies se comparent ainsi : a + 3b + d versus 2a + b + c + d càd 2b versus a+c Il suffit donc de comparer ces deux valeurs pour connaître la meilleure stratégie.
Question bonus 2 La première stratégie fait passer les 2 plus lents ensembles. La seconde stratégie fait passer les plus lents un par un. Dans les 2 cas, lorsqu'on a fait passer les 2 plus lents et ramené la torche au départ, les deux stratégies ont abouti au même résultat. Il est donc possible de changer de stratégie à chacun de ces moments !! Il est donc logique de comparer les 2 stratégies à chaque fois qu'elles sont intervertibles, afin de toujours utiliser la méthode la plus optimale.
La stratégie 1 fait traverser a et b, puis a (ou b) revient, puis les 2 plus lents traversent, puis b (ou a) revient. Durée : a + 2b + z (z = le temps du plus lent).
La stratégie 2 fait traverser a avec z, puis a revient, puis a traverse avec y, puis a revient. Durée : 2a + y + z.
Comparaison des 2 stratégies :a + 2b + z versus 2a + y + z Càd 2b versus a + y. Ce qui d'ailleurs s'applique parfaitement au cas à 4 voyageurs.
Donc, chaque fois que les 2 plus lents ont traversé, on refait la comparaison avec les 2 plus lents suivants pour choisir la nouvelle stratégie à adopter. On obtient donc la solution la plus optimale !
NB : s'il n'y a plus que 3 voyageurs, les 2 stratégies reviennent au même. Stratégie 1 : a et b traversent ; a revient ; a et c traversent. Stratégie 2 : a et c traversent ; a revient ; a et b traversent.
Pour l'énoncé original, le minimum est de 34 minutes - aller de 2 et 4 => 4 - retour de 2 => 6 - aller de 12 et 20 => 26 - retour de 4 => 30 - aller de 2 et 4 => 34
On remarque qu'il faut 2 trajets pour faire passer une personne, et un seul pour faire passer les deux dernières personnes. Pour N personnes il faut donc au minimum2(N-2)+1 trajets
Pour la "petite" généralisation à 4 personnes, a<b<c<d, il faut donc 5 trajets. 2 options se posent: - le plus rapide fait l'aller retour avec chacun. Total b+a+c+a+d = 2a + b + c +d - les deux plus rapides ramènent la torche à tour de rôle et les plus lents partent ensembles : b+a+d+b+b = a+3b+d En comparant les deux on trouve qu'il est plus rapide d'utiliser l'option 1 si a et c ont une meilleure moyenne que b (a+c < 2b), et l'autre option sinon.
Exemple: * 2-8-9-12 nous donne 8+9+12+2+2 = 33 avec l'option 1, 8+2+12+8+8 = 38 avec l'option 2 * 2-5-9-12 nous donne 5+9+12+2+2 = 30 avec l'option 1, 5+2+12+5+5 = 29 avec l'option 2.
"mais bon sang,mais c'est bien sûr .C'est clair comme de l'eau de roche". Comment n'y ai je pas pensé avant.
4 et 2 traversent (4 mn) 2 reste en face tout seul comme un grand et 4 revient (4 mn) 12 et 20 traversent ensemble (20 mn) 2 qui etait resté en face revient avec la torche (2mn) 2 retraverse avec 4 (4mn)
total 34 mn
On peut faire mieux :(28 mn) en respectant strictement l'énoncé. En effet rien n’oblige 2 a revenir chercher 4 qui a déjà traversé le pont une fois. on dit bien "traverser le pont" mais pas rester de l'autre coté.
Accueil
:
)
(à part une toute petite erreur d'étourderie, quand le mage traverse le pont, il met 4 minutes et pas 2)
