La solution intuitive est de faire en sorte que la personne qui rapporte la lampe soit celle
qui marche le plus rapidement : Albert.
A,B traversent : 2 mn
A revient : 1 mn
A,C traversent : 4 mn
A revient : 1 mn
A,D traversent : 8 mn
Total 16 mn
Mais... ceci n'est pas la meilleure solution !
A,B traversent : 2 mn
A revient : 1 mn
C,D traversent : 8 mn
B revient : 2 mn
A,B traversent : 2 mn
Total 15 mn !
Une solution générale de ce problème a été proposée par Günter Rote
(dont on peut trouver le papier original sur le Web) et relatée dans
"Pour la Science" N°324 d'octobre 2004.
Le lecteur intéressé pourra se reporter à l'article de Rote pour les détails
et démonstrations, ou en première approche à l'article de Jean-Paul Delahaye
dans Pour La Science.
Nous allons donner ici seulement la conclusion finale et la méthode générale.
|
Soient t1 ≤ t2 ≤ t2 ≤ ... tn
les temps de traversée de chacun.
V1 et V2 traversent d'abord Puis deux par deux tous ceux qui ont ti > 2t2 - t1 (s'il y en a un nombre impair, on laisse de côté le plus rapide) Reviennent alternativement V1 et V2, et retraversent ensemble autant qu'il le faut. Les autres voyageurs traversent ensuite avec V1, qui revient à chaque fois. |
Dans notre problème avec ti = 1, 2, 4, 8 (c'est trop simple !)
2×2 - 1 = 3 et donc les voyageurs C et D doivent traverser ensemble.
D'où la solution optimale ci dessus.
Un cas plus compliqué, et un script pour les fainéants, qui donne la liste des déplacement et le temps total :
Dans cet exemple 2×3 - 1 = 5 et donc les 6, 7, 8, 9, 10 doivent traverser par paires
Comme ils sont en nombre impair, seuls 7, 8, 9, 10 le feront.
Durée totale = 47 (au lieu de 10 + 9 + 8 + 7 + 6 + 4 + 3 + 6×1 = 53)