Weihnachtsmann rot

Aufgabe vom 14. Dezember

Ein etwas anderer Weihnachtsstern

Autoren: Sven Jäger, Rico Raber, Daniel Schmidt genannt Waldschmidt, Khai Van Tran

Projekt: AG Kombinatorische Optimierung und Graphenalgorithmen (COGA)

Aufgabe:

„Das ist ungerecht!“, ruft Rentier Miri, Wortführerin der Vereinten Rentiergewerkschaft (VeRti). „Den ganzen Winter haben wir Rentiere in der Plätzchenfabrik geschuftet! In Rekordzeit haben wir Zimt und Zucker über den zugefrorenen Fluss transportiert! Aber an Heiligabend, wenn es interessant wird, dürfen nur einige wenige von uns den Schlitten des Weihnachtsmanns ziehen.“

Nach Verhandlungen mit VeRti hat man sich schließlich darauf geeinigt, dass die Erde in 15 Zonen aufgeteilt wird und jede dieser Zonen von einem unterschiedlichen Rentiergespann beliefert wird, sodass jedes Rentier die Gelegenheit bekommt, den Schlitten zu ziehen. Der Weihnachtsmann wird also am Weihnachtstag seine Route am Nordpol starten, eine der Zonen beliefern und dann zum Nordpol zurückkehren, um die Rentiere zu wechseln. Danach wird die nächste Zone beliefert usw. Nachdem das letzte Präsent ausgeliefert ist, kehrt der leere Schlitten zum Nordpol zurück, was die sternförmige Rundtour abschließt.

„Wenn der Schlitten sowieso immer zum Nordpol zurückkehrt, dann könnte man ja immer nur die Geschenke auf den Schlitten laden, die auch in der jeweils nächsten Zone ausgeliefert werden“, wirft Wichtel Rico ein. „Dann haben die Rentiere weniger zu ziehen und wir sind schneller fertig.“ Mit Grauen muss der Weihnachtsmann an das letzte Jahr zurückdenken, als die Wichtel einen Tag vor Weihnachten anfingen, auf dem zugefrorenen See Geschenke versenken zu spielen, und Rudolph in letzter Sekunde noch neue Geschenke organisieren musste. Einen Teil der Geschenke zusammen mit den Wichteln aus den Augen zu lassen, kommt also nicht in Frage – und nicht nur weil allein der Berufsstolz des Weihnachtsmanns es ihm verbieten würde, mit einem nicht voll bepackten Schlitten loszufahren.

Um die beste Route zu planen, beugt sich Rudolph nun über eine Weltkarte (s. Abbildung 1). Verzeichnet sind die 15 Zonen mit dem Gewicht der in ihnen abzuliefernden Geschenke und ihren Distanzen vom Nordpol (s. auch Tabelle 1). Rudolf weiß, dass die Transportzeit nicht nur proportional zur gefahrenen Strecke, sondern auch proportional zum Gewicht des Schlittens und aller eingeladenen Geschenke ist: Der leere Schlitten wiegt 30 Tonnen (t). Den leeren Schlitten 10 Luftmeilen (lm) zu ziehen, nimmt 300 Mondsekunden (mon) in Anspruch. Wären 70 t an Geschenken auf dem Schlitten geladen (zusammen mit dem Schlitten also ein Gesamtgewicht von 100 t), so würden die Rentiere 2000 mon brauchen, um den Schlitten 20 lm zu ziehen. Da die am Nordpol bereitstehenden Rentiere ganz aufgeregt auf ihren Einsatz warten, nimmt das Wechseln des Rentiergespanns keine Zeit in Anspruch. Ebenso benötigt der Weihnachtsmann, der alte Routinier, zum Verteilen der Geschenke keine Zeit sobald der Schlitten in einer Zone angekommen ist.


PIC

Abbildung 1: Weltkarte mit den zu beliefernden 15 Zonen. Die Fahne markiert den Nordpol.


ZoneGewicht in tDistanz in lm
A 22 101
B 38 118
C 16 87
D 35 72
E 9 37
F 27 208
G 11 80
H 30 110
I 37 145
J 42 180
K 19 59
L 25 124
M 21 78
N 14 48
O 24 153

Tabelle 1: Gewicht der abzuliefernden Geschenke und Entfernung der Zonen vom Nordpol.

Festzulegen ist also lediglich noch die Reihenfolge, in der die Zonen befahren werden...

Die Fahrtzeit, die wir optimieren wollen, ist die Zeit vom Start des Weihnachtsmanns am Nordpol mit dem vollen Schlitten bis zur Rückkehr mit dem leeren Schlitten. Wir sagen, dass eine Route optimal ist, wenn sie die kürzestmögliche Fahrtzeit garantiert. Eine optimale Route heißt eindeutig, wenn es nur eine Reihenfolge gibt, die diese kürzestmögliche Fahrtzeit generiert.

Welche der folgenden Aussagen ist korrekt?


Illustration: Julia Nurit Schönnagel

Die Aufgabe als PDF runterladen

Antwortmöglichkeiten:

  1. In einer optimalen Route muss J vor E vor O besucht werden und die optimale Route ist eindeutig.

  2. In einer optimalen Route muss F vor M vor E besucht werden und die optimale Route ist eindeutig.

  3. In einer optimalen Route muss N vor H vor L besucht werden und die optimale Route ist eindeutig.

  4. In einer optimalen Route muss K vor G vor I besucht werden und die optimale Route ist eindeutig.

  5. In einer optimalen Route muss L vor J vor M besucht werden und die optimale Route ist eindeutig.

  6. In einer optimalen Route muss J vor E vor O besucht werden und die optimale Route ist nicht eindeutig.

  7. In einer optimalen Route muss F vor M vor E besucht werden und die optimale Route ist nicht eindeutig.

  8. In einer optimalen Route muss N vor H vor L besucht werden und die optimale Route ist nicht eindeutig.

  9. In einer optimalen Route muss K vor G vor I besucht werden und die optimale Route ist nicht eindeutig

  10. In einer optimalen Route muss L vor J vor M besucht werden und die optimale Route ist nicht eindeutig.

Sie müssen sich einloggen um die Aufgaben abgeben zu können.