Logikspiel für iPhone und Android
Vier Farben genügen - die Kunst liegt in der Reihenfolge.
Ein atmosphärisches Kartenrätsel über Grenzen, Farben und die stille Eleganz eines der berühmtesten Sätze der Mathematik.
Der Vier-Farben-Satz
Jede ebene Landkarte lässt sich mit höchstens vier Farben so einfärben, dass benachbarte Gebiete niemals dieselbe Farbe tragen.
Benachbart sind zwei Gebiete nur dann, wenn sie eine gemeinsame Grenzlinie teilen. Ein einzelner Berührungspunkt reicht nicht. Genau diese kleine Unterscheidung macht aus einer scheinbar einfachen Malaufgabe ein präzises mathematisches Problem.
Die Vermutung stammt von einem Studenten: 1852 färbte der Londoner Francis Guthrie eine Karte der englischen Grafschaften und bemerkte, dass er nie mehr als vier Farben brauchte, wie er die Grenzen auch zog. Sein Bruder trug die Frage an den Mathematiker Augustus De Morgan heran, der sie noch am selben Tag - dem 23. Oktober 1852 - in einem Brief an William Rowan Hamilton weitergab. Von da an ließ das Problem die Mathematik nicht mehr los.
1878 trug Arthur Cayley die weiterhin ungelöste Frage vor die London Mathematical Society, ein Jahr später veröffentlichte Alfred Kempe einen Beweis. Er stand elf Jahre lang unangefochten, bis Percy Heawood 1890 eine Lücke darin fand. Kempes Grundidee - sogenannte Kempe-Ketten - blieb trotzdem der Ausgangspunkt fast aller späteren Beweisversuche, auch des erfolgreichen.
Der Beweis
Fast 125 Jahre lang blieb der Vier-Farben-Satz eine Vermutung. Erst 1976 bewiesen Kenneth Appel und Wolfgang Haken an der University of Illinois, dass sie stimmt - aber nicht auf dem Papier. Sie reduzierten das Problem auf 1.936 unvermeidbare Kartenmuster, später auf 1.476, und ließen einen Computer jedes davon rund 1.200 Stunden lang durchrechnen. Kein Mathematiker konnte den Beweis mehr von Anfang bis Ende von Hand nachvollziehen - er war schlicht zu lang.
Das sorgte für Streit. War ein Beweis, den man nicht mehr lesen, sondern nur noch laufen lassen konnte, überhaupt ein Beweis? Die Mathematik-Fakultät der University of Illinois beantwortete die Frage auf ihre Weise.
„Four colors suffice.“Poststempel der University of Illinois, nach 1976 jahrelang im Umlauf
Die Zweifel verstummten erst mit der Zeit - siehe die Zeitleiste rechts. 2005 ließen Georges Gonthier und Benjamin Werner den kompletten Beweis noch einmal von einem Beweisassistenten namens Coq überprüfen: Zeile für Zeile, ohne die kleinste Lücke für Zweifel.
Appel & Haken: 1.476 geprüfte Kartenmuster, ca. 1.200 Stunden Rechenzeit - der erste Beweis.
Appel & Haken veröffentlichen die vollständige, rund 400 Seiten lange Beweisführung.
Robertson, Sanders, Seymour & Thomas verkleinern den Beweis auf 633 Fälle.
Gonthier & Werner lassen den kompletten Beweis vom Beweisassistenten Coq bestätigen.
Der Vier-Farben-Satz beschreibt reine Geometrie. Sobald echte Länder und echte Grenzen ins Spiel kommen, zeigt er auch seine Grenzen.
Nachbarschaft zählt nur, wenn zwei Gebiete eine echte Grenzlinie teilen. Am „Four Corners“ in den USA berühren sich Arizona, Colorado, New Mexico und Utah in einem einzigen Punkt - nach dem Satz dürften alle vier sogar dieselbe Farbe tragen. Auf echten Karten wird trotzdem meist unterschiedlich eingefärbt, damit die Grenze überhaupt sichtbar bleibt.
Jedes Gebiet muss außerdem zusammenhängend sein. Russlands Oblast Kaliningrad liegt getrennt vom übrigen Staatsgebiet, eingeschlossen zwischen Polen und Litauen. Verlangt eine Karte, dass beide Teile dieselbe Farbe tragen, kann sie mehr als vier Farben brauchen - der Satz kennt eben nur Geometrie, keine Politik.
Cartographer übersetzt den Vier-Farben-Satz in 120 handgezeichnete Inselkarten, verteilt auf vier Schwierigkeitsstufen. Die Regel bleibt immer dieselbe - nur die Karten werden verschlungener.
Teilen zwei Gebiete eine Grenze, brauchen sie unterschiedliche Farben. Mehr Regeln gibt es nicht.
Vier Schwierigkeitsstufen führen von einfachen Inseln zu Karten, in denen ein früher Fehler sich erst viele Gebiete später rächt.
Jede gelöste Karte entfaltet sich wie ein altes Atlasblatt - ruhig, mit Gold als stiller Belohnung am Ende.
Vollwertige Demo
Keine Simulation - das ist Cartographer selbst, so wie es auf dem iPhone läuft: mit Kampagne, Fortschritt, Musik und allen frei spielbaren Karten. Einfach antippen und loslegen.
Antworten auf das, was am häufigsten gefragt wird - zur Mathematik genauso wie zur App.
Weil sich jede ebene Karte als planarer Graph beschreiben lässt, und jeder planare Graph sich mit höchstens vier Farben so färben lässt, dass verbundene Punkte nie dieselbe Farbe teilen. Das ist der Kern des Vier-Farben-Satzes - bewiesen, nicht nur beobachtet.
Kenneth Appel und Wolfgang Haken 1976 an der University of Illinois, mit einem computergestützten Beweis über 1.476 Kartenmuster. 2005 wurde der komplette Beweis von Georges Gonthier und Benjamin Werner formal mit dem Beweisassistenten Coq bestätigt.
Nicht vollständig - das war schon 1976 der Streitpunkt. Die leichtere Variante, der Fünf-Farben-Satz, lässt sich mit Kempes Methode dagegen komplett von Hand beweisen.
Weil politische Karten Regeln verletzen, die der Satz voraussetzt - etwa wenn ein Land aus getrennten Exklaven besteht, die dieselbe Farbe tragen sollen, wie Russland mit der Oblast Kaliningrad.
Ja. Die ersten 10 Karten sind komplett kostenlos, ohne Werbung und ohne Konto. Für die restlichen 110 der insgesamt 120 handgezeichneten Inselkarten gibt es eine einmalige Freischaltung statt eines Abos.
Aktuell im App Store für iPhone. Eine Android-Version über Google Play ist in Vorbereitung. Die Demo weiter oben läuft direkt im Browser, auf jedem Gerät.
Nein. Die Regel lässt sich in einem Satz erklären: Nachbarn dürfen nie dieselbe Farbe haben. Den Rest übernehmen ein Gefühl für Karten und etwas Geduld.
Bereit für mehr?
Die Demo zeigt nur den Anfang. Die App bringt alle 120 handgezeichneten Karten mit - freigeschaltet durch einen einmaligen Kauf statt ein Abo, spielbar offline und ganz ohne Werbung.
Die Geschichte und die Beweise auf dieser Seite stützen sich auf diese Quellen - für alle, die tiefer einsteigen wollen.