Ken Jennings


December 8, 2008

If you think Russia never invented anything good except for vodka, show trials, and creepily tattooed mafiosi, you are obviously not a child of the early 1990s. Duh, Tetris! I was briefly obsessed with the hit video game Tetris in high school. Tetris is a game about mastering chaos–in fact, turning messy chaos into neat, beautiful order through sheer force of will. It’s a fantasy about cleaning your room (or your mental room, or whatever). I saw the little falling blocks whenever I closed my eyes.

I also found myself idly drawing Tetris pieces in boring classes/work meetings/worship services/etc. And, in doing so, I noticed that the seven figures in Tetris constituted every possible combination of four square tiles connected on their edges. I noticed that there were two pairs of mirror images and three other shapes. I started to wonder what Tetris would be like if the game was played with, say, 3- or 5-tile pieces instead. How many of those pieces would there be?

The 1-tile Tetris game (Unis?) would be pretty dull: there’s only one piece.

And as long as you scatter them reasonably evenly, you could play indefinitely. The 2-tile game (Duis, I guess) also only has the one piece, because you can rotate falling pieces:

Tri-is would have two different pieces:

We already know Tetris has five pieces, two of which have reflections:

And a hypothetical Pentis or Hextis? Played by super-powerful 4-dimensional aliens or whatever? Well, my doodling led me to believe there were twelve 5-tile pieces:

And 35 6-tile pieces.

I remember being a little disappointed that this progression (1, 1, 2, 5, 12, 35 . . .) didn’t turn out to be something cool like the Fibonacci sequence. But what did my Tetris sequence represent mathematically, if anything? Was there some expression that would give you the value of the nth term? And where did the sequence go next? It got awfully hard to count pieces after they got bigger then 6 tiles. You never knew if you were missing some shapes or duplicating others (or reflections of others). The only reason I was doing this crap in meetings in the first place was because of my short attention span, for crying out loud. It was definitely too short to keep track of hundreds of geometric figures.

I knew that four-square Tetris pieces were called “tetrominoes” but I didn’t know how to generalize the term to other sizes, so I called them “n-ominoes.” Recently, doing some Googling, I realized that was my big mistake: I’d been calling them the wrong thing all this time. If you know these figures are really called “polyominoes,” the Internet is (surprise!) full of abstruse information and complicated theory about them. It turns out that mathematicians have been fooling around with polyominoes for over a century. In fact, they inspired Tetris, not the other way around.

And plenty of research has been done on my little (1, 1, 2, 5, 12, 35 . . .) sequence. (The next few terms are 108, 369, and 1,265, it turns out.) There are laborious inductive algorithms to generate each term from the previous one. There are even ways to estimate each term, within certain bounds. But I learned that, in one respect at least, science had advanced no further than my scratch pad: there’s still no known equation that’ll magically give you the nth term in the sequence!

Which–though I’m obviously a naive math novice–seems weird to me. Is it really possible that this simple, intuitive sequence–one you could informally explain in a few sentences to a 10-year-old–has no way to express it mathematically? Or can it be shown that there must be an algebraic way to compute each term, but it’s so complicated it has yet to be discovered? I don’t know enough about the theory here to say one way or another. But I’m pretty happy to have found out, finally, what “polyominoes” are really called, and to have found that Wikipedia page. Next time I find myself trying to doodle all 108 “heptominoes,” I can just bring up this graphic instead. Aahhhh. Order out of chaos.

Posted by Ken at 1:19 pm