• By Markus Pössel
  • Lesedauer ca. 4 Minuten
  • Comments Off on Tetris und einfache Fragen, die nicht einfach zu beantworten sind

Tetris und einfache Fragen, die nicht einfach zu beantworten sind

BLOG: Heidelberg Laureate Forum

Laureates of mathematics and computer science meet the next generation
Heidelberg Laureate Forum
Mira Shalah at the HLF 2018. Image: M. Shalah
Mira Shalah beim HLF 2018. Image: M. Shalah

Einer der spannenden Aspekte von Mathematik ist, dass es selbst bei Fragen, die sich sehr einfach formulieren lassen, ausnehmend schwer sein kann, die korrekte Antwort zu finden. Fragen Sie einfach Mira Shalah, eine der Nachwuchsforscherinnen beim diesjährigen Heidelberg Laureate Forum. Wenn Sie irgendwann einmal Tetris gespielt haben, das Spiel mit den einfachen Blockformen und dem hohen Suchtpotenzial, dann wissen Sie: das ist vom Aufbau her eigentlich ein ganz einfaches Spiel. (Dass es in der Praxis beliebig schwierig werden kann, wenn die Blöcke dann immer schneller fallen, steht auf einem anderen Blatt und ändert nichts daran, dass die Formen der Tetris-Blöcke jede für sich wirklich einfach sind.)

Aber wie sich herausstellt, sind selbst die einfachen Tetris-Formen nur eine Verallgemeinerung weit von einem mathematischen Problem entfernt, das sehr schwer zu lösen ist. Stellen Sie sich ein quadratisches Gitter vor. Färben Sie nun vier der quadratischen Felder ein, aber stellen Sie sicher, dass Sie eine verbundene Struktur erhalten – jedes ausgefüllte Feld sollte sich eine Kante mit mindestens einem anderen ausgefüllten Feld teilen. Die resultierenden Formen werden Tetrominos genannt, und sie sind ein Sonderfall von ”Gittertieren”, dem allgemeineren Ausdruck für derartige verbundene Formen auf quadratischen und auch auf allgemeineren Gittern.

Tetrominos

Hier sind zwei sehr einfache Tetrominos:
Wir sind nicht daran interessiert, wo genau in dem Gitter sich diese Gebilde befinden – wenn wir also beispielsweise die linke Form um ein Quadrat nach oben verschieben würden, würden wir dies immer noch als dasselbe Tetromino betrachten. Technisch gesehen geht es hier nur um “fixierte Tetrominos”. Rotation dagegen führt zu einem neuen Tetromino. In unserem Beispiel betrachten wir die beiden dargestellten Tetrominos als unterschiedlich, da sie um 90 Grad relativ zueinander gedreht sind.

Hier sind zwei weitere Gebilde, die jedem Tetris-Anwender bekannt sind:

Es handelt sich um eine L-Form und das Spiegelbild einer L-Form. Und für jede der beiden Formen gibt es wieder insgesamt vier Versionen, die einer Drehung um 0, 90, 180 und 270 Grad gegenüber der hier gezeigten Ausrichtung entsprechen. Hier sind drei weitere einfache Formen:

Das linke Gebilde hat wiederum vier verschiedene Versionen, entsprechend einer Drehung um 0, 90, 180 und 270 Grad der abgebildeten Version. Die quadratische Form in der Mitte bleibt durch solche Drehung um Vielfache von 90 Grad unverändert. Die rechte Form hat eine zugehörige Spiegelform, und sowohl sie selbst als auch die Spiegelform haben zwei verschiedene Versionen, die sich durch Rotation um 90 Grad unterscheiden. (Drehen Sie diese Formen dagegen um 180 Grad, dann landen Sie dort, wo Sie angefangen haben!)

Das macht insgesamt 2 + 4 + 4 + 4 + 4 + 1 + 2 + 2 + 2 = 19 Tetrominos, und das ist auch schon alles – das sind alle Tetrominos, alle Formen, denen wir in einem gewöhnlichen Tetris-Spiel je begegnen werden.

Jenseits von Tetris

Was wäre, wenn wir feste Pentominos in Betracht ziehen würden, die jeweils aus fünf quadratischen Feldern bestehen? Wie viele verschiedene solche Pentominos gibt es? Wenn Sie Mathematiker kennen, werden Sie nicht überrascht sein, dass sich dann recht bald die Frage anschließt, wieviele Polyominos (das ist der allgemeine Begriff) mit N zusammengesetzten Quadraten für eine ganze Zahl N es gibt. Die Antwort ist übrigens nicht nur für Mathematiker, sondern auch in der statistischen Physik von Interesse – ähnliche Fragen stellen sich, wenn Sie versuchen, verzweigte Polymere oder Perkolationsprozesse (das Durchtreten von Flüssigkeiten durch eine poröse feste Struktur) zu modellieren.

Und haben wir sie, die Frage, die leicht zu formulieren, aber sehr schwer zu beantworten ist! Tatsächlich hat Mira einen gehörigen Teil der Forschung für ihre Doktorarbeit am Technion in Haifa, Israel, darauf verwandt, zumindest bestimmte Teile der Antwort zu finden. (Als sie 2017 ihren Abschluss machte, war sie übrigens eine der ersten israelisch-arabischen Frauen mit einem Doktorgrad in Informatik.)

Wenn N größer wird, nähert sich die Anzahl der Möglichkeiten für N-Minos dem exponentiellen Wachstum an. Anders ausgedrückt: Die Zahl der unterschiedlichen Formen nimmt in Abhängigkeit wie Lambda hoch N zu, wobei Lambda eine für Polyominos allgemein charakteristische Wachstumskonstante ist. Aber welchen Wert hat Lambda? Da die explizite Anzahl der Möglichkeiten nur bis zu N=56 berechnet wurde (dabei ergibt sich eine 32-stellige ganze Zahl), ist es notwendig, auf Tricks zurückzugreifen.

Um zum Beispiel eine untere Grenze für die Wachstumskonstante zu berechnen, betrachteten Mira und ihre Kollegen ein Gitter, das wie ein Zylinder aufgerollt wird. Für Polyominos auf einem solchen Zylinder gibt es weniger Möglichkeiten als in der Ebene (einfach weil es weniger Möglichkeiten gibt, ein Polyomino in der aufgerollten Richtung fortzusetzen als in einer unendlich ausgedehnten Ebene). Eine andere Konstruktion ermöglicht die Abschätzung einer oberen Grenze. In ihrer Doktorarbeit gelang es Mira konkret, die untere Grenze für die Wachstumskonstante von 3,98 auf 4,00253 und die obere von 4,65 auf 4,5252 zu verbessern.

Einfache Frage und anspruchsvolle Forschung um auch nur einen Teil der Antwort zu finden. Falls Sie in nächster Zeit zufällig Tetris spielen sollten: denken Sie an die Mathematik, die dahintersteckt! Mathematik ist eben wirklich überall

 

Avatar photo

Markus Pössel hatte bereits während des Physikstudiums an der Universität Hamburg gemerkt: Die Herausforderung, physikalische Themen so aufzuarbeiten und darzustellen, dass sie auch für Nichtphysiker verständlich werden, war für ihn mindestens ebenso interessant wie die eigentliche Forschungsarbeit. Nach seiner Promotion am Max-Planck-Institut für Gravitationsphysik (Albert-Einstein-Institut) in Potsdam blieb er dem Institut als "Outreach scientist" erhalten, war während des Einsteinjahres 2005 an verschiedenen Ausstellungsprojekten beteiligt und schuf das Webportal Einstein Online. Ende 2007 wechselte er für ein Jahr zum World Science Festival in New York. Seit Anfang 2009 ist er wissenschaftlicher Mitarbeiter am Max-Planck-Institut für Astronomie in Heidelberg, wo er das Haus der Astronomie leitet, ein Zentrum für astronomische Öffentlichkeits- und Bildungsarbeit, seit 2010 zudem Leiter der Öffentlichkeitsarbeit am Max-Planck-Institut für Astronomie und seit 2019 Direktor des am Haus der Astronomie ansässigen Office of Astronomy for Education der Internationalen Astronomischen Union. Jenseits seines "Day jobs" ist Pössel als Wissenschaftsautor sowie wissenschaftsjournalistisch unterwegs: hier auf den SciLogs, als Autor/Koautor mehrerer Bücher und vereinzelter Zeitungsartikel (zuletzt FAZ, Tagesspiegel) sowie mit Beiträgen für die Zeitschrift Sterne und Weltraum.