Forum: Wissenschaft
Rätsel der Woche: Rundfahrt garantiert
SPIEGEL ONLINE

Schnellstraßen verbinden sechs Städte, aber wie sie verlaufen, bleibt unklar. Trotzdem ist eine Rundreise durch vier Städte auf jeden Fall möglich. Wissen Sie, warum?

Seite 1 von 7
Eriol Brumel 02.10.2016, 12:45
1. Wo liegt mein Denkfehler?

Folgende Anordnung der Straßen sollte die genannten Bedingungen erfüllen:

A - B - C
I X I X I
D - E - F

Dann ist aber eine direkte Fahrt z.B. durch A, B, C, F nicht möglich, weil A weder zu C noch zu F eine direkte Verbindung hat.

Beitrag melden Antworten / Zitieren
Tschuklu 02.10.2016, 13:10
2. Verstehe wer will,

ich aber nicht. E + F erfüllen bei dieser Lösung die Voraussetzungen der Aufgabe nicht. Sie sind doch nicht mit drei Städten direkt verbunden!?

Beitrag melden Antworten / Zitieren
h.weidmann 02.10.2016, 13:28
3.

Zitat von Eriol Brumel
Folgende Anordnung der Straßen sollte die genannten Bedingungen erfüllen: A - B - C I X I X I D - E - F Dann ist aber eine direkte Fahrt z.B. durch A, B, C, F nicht möglich, weil A weder zu C noch zu F eine direkte Verbindung hat.
Die Aufgabenstellung beachten:

"Beweisen Sie, dass man stets vier Städte so auswählen kann, dass eine Rundreise auf Schnellstraßen durch diese vier Städte möglich ist."

Das ist so zu interpretieren, dass nicht bei jeder Kombination von vier Städten eine Rundreise möglich sein soll, sondern bei mindestens einer.
Sie machen genau das Gegenteil, Sie wählen vier Städte, bei denen eine Rundreise nicht möglich ist.

Sie können aber z.B. die Städte A, B, E und D wählen. Damit ist die Anforderung erfüllt.

Beitrag melden Antworten / Zitieren
betonklotz 02.10.2016, 13:29
4. Was soll die Fallunterscheidung?

Offensichtlich reicht es doch aus den schwierigsten möglichen Fall zu betrachten. Und das ist der Fall mit der kleinsten möglichen Zahl an Straßen der mit der Aufgabenstellung vereinbar ist. Man nehme also an, daß jede Stadt mit genau drei anderen direkt verbunden ist et voila.

Beitrag melden Antworten / Zitieren
zebrapunktReloaded 02.10.2016, 13:43
5. Wie ich meine, viel kürzer...

Ich kann eine beliebige Menge von beliebig angeordneten Punkten (Städten) so mit Dreiecken vernetzen, dass sich keine Überschneidungen der Kanten (Straßen) ergeben (z.B. Delaunay-Triangulation). Im entshenden Netz ist die Bedingung immer erfüllt, dass eine Stadt eine Verbindung zu mindestens 3 anderen Städten hat. Die Städte zweier nebeneinander liegender Dreiecke kann ich dann für meine 4-Städtetrip anfahren.

Beitrag melden Antworten / Zitieren
zebrapunktReloaded 02.10.2016, 13:59
6. Kommando zurück

Zitat von zebrapunktReloaded
Ich kann eine beliebige Menge von beliebig angeordneten Punkten (Städten) so mit Dreiecken vernetzen, dass sich keine Überschneidungen der Kanten (Straßen) ergeben (z.B. Delaunay-Triangulation). Im entshenden Netz ist die Bedingung immer erfüllt, dass eine Stadt eine Verbindung zu mindestens 3 anderen Städten hat. Die Städte zweier nebeneinander liegender Dreiecke kann ich dann für meine 4-Städtetrip anfahren.
Das mit den drei anderen Städten stimmt nicht.

Beitrag melden Antworten / Zitieren
permissiveactionlink 02.10.2016, 14:03
7. How many roads must...

...a man walk down ? Spätestens nach der Lektüre von "Hitchhiking through the galaxy" wissen wir : Es sind genau 42. Tatsächlich ist dies die Gesamtzahl der möglichen Direktverbindungen zwischen sechs Städten, direkt berechenbar mit der Gauss'schen Summenformel. Die Bedingung, dass jede Stadt mit minimal drei Direktverbindungen mit anderen Städten verbunden ist, lässt sich aber mit einer Minimalanzahl von Direktverbindungen realisieren. Wie groß ist diese ? Und noch eine Frage stellt sich dem rational denkenden Geist : Wenn jede Stadt mit jeder direkt gebunden ist, und "Deep Thought" dafür das Ergebnis 42 liefert, wie viele Vierstadtrundreisen existieren dann, wenn der Start- und Endpunkt einer Rundreise wesentlich ist ?

Beitrag melden Antworten / Zitieren
tl-hd 02.10.2016, 14:14
8.

Zitat von Tschuklu
ich aber nicht. E + F erfüllen bei dieser Lösung die Voraussetzungen der Aufgabe nicht. Sie sind doch nicht mit drei Städten direkt verbunden!?
Die weiteren Verbindungen dieser Städte sind nicht dargestellt. Wenn Sie diese noch hinzufügen, ändert das nichts an der Existenz des schon bestehenden Rundkurses. Es ergeben sich evtl. noch weitere Rundkurse, aber da nur gezeigt werden sollte, dass mind. ein Rundkurs existiert, kann man abbrechen, wenn dieser gefunden wurde. Ob dann noch weitere Straßen existieren, ist unerheblich.

Beitrag melden Antworten / Zitieren
permissiveactionlink 02.10.2016, 14:15
9. #2, Tschuklu

Wieso denn das ? Die Auflösung der Aufgabe betrachtet doch nur die jeweils mindestens drei Verbindungen der Städte A und B. Über die Verbindungen der Städte C,D,E und F untereinander wird da gar nichts gesagt. Natürlich hat jede von ihnen auch mindestens drei Direktverbindungen. Aus der Abbildung in der Auflösung mit dem Rundkurs A-C-B-D könnte man sonst ja auch den falschen Schluss ziehen, C und D hätten jeweils nur zwei Direktverbindungen statt mindestens drei.

Beitrag melden Antworten / Zitieren
Seite 1 von 7