15 Die Straße von Bethlehem

© Julia Nurit Schönnagel, MATH+

Autor: Matthew Maat (Universiteit Twente)
Projekt: Combining algorithms for parity games & linear programming

Aufgabe

Abbildung 1: Karte des Straßennetzes. Kreise und Quadrate stellen Städte dar. Pfeile repräsentieren Einbahnstraßen zwischen den Städten, die nur in die Richtung des jeweiligen Pfeils benutzt werden können.

Das Straßennetz ist in Abbildung 1 dargestellt. Maria und Josef starten in Bethlehem (B auf der Karte). Die 16 Städte sind durch Quadrate und Kreise markiert. Jede der Städte Emmaüs, Filadelfia, Gerar und Hebron (E, F, G und H) enthält möglicherweise einen römischen Wachposten (in den anderen Städten gibt es keine Wachposten). Es ist allen Einheimischen bekannt, wie die Karte aussieht und wo sich die Wachposten befinden. Die Menschen in dieser Region vertrauen Fremden jedoch nicht so leicht, weshalb sie Durchreisenden ihr geographisches Wissen nicht in Gänze preisgeben. Reisenden wird, sobald sie in einer Stadt ankommen, lediglich gesagt, welche Straße sie von dieser Stadt aus nehmen sollten. Alle Straßen sind Einbahnstraßen, d.h. sie können nur in einer Richtung passiert werden und es ist umöglich, unterwegs umzukehren. Da die Reisenden den Weg nicht kennen, werden sie den ihnen mitgeteilten Richtungsangaben stets Folge leisten.

In den meisten Städten (weiße Kreise) sind die Einwohner freundlich und werden die Reisenden, wenn möglich, in eine Richtung schicken, die es ihnen erlaubt, die römischen Wachposten zu umgehen. Einige Städte (graue Quadrate) hingegen werden vollständig von Herodes’ Spionen bewohnt, die die Reisenden, wenn möglich, in eine Richtung schicken, die zu einem Wachposten führt. Sowohl die freundlichen Einwohner als auch die Spione wissen, wo die Spione leben, und wählen unter Berücksichtigung des gesamten verbleibenden Weges nach Ägypten jeweils eine der besten Optionen, um ihr Ziel zu erreichen.

Beispiel: Angenommen, Emmaüs hat einen römischen Wachposten, Filadelfia jedoch nicht. Dann gilt: Reisende, die in der Stadt X ankommen, werden von den Spionen nach E, und Reisende, die in der Stadt Y ankommen, von den freundlichen Einwohnern nach F geschickt. Man bemerke, dass die Spione die Reisenden in diesem Fall nicht von von X nach Y schicken werden, weil sie wissen, dass sie von den dort lebenden freundlichen Einwohnern weiter nach F geleitet werden würden.

Am Ende kommen Maria und Joseph mit dem Kind sicher in Ägypten an, ohne auf einen Wachposten zu stoßen. In Ägypten treffen sie auf andere Reisende, die in Afek, Cäsarea und Damaskus (A, C, D auf der Karte) gestartet sind und ebenfalls auf Angaben von Einheimischen angewiesen waren. Merkwürdigerweise sind diese auf ihrer Reise nach Ägyten allesamt römischen Wachposten begegnet.
Angesichts der Tatsache, dass Joseph und Maria nicht auf einen römischen Wachposten gestoßen sind, die anderen Reisenden jedoch schon, welche der folgenden Aussagen trifft auf den Standort bzw. die Standorte des Wachpostens bzw. der Wachposten zu?

Bemerkung: Reisende erhalten auch in den Städten, in denen sie starten, Richtungsangaben.

Antwortmöglichkeiten

1. Es gibt nur eine Möglichkeit für die Verteilung der Wachposten. Bei dieser gibt es genau einen Wachposten.
2. Es muss genau 2 Wachposten geben und diese müssen sich in E und F befinden.
3. Es muss genau 2 Wachposten geben und diese müssen sich in E und G befinden.
4. Es muss genau 2 Wachposten geben und diese müssen sich in E und H befinden.
5. Es muss genau 2 Wachposten geben und diese müssen sich in F und G befinden.
6. Es muss genau 2 Wachposten geben und diese müssen sich in F und H befinden.
7. Es muss genau 2 Wachposten geben und diese müssen sich in G und H befinden.
8. Es gibt nur eine Möglichkeit für die Verteilung der Wachposten. Bei dieser gibt es genau drei Wachposten.
9. Es gibt genau zwei verschiedene Möglichkeiten für die Verteilung der Wachposten.
10. Es gibt mehr als zwei verschiedene Möglichkeiten für die Verteilung der Wachposten.

Projektbezug

Diese Aufgabe hängt mit Erreichbarkeitsspielen zusammen.