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 7 von 7
tl-hd 07.10.2016, 17:55
60.

Zitat von querulant_99
Vielen Dank für diesen schönen Widerspruchsbeweis. Mit meiner Quengelei wollte ich keinesfalls bestreiten, dass man bei dieser Aufgabenstellung immer einen Rundkurs mit 4 Städten findet. Mir ging es eher um die m.E. schludrige Verwendung des bestimmten Artikels bei der Beweisführung, was bei mir zu Missverständnissen führte. Der Satz: "Wir zeigen im Folgenden, dass diese beiden Städte, wir nennen sie A und B, Teil *des* gesuchten Rundkurses sind, der durch vier Städte führt." kam bei mir so rüber in dem Sinne: Egal welchen Rundkurs man wählt, jeder dieser Rundkurse führt zwangsweise durch A und B. Diesen Beweis kann ich aber nirgendwo erkennen. Ich sehe lediglich den schwächeren Beweis, dass es auch durch die miteiteinander schlecht verbunden Städte A und B mindestens einen Rundkurs gibt
In der Lösung werden zwei Fälle unterschieden, nämlich dass jede Stadt mit jeder direkt verbunden ist (dann ist die Lösung trivial), und dass dies nicht der Fall ist. Jetzt können Sie gerne ausrechnen, wie viele verschiedene Graphen es gibt, die die Mindestanforderungen erfüllen, ohne dass jede Stadt mit jeder verbunden ist. Sie können auch gerne für jeden dieser Graphen zeigen, dass ein Rundkurs existiert. Oder sie argumentieren wie in der Musterlösung, dass es in diesem Fall mindestens ein Paar von Städten gibt, die nicht miteinander verbunden sind. Ob Sie diese nun A und B nennen oder X und Y oder Ahausen und Beispielstadt oder wie auch immer ist für den Lösungsweg unerheblich.

In der Mathematik gibt es dafür den schönen Begriff "oBdA" ("ohne Beschränkung der Allgemeinheit"). Dadurch, dass die Städte also aBdA als A und B benannt werden, folgt also keinerlei Einschränkung bzgl. der Allgemeingültigkeit der Lösung.

Beitrag melden Antworten / Zitieren
querulant_99 09.10.2016, 10:18
61. @tl-hd, #60

Das ist alles richtig, was Sie schreiben. Ich würde aber den Beweis wie folgt modifizieren:
Aus der Menge der 6 Städte wählt man eine beliebige Teilmenge von 4 Städten aus. Es gibt jetzt 2 Fälle:
(1) Ausgehend von einer beliebigen Stadt der Teilmenge erreicht man durch die 3 Verbindungsstaßen alle übrigen Städte dieser Teilmenge. Man kann jetzt alle 4 Städte in beliebiger Reihenfolge durch einen Rundkurs erreichen (Trivialfall).
(2) Man findet 2 Städte, die nicht direkt miteinander verbunden sind, und bezeichnet diese mit A und C. Man findet dann aus der Gesamtmenge zwei weitere Städte B und D, so dass der Rundkurs A,B,C,D,A möglich ist.
Der Beweis dafür wird dann sinngemäß wie in der Musterlösung geführt.

Beitrag melden Antworten / Zitieren
tl-hd 09.10.2016, 10:37
62.

Zitat von querulant_99
Das ist alles richtig, was Sie schreiben. Ich würde aber den Beweis wie folgt modifizieren: Aus der Menge der 6 Städte wählt man eine beliebige Teilmenge von 4 Städten aus. Es gibt jetzt 2 Fälle: (1) Ausgehend von einer beliebigen Stadt der Teilmenge erreicht man durch die 3 Verbindungsstaßen alle übrigen Städte dieser Teilmenge. Man kann jetzt alle 4 Städte in beliebiger Reihenfolge durch einen Rundkurs erreichen (Trivialfall). (2) Man findet 2 Städte, die nicht direkt miteinander verbunden sind, und bezeichnet diese mit A und C. Man findet dann aus der Gesamtmenge zwei weitere Städte B und D, so dass der Rundkurs A,B,C,D,A möglich ist. Der Beweis dafür wird dann sinngemäß wie in der Musterlösung geführt.
Da Sie so viel Wert auf die Details der Musterlösung legen, muss man auch bei Ihrem Vorschlag auf Details achten. Und da fällt schon der erste Fall durch. Denn damit, dass es von einer Stadt direkte Verbindungen in alle drei übrigen der vier betrachteten Städte gibt, ist nicht bewiesen, dass es einen Rundkurs gibt, weil Sie keinerlei Aussage über die Verbindungen dieser drei Städte untereinander treffen.

Aber schon die beliebige Auswahl der Teilmenge von vier Städten ist eine unzulässige Einschränkung. Schließlich gibt es wie von anderen Foristen gezeigt Fälle, in denen Rundkurse nur durch bestimmte Städte, aber nicht durch beliebige Teilmengen existieren. Sie müssen also in Ihrem Beweis die beiden Städte E und F mit einbeziehen. So ist z.B. im Sinne der Aufgabenstellung denkbar, dass die Stadt A mit B, C und D direkt verbunden ist, die Städte B, C und D aber neben der Verbindung mit A jeweils noch mit E und F verbunden sind. Dann hat jede Stadt mindestens drei Verbindungen, aber kein Rundkurs durch A, B, C und D existiert. Somit ist Ihr "Beweis" schon im angeblich trivialen Fall widerlegt.

Beitrag melden Antworten / Zitieren
querulant_99 09.10.2016, 11:53
63.

Zitat von tl-hd
Da Sie so viel Wert auf die Details der Musterlösung legen, muss man auch bei Ihrem Vorschlag auf Details achten. Und da fällt schon der erste Fall durch. Denn damit, dass es von einer Stadt direkte Verbindungen in alle drei übrigen der vier betrachteten Städte gibt, ist nicht bewiesen, dass es einen Rundkurs gibt, weil Sie keinerlei Aussage über die Verbindungen dieser drei Städte untereinander treffen. Aber schon die beliebige Auswahl der Teilmenge von vier Städten ist eine unzulässige Einschränkung. Schließlich gibt es wie von anderen Foristen gezeigt Fälle, in denen Rundkurse nur durch bestimmte Städte, aber nicht durch beliebige Teilmengen existieren. Sie müssen also in Ihrem Beweis die beiden Städte E und F mit einbeziehen. So ist z.B. im Sinne der Aufgabenstellung denkbar, dass die Stadt A mit B, C und D direkt verbunden ist, die Städte B, C und D aber neben der Verbindung mit A jeweils noch mit E und F verbunden sind. Dann hat jede Stadt mindestens drei Verbindungen, aber kein Rundkurs durch A, B, C und D existiert. Somit ist Ihr "Beweis" schon im angeblich trivialen Fall widerlegt.
Da ist mir in der Tat ein Patzer bei der Formulierung des Trivialfalls unterlaufen. Ich wollte hier natürlich ausdrücken, dass alle 4 Städte direkt miteinander verbunden sind, was natürlich immer machbar ist. wenn von jeder Stadt 3 Verbindungsstraßen ausgehen. Der fragliche Satz könnte dann folgendermaßen lauten:
.
JEDE Stadt der Teilmenge sei durch jeweils eine Verbindungsstraße mit jeder anderen Stadt der Teilmenge.verbunden.

Ich hoffe, jetzt ist die die Formulierung wasserdicht.

Beitrag melden Antworten / Zitieren
tl-hd 09.10.2016, 14:20
64.

Zitat von querulant_99
Da ist mir in der Tat ein Patzer bei der Formulierung des Trivialfalls unterlaufen. .... Ich hoffe, jetzt ist die die Formulierung wasserdicht.
Nein, noch lange nicht. Wie gesagt ist schon die beliebige Auswahl von vier Städten falsch, weil nicht notwendigerweise durch jede solche Auswahl ein Rundkurs existiert (was auch nicht in der Aufgabenstellung gefordert ist, es muss ja nur ein Rundkurs durch 4 der 6 Städte existieren, aber nicht für jede beliebige Auswahl von 4 Städten).

Beitrag melden Antworten / Zitieren
Seite 7 von 7