Tetris and the curious case of simple questions with tough answers
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.
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.
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.