The Tetris Proof
I spent two years in graduate school working toward a Masters in Computer Science, with a focus in theory, while also serving as a teaching assistant for EECS 376, Foundations of Computer Science. I often joke to friends that the material taught in class had little practical value, which has more than a grain of truth; theoretical computer science is usually far-removed from my daily life as a software engineer. In fact, some of my professors advised me against specializing in theory, recommending more lucrative specialties like Artificial Intelligence or Security. Even upon graduating, I felt uncertain of my choice until one memorable incident showed me I definitely made the right decision.
A few years ago, I was living in an apartment with a group of friends, all of us on the geekier side. One day, a roommate came back and, barely able to contain his excitement, informed us that he had just purchased a set of Tetris piece magnets. Upon hearing the news, we decided to arrange them on the refrigerator immediately. Tearing open the package, we saw that the Tetris pieces were laid out in neat rows on a single sheet, each row containing 7 copies of the same tetromino. As you may remember, there are exactly 7 tetrominoes, making a total of 49 total magnets.
We rushed to move the magnets from the packaging to their new home on the fridge, enjoying the crisp snap of each magnet to the cold surface. At first, we placed them at random with no particular pattern. Then, following our instincts, we began arranging them tightly so that they hugged one another; there are few things more satisfying than tidying up (unfortunately, this does not seem to apply to my room). Somehow, wordlessly, we understood this was the right way to play with our new toy, and began creating the most compact, neatly aligned set of pieces possible. As the clump grew, someone asked if we could arrange the pieces into a square. Quickly doing the math, I pointed out that, since each tetromino has an area of 4 units, they covered a total area of 7x7x4, a perfect square. Delighted by our serendipitous situation, we began to construct a 14x14 square.
Several minutes into the game, we almost had our square, with just a few pieces remaining and only a handful of places to put them. No matter, we thought; a bit of nudging here and shuffling there would get us to the solution in no time. However, like unruly children, each time we ordered new pieces into place, others would fall out of line. After a few attempts, this phenomenon began to feel inevitable and I lost enthusiasm.
Literally and figuratively taking a step back — the front of the refrigerator was getting crowded and my friends were still as engaged as before –– I began to reconsider if it was even possible to build the square. Sure, we had the right amount of material, but what if our pieces could not be fit together correctly? And if it was impossible, could I prove that was the case? As I mulled this over, another question with a similar flavor wandered into my mind.
The Mutilated Chessboard problem is discussed in almost every introductory class to Discrete Mathematics:
Suppose a standard 8×8 chessboard has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2×1 so as to cover all of these squares?
The answer is no, and we can formally prove it by contradiction. The key fact is that the mutilated chessboard has 2 white squares removed, leaving 30 white squares and 32 black squares. On the other hand, each domino must cover exactly one white square and one black square. Assume there is a tiling of the mutilated chessboard such that dominoes cover the 62 squares. Then 31 of them must be white and 31 must be black, a contradiction.
Our Tetris problem resembled the Mutilated Chessboard problem; could some of the thinking behind the proof carry over as well? There was no chessboard in our problem. But if we imagined that our square was colored like a chessboard, would that help us solve it? Following a hunch, I started mentally checking through the tetrominoes to see how they might be colored if laid out on a 14x14 “chessboard”. Six of the tetrominoes, the “straight”, “square”, the two “L” shapes and two “skew” shapes must all be composed of an equal number of black and white squares, like dominoes. Note that this is true regardless of how the shapes are rotated.
However, the last tetromino, the “T” shape, is special. Depending on its position on a chessboard, it is either composed of 3 black squares and 1 white, or 3 white squares and 1 black.
In a flash, I saw the answer and proof clearly. The 42 non-“T”-shaped tetrominoes comprise an equal number of white and black squares. However, there is no way that the 7 “T”-shapes could add up to an equal number of blacks and whites (formal proof is left as an exercise to the reader). Therefore, the total number of black and white squares covered by all 49 tetrominoes cannot be equal. But if our 14x14 square were colored like a chessboard, it would contain an equal number of white and black squares. Therefore, by contradiction, there is no way to construct a square entirely from our set of pieces.
While I had been deliberating, my friends had been hard at work rearranging pieces. Though I now knew the task was Sisyphean, they were still in the deep state of flow that occurs when puzzle-solving, their brows furrowed with concentration. With inappropriate glee, I informed them of my magnificent discovery. As I sketched out the proof above, their faces changed, first to denial and then to disappointment. Once convinced I was right, they begrudgingly returned to their everyday routines.
With a satisfied sigh, I sat back and took measure of myself. Sure, my classmates who focused on Artificial Intelligence and Machine Learning were working on self-driving cars and other exciting projects sure to change the world, but would they ever be able to save their friends from working toward an unattainable goal? As Aristotle said, “the roots of education are bitter, but the fruit is sweet”, and the sweetest fruit of all is the one you share with your friends.
