Weihnachtsmann rot

Challenge from 14. December

A Slightly Different Christmas Star

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

Project: Combinatorial Optimization & Graph Algorithms group (COGA)

Challenge:

“This is unfair!” exclaims reindeer Miri, spokeswoman of the United Reindeer Transport Union (URTU), “We toiled in the cookie factory throughout the winter! We transported flour, cinnamon, and sugar in record time! But on Christmas Day, when we finally get to the interesting part, only a few of us may draw Santa’s sleigh.”

After negotiations with URTU it is decided to divide the earth into 15 zones with each zone being assigned to a different team of reindeer in order to give everyone the opportunity to draw Santa’s sleigh at least once. Therefore, on Christmas Day, Santa will start his tour at the North Pole, deliver the presents in one of the zones; then he will return to the North Pole in order to swap the reindeer. Afterwards, the presents in the next zone will be delivered and so on. After the last present is delivered, the empty sleigh will return to the North Pole completing the star shaped tour.

“Since the sleigh will return to the North Pole after visiting a zone anyway, we should only load those presents that will be delivered in the respective next zone onto the sleigh,” suggests gnome Rico. “Then the reindeer will have to draw a lighter load and will be faster.” Santa flinches while remembering last year’s Christmas when the gnomes started some rounds of clay gift shooting the day just before Christmas and Rudolph had to get some new presents wrapped at the last minute. So leaving the gnomes alone with the gifts is out of the question—and not just due to Santa’s professional pride forbidding him to start his route with a mostly empty sleigh.

In order to plan the best route, Rudolph looks at a world map (see Figure 1), on which the 15 zones are recorded together with their respective distances to the North Pole and the weight of the respective presents (see also Table 1). Rudolph knows that the transport time is not only proportional to the distance traversed but also proportional to the weight of the sleigh including all the gifts still loaded onto it: The empty sleigh weighs 30 tons (t) and drawing the empty sleigh 10 air miles (am) takes 300 moon seconds (mon). With presents weighing 70 t loaded on the sleigh (so including the sleigh yields a total weight of 100 t) the reindeer would need 2000 mon to draw the sleigh 20 am. Since the reindeer waiting at the North Pole are nervously anticipating their turn, changing the reindeer takes no time at all. Once the sleigh arrives in one of the zones, Santa with his millennia of experience can distribute the gifts without loosing any time too.


PIC

Figure 1: World map with the 15 zones. The flag marks the North Pole.


ZoneWeight in tDistance in am
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

Table 1: Weight of the presents to be delivered and distance of the zones from the North Pole.

All that remains to be done is to determine the order in which the zones are visited...

The travel time we want to minimize is the time from Santa starting at the North Pole with the fully loaded sleigh until Santa returns to the north Pole with an empty sleigh. We say that a route is optimal if it minimizes that travel time. We say that an optimal route is unique if there is only one order of zones that minimizes the travel time.

Which one of the following statements is correct?


Artwork: Julia Nurit Schönnagel

PDF download

Possible answers:

  1. An optimal route must visit J before E before O and the optimal route is unique.

  2. An optimal route must visit F before M before E and the optimal route is unique.

  3. An optimal route must visit N before H before L and the optimal route is unique.

  4. An optimal route must visit K before G before I and the optimal route is unique.

  5. An optimal route must visit L before J before M and the optimal route is unique.

  6. An optimal route must visit J before E before O and the optimal route is not unique.

  7. An optimal route must visit F before M before E and the optimal route is not unique.

  8. An optimal route must visit N before H before L and the optimal route is not unique.

  9. An optimal route must visit K before G before I and the optimal route is not unique.

  10. An optimal route must visit L before J before M and the optimal route is not unique.

You have to log in to be able to submit your answer.