maettig.com

Thiemos Archiv

Ich bin auf eine nette kleine Art von Rätseln gestoßen, die wirklich knifflig sein können, obwohl die Regeln sehr schlicht sind. Die Aufgabe besteht darin, eine vorgegebene Flächenaufteilung mit nur vier Farben so zu füllen, dass sich nie zwei gleichfarbige Flächen berühren. Als einzige Ausnahme sind Berührungen an einer Ecke erlaubt (im hier gezeigten Beispiel kommt das nicht vor). Mit dieser simplen, aus dem Vier-Farben-Satz (früher auch »Vier-Farben-Vermutung«) stammenden Regel lassen sich nun zwei Arten von Aufgaben konstruieren. Zuerst kann man versuchen, Lösungen für vorgegebene Vier-Farben-Rätsel zu finden.

Vier-Farben-Rätsel

Das hier gezeigte Bild stellt einen Behälter dar, der mit Sand (stark vergrößert) oder Bällen gefüllt ist, die sich gegenseitig berühren. Betrachtet man nur die Sandkörner und lässt den Behälter und die Luft zwischen den Sandkörnern außer Acht, stellt man fest, dass man drei Farben für die Füllung benötigt. Die Luft erhält die vierte Farbe. Für den Behälter bleibt nun scheinbar keine Farbe mehr übrig.

Um dennoch eine Lösung finden zu können (die dem – übrigens mathematisch bewiesenen – Vier-Farben-Satz zufolge immer existieren muss), ist es erlaubt und sogar erforderlich, bereits ausgefüllte Flächen umzufärben. Eine der möglichen Lösungen für das oben gezeigte Rätsel kann hier eingesehen werden.

Hat man das geschafft (am besten natürlich, ohne sich die Lösung anzusehen) kann man als nächstes versuchen, neue Vier-Farben-Rätsel zu schaffen, die den Betrachter in die Irre führen und möglichst schwer zu lösen sind. Der Leser sei jedoch gewarnt: Es ist verlockend, nach einer Flächenaufteilung zu suchen, die sich unmöglich mit nur vier Farben füllen lässt. Solche vermeintlichen Unmöglichkeiten beruhten jedoch immer auf ungültigen Annahmen. In der oben gezeigten Sandkiste war es beispielsweise unzulässig, der Luft zwischen den Bällen eine feste Farbe zuzuordnen. Damit schafft man das, was auf Landkarten »Exklaven« genannt wird, und bewegt sich damit bereits außerhalb der engen Definition des Vier-Farben-Satzes.

Kennst Du dieses Vier-Farben-Rätsel schon ?
http://wiesbaden.kijiji.de/c-Kaufen-Verkaufen-PC-Videospiele-Vier-Farben-Raetsel-W0QQAdIdZ30380079
Franz Scheerer
Ja, Spaßvogel, beim Zeichnen dieses Rätsels habe ich dir geholfen. Die Lösung sieht übrigens so aus. Und übrigens: Es ist völlig egal, wie viele weiße Felder du noch in dieses Bild einbaust (bei 9 sind wir ja schon), es wird immer eine Lösung geben.
Thiemo
Du hast recht. Es können natürlich auch Felder zusammengefasst werden, um die Aufgabe schwieriger zu machen. Das kleine gelbe Feld in der Mitte unter dem kleinen, pinken Feld mit dem Fragezeichen kann zu einem größeren verbunden werden. Dieses größere Feld kann dann nach oben verlängert werden, so dass es das andere pinke Feld mit dem Fragezeichen und auch noch das gelbe neben dem winzigen pinken weiter oben berührt. Das kleine blaue Feld in der Mitte zwischen den beiden pinken Feldern, kann auch mit den beiden pinken zu einem größeren zusammengefasst werden. Wenn du die Lösung dafür gefunden hast, verrate ich dir auch noch wie das Bild in zwei große Teile zerschnitten werden kann, so dass es gar keine Lösung mehr gibt.
Franz Scheerer
Klar, das schmale rote Feld in der Mitte mit Fragezeichen sollte auch noch bis zu dem jetzt vergrößerten pinken Feld verlängert werden. Sonst ist die Lösung natürlich ganz einfach.
Franz Scheerer
Ok, die Lösung ist immer noch recht leicht zu finden. Nach dem Tausch von einigen pinken und roten Feldern kann das gelbe Feld oben pink gefärbt werden und die Lösung ist ein Kinderspiel. Jetzt kann das schmale rote Feld mit dem Fragezeichen bis hinauf zum kleinen pinken neben dem gelben verlängert werden. Jetzt ist die Lösung schon schwieriger.
Franz Scheerer
Schwieriger ja, aber nicht unmöglich. Es ist völlig egal, wie oft du noch Felder in dieses Bild einfügst oder zusammenfasst, das Bild zerschneidest oder erweiterst. Das ändert überhaupt nichts, weil du letztlich immer wieder genau das Selbe machst: Du suchst nach Stellen, an denen ein Feld möglichst viele andere Felder berührt. Dabei vergisst du, dass das neu geschaffene Feld automatisch dafür sorgt, dass sich andere Felder nicht mehr berühren. An diesen Stellen kann man die Felder dann problemlos umfärben. (Mathematisch: Der Graph erhält einen neuen Knoten, dabei werden vorhandene Verbindungen unterbrochen.)
Thiemo
Wenn das überhaupt nichts ändert, kann es ja auch nicht schwieriger werden. Ich sehe jedenfalls unzählige Möglichkeiten das Bild so zu verändern, dass jedenfalls keine triviale Umfärbung erkennbar ist, um wieder mit vier Farben auskommen zu können. Es könnten etwa einige blaue Felder an den Rand verlängert werden, so dass vier Farben am Rand liegen, die mit einem zusätzlichen Feld abgedeckt werden könnten. Wird etwa das blaue und das gelbe Feld mit den Fragezeichen nach rechts oben an den Rand verlängert, kann dies auch nicht mit einer einfachen Vertauschung von blau und gelb gekontert werden. Schließlich könnten verschiedene Kopien der Abbildung erstellt werden und diese derart kombiniert werden, dass eine Färbung mit nur vier Farben unmöglich wird.
FssWsb
Das Rätsel kann auch durch die Verschiebung der dreigeteilten Umrandung wesentlich erschwert werden. Das rote Drittel kann am linken Rand nach unten bis zu dem größeren roten Feld verlängert werden. Das gelbe kann am rechten Rand nach oben bis zu dem gelben Feld mit Fragezeichen verlängert werden. Damit wird das Rätsel wieder richtig kniffelig.
FssWsb
Jetzt habe ich eine Lösung gefunden, für die verschobene Umgebung. Blau und pink wird unten vertauscht, die rote Umgebung wird pink ... Wenn aber die rote Umgebung zusätzlich auf der rechten Seite bis zu dem blauen Feld unten rechts erweitert wird, statt die gelbe Umgegbung zu erweitern, scheint es keine Lösung mehr zu geben.
FssWsb
Warum ist das jetzt schwierig: Die rote Umgegung, das rote Feld rechts unten und die pinke Umgebung benötigen in jedem Fall drei verschiedene Farben. Dies ist jedoch unmöglich, wenn alle an blau und gelb angrenzen. Mit dem Pink-Blau-Tausch wird dieses Rätsel aber gelöst. Aber mit der größeren roten Umgebung klappt es trotzdem nicht so einfach. Aber sicher kannst du mir erklären wie das Rätsel mit der Knotenfärbung in der Graphentheorie gelöst werden kann.
FssWsb
Wie ich schon sagte: Es spielt nicht die geringste Rolle.
Thiemo
Stimmt, auch bei diesem Bild scheint es ziemlich schwierig zu werden, wenn die rote Umgebung nach unten bis zu den beiden (in diesem Bild) roten Feldern ausgeweitet wird. Falls hier die das blaue und das gelbe Feld am rechten Rand mit Fragezeichen an den oberen Rand geführt wird und eine weitere Umgebung eingeführt wird, könnte eventuell noch pink und blau getauscht werden, um eine vierte Farbe am Rand zu verhindern. Falls aber die pinke Umgebung blau gefärbt wird ... Ok, dann braucht gar nicht getauscht werden. Naja, vielleicht sollte noch ein Feld mehr an den Rand geführt werden. Ich denk nochmal darüber nach.
FssWsb
Das kleine blaue Feld über dem großen, pinken, schwarzumrandeten ist natürlich keine Erschwernis, weil es nur drei Nachbarn hat. Es könnte zu dem Blauen verlängert werden. Die Sache kann natürlich leicht durch einen Tausch von pink und blau korrigiert werden. Mit der Umrandung ist es aber nicht so einfach. Als weitere Erschwernis bietet sich noch an die rote Umgebung etwa über dem gelben Feld in der Mitte in zwei Teile zu teilen. Dann natürlich ohne weitere Felder am Rand. Nach der Teilung gibt es aber immerhin schon vier.
FssWsb
Hallo, Erde an Schwachkopf: Es ist schnurzpiepegal, welche Felder du wohin verlängerst. Jedesmal, wenn du irgendwo eine neue Verbindung zwischen zwei Feldern schaffst, wird dabei zwangsläufig die Verbindung zwischen irgendwelchen anderen Feldern aufgelöst. Mit anderen Worten: Du schaffst mit deinen Versuchen, die Lösung schwerer zu machen, unabsichtlich immer neue Lösungsmöglichkeiten. Dieses idiotische Spiel kannst du unendlich lange fortsetzen, ohne jemals etwas zu erreichen. Du drehst dich im Kreis und jagst deinen eigenen Schwanz.
Thiemo
Ich habe jetzt eine Weile nach Lösungen mit der vergrößerten roten Umgebung gesucht aber keine gefunden. Vielleicht könnte ein Computer, der einfach alles durchprobiert, doch noch eine finden. Es könnte auch eine einzige Umgebung benutzt werden, also die 19 - sofern ich richtig gezählt habe - äußeren Felder alle zum Rand hin vergrößert werden. Jetzt könnten von diesem Gebilde 64 Kopien gemacht werden und diese Quadrate die Felder eines Schachbretts bilden. Dieses Schachbrett könnte dann wieder eine dreigeteilte Umgebung erhalten. Dann kann ich wirklich keine Lösung mehr finden. Kannst du mir verraten, wie die Lösung für so ein schwieriges Rätsel mit Hilfe der Knotenfärbung in der Graphentheorie gefunden werden kann ? Obwohl - eigentlich ist es ja schnurzpiepegal wie und ob man so was mit nur vier Farben färben kann oder ?
Franz Scheerer
Falls dir das jetzt zu einfach ist, kannst du von dem Schachbrett (ohne Rahmen) wieder 64 Kopien machen und ein größeres Schachbrett daraus bauen. Dieses Schachbrett kannst du dann in deinen Sandkasten werfen ... Der Vier-Farben-Satz ist also mehr oder minder offensichtlich falsch oder ?
Franz Scheerer
Wuff.
Thiemo
Lustige Diskussion hier. ;-) Danke für deinen interessanten Kommentar. Ich setze mal unten einen Backlink für den geneigten Leser.
Gruß,
Magdalena
Der Vierfarbensatz ist in der Tat vergleichbar mit der Aussage es gäbe beim Sudoku genau 6.670.903.752.021.072.936.960 Lösungen, also verschiedene Möglichkeiten die 81 Felder mit den Ziffern 1 bis 9 den Regeln entsprechend zu füllen. Es heißt dies sei mathematisch beweisen, ohne das irgendwo ein nachvollziehbarer Beweis zu finden wäre. Tatsächlich ist die Behauptung unglaubhaft, da es (9*8*7* ... *2*1) hoch 3 Möglichkeiten gibt die 27 Felder in der Diagonalen auszufüllen. Schwierige Sudoku-Rätsel haben auch etwa 27 vorgegebene Ziffern (manche sogar noch deutlich weniger). Die Zahl der Möglichkeiten sollte
daher eher in der Größenordnung von 47.784.725.839.872.000 vermutet werden. Aber wenn jemand behauptet der Mathematiker X habe etwas bewiesen, wird dies selten kritisch hinterfragt. In Wahrheit wird erst erkennbar, ob es es Lösung gibt, wenn man konkret beginnt Zahlen einzusetzen und erst am Schluss sieht man, ob es aufgeht. Die Zahl der Lösungen beim Sudoku ist unbekannt, ebenso wie der Vierfarbensatz höchst wahrscheinlich falsch ist.
Internet-Experte

Kommentare zu diesem Beitrag können per E-Mail an den Autor gesandt werden.

[ ← Zurück zur Übersicht ]

Impressum & Datenschutz