Project: MATH+ Application Area AA3: Networks
Challenge:
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:
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:
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.