Vier Wanderer müssen nachts eine wacklige Hängebrücke überqueren. Sie haben nur eine Taschenlampe, und es gilt:
Die Brücke trägt höchstens zwei Personen gleichzeitig.
Wer über die Brücke geht, braucht die Lampe – sie lässt sich nicht werfen.
Gehen zwei gemeinsam, bestimmt der Langsamere das Tempo.
Die vier brauchen allein 1, 2, 5 und 10 Minuten für einen Weg.
Schaffen es alle vier in 17 Minuten auf die andere Seite? Und geht es schneller?
Hinweis anzeigen
Der naheliegende Plan – der Schnellste geleitet jeden einzeln hinüber – kostet 19 Minuten. Überlege, was die beiden Langsamen so teuer macht, und ob sich diese Kosten teilen lassen.
Lösung
Die Lösung ist ausgeblendet. Nimm dir erst selbst Zeit für die Aufgabe – der Aha-Moment lässt sich nicht nachholen.
Wirklich aufdecken?
Hast du es ernsthaft versucht – und den Hinweis gelesen? Danach gibt es kein Zurück im Kopf.
Lösung
Ein Plan über 17 Minuten. Die Namen seien $1, 2, 5, 10$ nach ihren Zeiten:
Schritt
Wer geht
Richtung
Dauer
1
$1$ und $2$
hinüber
2
2
$1$
zurück
1
3
$5$ und $10$
hinüber
10
4
$2$
zurück
2
5
$1$ und $2$
hinüber
2
Summe: $2 + 1 + 10 + 2 + 2 = 17$ Minuten. Nach Schritt 5 ist niemand mehr auf der Startseite.
Der Kniff. Die beiden Langsamen gehen gemeinsam. Dann kostet die 10-Minuten-Überquerung die 5 Minuten von Person $5$ gewissermassen nichts mehr, weil beide Zeiten im selben Weg aufgehen.
Warum es nicht schneller geht. Vier Personen brauchen mindestens drei Hinwege, und zwischen den Hinwegen muss die Lampe zweimal zurückkommen – also mindestens fünf Überquerungen. Person $10$ ist auf genau einem Hinweg dabei.
Fall A: $5$ und $10$ gehen zusammen. Dieser Hinweg kostet 10 Minuten. Bleibt zu klären, wer die beiden Rückwege übernimmt; die wenigen Möglichkeiten liefern alle mindestens 17 Minuten, und der Plan oben erreicht diesen Wert.
Fall B: $5$ und $10$ gehen auf verschiedenen Hinwegen. Dann kostet ein Hinweg mindestens 10 und ein anderer mindestens 5 Minuten. Der dritte Hinweg und die beiden Rückwege kosten je mindestens 1 Minute. Zusammen also mindestens
$$
10 + 5 + 1 + 1 + 1 = 18 > 17 .
$$
Fall B ist damit nie optimal, und 17 Minuten sind das Minimum. $\blacksquare$