Weihnachtsmann rot

Challenge from 11. December


Author: Martin Skutella

Project: MATH+ Application Area AA3: Networks


Slightly annoyed, Santa Claus hangs up the phone. Just a moment ago, he was talking to his good-for-nothing brother-in-law, who once again urgently needs Santa's help at the South Pole. But no matter how hard he thinks, Santa does not know how to travel there and still be back in time for Christmas at the North Pole. Helplessly, he stares at the world map on the wall (see Fig.), when Elf Einstein passes by. As always, Einstein has his assistant, elf Rosen, in tow.

The world map shows the locations A to H, the North Pole N, and South Pole S. Furthermore, the travel times between these locations.

For weeks, the two elves have been talking about nothing but their latest discovery—much to the sorrow of all the other elves. Rumour has it that it has something to do with the field equations of General Relativity. But in the absence of any deeper understanding, everyone just talks about wormholes.

“How are your wormholes doing, Einstein?” asks Santa. Slightly offended, Einstein sticks out his tongue. However, he overcomes his pride and starts lecturing: “Our latest insights into gravitational anomalies point to unexpected connections between certain places; just as a wormhole connects two points on the surface of an apple. These connections may even make time travel possible!”
Santa interrupts musing about his upcoming trip to the South Pole and starts to listen attentively.

Accompanied by Einstein and Rosen, Santa sets off for the South Pole shortly after. For safety reasons, the outward journey to the South Pole is still to be made along the classic connections that are drawn as lines on the world map. The numbers next to the connections indicate the number of hours required. For example, the travel time from the North Pole N along the possible travel routes via C and H to the South Pole S amounts to 6+4+7=17 hours.

Einstein and Rosen want to use the outward journey to the South Pole to clarify final details with regard to the gravitational anomalies of the three wormholes that they have marked in bold on the world map. On the return journey to the North Pole, it will then be possible “to let the clock run backwards” on the three connections marked in bold. Thus, the adventurers are able to travel into the past. For example, the travel time along the route from the South Pole S via H and C to the North Pole N will only be 7+(-4)+6=9 hours.

Santa is very enthusiastic, but Einstein warns against the excessive use of wormholes: “We can use each wormhole at most once, and even that may be risky.”
After some thought, Santa states the following objectives:

  • O1: In order to enable a timely return, the total travel time for the journey from the North Pole to the South Pole and back must not exceed 24 hours.

  • O2: In order to avoid possible discontinuities in space-time as far as possible, no more than two of the three wormholes are to be used on the journey from the South Pole back to the North Pole.

  • O3: To make the journey as varied as possible, none of the connections should be used on both the outward and the return journey—not even in the opposite direction.

  • O4: In order to meet as many friends as possible on the trip, each of the places A to H should be visited at least once during the whole journey.

  • O5: In order to be a burden to as few friends as possible, at most one of the places A to H should be visited on both the outward and the return journey.

  • O6: On the other hand, in order to bless at least a few friends with two visits, at least one of the places A to H should be visited on both the outward and the return journey.

Disappointedly, the three travel companions realise that the six objectives are not compatible. Even for certain combinations of three objectives, there seems to be no admissible itinerary for the round trip to the South Pole and back to the North Pole.

For which of the following combinations exists no such admissable round trip?

Artwork: Friederike Hofmann

PDF download

Possible answers:

  1. O1, O2, and O3.

  2. O1, O2, and O5.

  3. O1, O2, and O6.

  4. O1, O3, and O5.

  5. O1, O3, and O6.

  6. O1, O4, and O5.

  7. O1, O5, and O6.

  8. O1, O4, and O6.

  9. O2, O3, and O4.

  10. O4, O5, and O6.

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

Project relevance:

Shortest path problems play a fundamental role in many areas of combinatorial optimisation and especially network optimisation. They are essential building blocks in the efficient solution of numerous practical problems, for example in the area of traffic. In the MATH+ research centre, shortest path problems are studied in the following research projects, among others, in the application area Networks:

AA3-2: Nash flows over time in transport and evacuation simulation

AA3-3: Discrete-Continuous Shortest Path Problems in Flight Planning

AA3-4: Flow-Preserving Graph Contractions with Applications to Logistics Networks

AA3-5: Tropical Mechanism Design

Obviously, the alleged connection to the theory of the Einstein-Rosen bridge (wormholes) mentioned in the challenge is fictitious.