Tetris and the curious case of simple questions with tough answers

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 at the HLF 2018. Image: M. Shalah

One of the most fun things about mathematics is that sometimes you can formulate very simple questions that turn out surprisingly hard to answer. Just ask Mira Shalah, one of this year’s Young Researchers at the Heidelberg Laureate Forum. After all, if you’ve ever played Tetris, with its characteristic simple block shapes dropping from the top of your screen, at least at a fundamental level, it is a fairly simple game. (Admittedly, with increasing drop speed it becomes an arbitrarily hard game sooner than you would like, but that does not take away from the fact that the Tetris shapes are really simple in and of themselves.)

But as it turns out, even the simple Tetris shapes are just one generalization away from a mathematical problem that is fairly tough to solve. Imagine that you have a square grid. Now color in four of the squares, but make sure that you get a connected structure – each filled-in square should share an edge with at least one other filled-in square. The resulting shapes are called tetrominoes, and they are a special case of ”lattice animals,” that is, of similarly connected shapes on more general lattices.

Tetrominos

Here are two very simple tetrominos:
We are not interested in the shapes’ positions, so if we were to shift, say, the left shape up by one square, we would still consider this the same shape. In technical terms, all we will talk about here are “fixed tetrominoes”. Rotation is allowed to make a difference, though; in the context we have here, we regard those two shapes as distinct, since they are rotated by 90 degrees relative to each other.

Here are two other shapes familiar to any Tetris user:

It’s an L shape and the mirror image of an L shape. And for each of the two shapes, there are four versions, corresponding to rotation by 90, 180 and 270 degrees relative to the orientation shown here. Here are three more simple shapes:

The left-hand shape again has four different versions, corresponding to a rotation by 0, 90, 180 and 270 degrees. The square shape in the middle is unchanged by rotation. The right-hand shape has a corresponding mirror shape, and both itself and the mirror shape have two different rotation versions: 0 and 90 degrees. (Rotate by 180 degrees, and you end up where you started!)

This makes a total of 2 + 4 + 4 + 4 + 1 + 2 + 2 = 19 tetrominoes, and that’s it – that’s all tetrominoes there are, all we will ever encounter in an ordinary Tetris game.

Beyond Tetris

What if we considered fixed pentominoes, each consisting of five squares? How many different varieties are there? If you know mathematicians, you will not be surprised that pretty soon we are asking how many polyominoes (the general term) with N constitutent squares there are for any integer N. Incidentally, this is not only of interest to mathematicians, but also to statistical physicists – similar questions pop up if you try to model branched polymers, or percolation processes.

And that turns out to be a question that is easily formulated, but very hard to answer! In fact, Mira spent much of her PhD at the Technion in Haifa, Israel, trying to find certain parts of the answer. (Incidentally, when she graduated in 2017, she became one of the first Israeli-Arab women to earn a PhD in computer science.)

As N grows larger, the number of possibilities for N-ominoes approach exponential growth, the number of possibilities increasing as some growth constant lambda to the power of N. But which growth constant? Since explicit numbers of possibilities have been computed only up to N=56 (where the number of possibilities is a ridiculously large 32 digit integer), it is necessary to resort to tricks.

For instance, to compute a lower bound for the growth constant, Mira and her colleagues resorted to a lattice that is rolled up like a cylinder – compute the number of fixed polyominoes on such a cylinder, and there will be fewer than on a plane (simply because there are fewer ways of extending the polynomino in the rolled-up direction than in an infinite plane). Similar construction allow for estimating an upper bound. In her thesis work, Mira managed to improve the lower bound from 3.98 to 4.00253, and the upper bound from 4.65 to 4.5252.

And there you have it – a deceptively simple question, and a challenging road to finding even part of the answer. Think about this if you should find yourself playing Tetris at some point. Mathematics is everywhere.

 

 

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.

2 comments

  1. Spell-checking and the reasonable applicability of a single answer to distinct problems

    Markus Pössel schrieb (27. September 2018):
    > Tetrominos […] In technical terms, all we will talk about here are “fixed tetrominoes”. Rotation is allowed to make a difference [… and mirroring is allowed to make a difference, too.]

    > As N grows larger, the number of possibilities for N-ominoes [… increases] as some growth constant lambda to the power of N.

    However, such growth with its particular value of the asymptotic growth constant (also known as “Klarner’s constant”) does apply not only to the number of possibilities for the described fixed N-ominoes, but similarly and with the exact same growth constant value also to the number of possibilities for free N-ominoes, which count as one and the same all (namely up to possibly eight) distinct variants of fixed polyominoes related through rotation or mirroring;
    since the N-th root of 8 approaches 1, as N grows ever larger.

  2. Bonus commentary on a question asked, and answered

    Question:
    How many squares of a p-by-q rectangular grid may be filled in at most
    such that the resulting shape is no polyomino ?

    Answer:
            Max[ (p * q) – 2, Max[ p * (q – 1), q * (p – 1) ] ].

    Considering specificly only square grids, i.e. p-by-p grids, the corresponding number (of the most squares which may be filled without resulting in a polyomino) is accordingly:

            Max[ (p^2) – 2, (p^2) – p ].

    One of the fun things about mathematics is that you can (always) formulate and (sometimes) even answer questions without worrying whether someone else may have already answered or even only asked them before