Mathema (entwickelt von Hugo Parlier und Paul Turner) ist keine klassische App, sondern eher ein interaktives Buch.
Ich habe vor einigen Wochen einen Vortrag von Hugo Parlier über sein Buch/seine App gehört.
Aufhänger des Vortrags war die Veranschaulichung von Spielen und Rätseln mittels Graphen, bspw. des Rubik-Würfels.
“Mankind has not seen all positions of the Rubik’s cube”: es gibt 43×1018 mögliche Positionen des Zauberwürfels und nach einer sehr groben Überschlagsrechnung könne die Menschheit in den 42 Jahren seit der Erfindung des Würfels bisher maximal 42×1017 davon gesehen haben.
Die verschiedenen Positionen des Zauberwürfels lassen sich als Knoten eines Graphen veranschaulichen: zwei Knoten werden dann durch eine Kante verbunden, wenn die Positionen durch eine Drehung ineinander überführt werden können. Eine Lösung des Zauberwürfels besteht in einem (möglichst kurzen) Weg von einem gegebenen Knoten zum Ausgangsknoten.
Das ist natürlich ein nicht beherrschbarer Graph mit 43×1018 Knoten. Erstaunlicherweise wurde aber vor einigen Jahren bewiesen, dass der Durchmesser dieses Graphen nur 20 ist. Man kann also von jeder Position in maximal 20 Zügen zur Ausgangsposition kommen.
In dem Vortrag wurden einige der Spiele aus dem e-Buch vorgestellt und mathematisch (meist graphentheoretisch) interpretiert. Zum Beispiel dieses, bei dem es darum geht die Felder so zu verschieben, dass man einfarbige Zeilen bekommt.
Das nächste Spiel ist mathematisch dasselbe wie das vorherige, es sieht nur attraktiver aus.
Beim nächsten Beispiel geht es um Domino. Der Graph der Domino-Zerlegungen ist bekanntlich nicht zusammenhängend: wenn man sich die Felder schachbrettmäßig schwarz und weiß gefärbt denkt, dann kann eine Zerlegung, in der zwei schwarze Felder freigelassen wurden nicht in eine Zerlegung überführt werden, in der ein weißes und ein schwarzes Feld frei sind.
Eine andere Frage ist, ob man jede Zerlegung durch sukzessive 90-Grad-Drehungen je zweier benachbarter Dominosteine (also eines 2×2-Quadrats) in jede andere Zerlegung überführt werden kann. Mit anderen Worten: ob der Flip-Graph zusammenhängend ist.
(Die Bilder lassen sich durch Anklicken vergrößern.)
Das ist tatsächlich der Fall und es wurde von Thurston bewiesen.
Flip-Graphen von Polygonen beschreiben die Dreiecks-Zerlegungen eines gegebenen Polygons. Zwei Dreiecks-Zerlegungen werden dann durch eine Kante verbunden, wenn sie durch einen “Flip” (d.h. die Auswahl der anderen Diagonale innerhalb eines Vierecks) ineinander überführt werden können.
Der Durchmesser dieses Graphen ist 2n-10, wenn n die Anzahl der Ecken des Polygons ist. Man kommt also von einer Zerlegung des n-Ecks in maximal 2n-10 Schritten zu jeder anderen Zerlegung.
Die Buchapp gibt es hier
Kommentare (4)