Mathematik Nr. 49 - Die Wüstendurchquerung

Ein LKW muss eine Wüste durchqueren, die 400 km breit ist. In der Wüste gibt es keine Tankstellen. Er kann jedoch Depots mit Benzin anlegen und an diesen Depots seinen tank auffüllen. Insgesamt kann der LKW 180 Liter (Verbrauch 1 Liter je 1 km) tanken. Dieser Tankvorrat kann entweder verbraucht (verfahren) oder in das Depot gebracht werden (natürlich auch anteilig verfahren und eingelagert werden). Am Startpunkt kann der LKW beliebig oft tanken und die Depots können eine beliebige Menge Benzin lagern.

Was ist die minimale Kilometerzahl, die der LKW fahren muss, um die Wüste zu durchqueren? Wie sieht die Verteilung der Depots aus?

∨ Lösung

Siehe auch die Diskussion im Forum.

Von Wolf W. Radzinski:

Man fängt von hinten an: Die letzte Fahrt geht über 180 km; man muss beim Depot 400-180=220 km mit vollem Tank losfahren.

Um dort ein Depot anzulegen muss man mindestens 1 mal hin, ein mal mal zurück und schließlich noch ein mal Richtung Ziel, also 3 Fahrten absolvieren. Mit einem Depot schafft man also 180+60=220 km.

Mit zwei zusätzlichen Fahrten kann man ein weiteres Depot bei 220-180/5=184 km einrichten; d.h. mit zwei Depots kommt man 180+60+36=276 km weit.

Mit drei Depots kommt man um 180/7 km weiter; mit 4 Depots nochmals um 180/9 km; usw.

Mit elf Depots kommt man erstmals über 400 km weit: 180+180/3+180/5+...+180/23 = 400,38 km. Der LKW ist dann 12*180-0,38 = 2159,62 km weit gefahren.

Von Detlef Dierig:

Das letzte Depot darf höchstens 180km vor dem Ziel liegen, also frühestens bei km220. Wenn der LKW 90km weit fährt um ein Depot anzulegen, sind noch 90l im Tank. Die Menge braucht er aber für die Rückfahrt. Man kann also mit einer einzigen Depot-Fahrt kein Depot aufbauen, das mehr als 90km entfernt ist. Die Idee zwei oder mehr Fahrten je Depot zu kalkulieren scheidet aus, da unterwegs keine Tankstelle ist. Man muss also erst einige Depots aufbauen, um mit deren Inhalt die weiter entfernten Depots errichten zu können.

Betrachten wir die n Depots unmittelbar vor der Zielfahrt. Nennen wir xi die Entfernungen der Depots vom Ausgangspunkt in km und vi die Inhalte in Litern. Für die optimale Depot-Ausnutzung muss v₁ = x₁ und v_i = x_i – x_i-1 für alle i=2,…,n gelten. Dann enthält jedes Depot genau so viel, wie der LKW an dieser Stelle zum Volltanken benötigt.

Andererseits müssen die Depots auch aufgebaut werden. Der Zustand vor jeder einzelnen Depot-Fahrt muss auch deren Rückfahrt gewährleisten. Auf der Hinfahrt verlässt der LKW den Ausgangspunkt und optimal auch jedes Depot auf seinem Weg mit einem vollen Tank und auf der Rückfahrt erreicht der LKW jedes dieser Depots bzw. den Ausgangspunkt wieder mit einem leeren Tank. Die optimale Depot-Verteilung vor dem Aufbau des Depots n ändert sich daher zu v₁ = 2 * x₁ und v_i = 2 * (x_i – x_i-1) für alle i=2,…,n.

Es gilt insbesondere 2 * x₁ = v₁. Die erste Depot-Fahrt baut das erste Depot auf, optimal also 2 * x₁ + v₁ = 180 oder x₁ = 45 und v₁ = 90. Dieses Depot verschiebt de facto den Ausgangspunkt um 45km auf das Ziel zu. Also liegen die nächsten Depots entsprechend bei km 90, 135, ….

Stellt man sich nun den Anfang des Weges rechts vor und das Ziel links und zeichnet man ein leeres Depot als 0, ein volles als 1, so ergibt sich eine duale Zahl, die mit jeder Depot-Fahrt um 1 erhöht wird. Nach der 31. Depot-Fahrt sind also 5 Depots gefüllt, bei km 45, 90, 135, 180, 225. Das reicht aus, um bei der 32. Fahrt mit 5l Tankinhalt ins Ziel zu gelangen.

Allerdings sind dann alle Depots noch halbvoll, weil man während der Aufbauphase doppelt so viele Depots benötigt hat wie zur Zielfahrt. Zur Optimierung lässt man das erste und dritte Depot leer, also gibt es drei Depots mit je 90l bei km90, 180, 225. Insgesamt sind es dann 26 Depot-Fahrten („11010“) und eine Zielfahrt, danach sind noch 45l im fünften Depot und 5l im Tank des LKW.

In der Summe hat der LKW also 27 * 180l – 50l = 4810l verbraucht und ist daher 4810km gefahren.