Saturday, September 06, 2014

How Many Colored Tetrominoes?

Question: How many different colored tetrominoes are there if we allow only four colors total?

Second question: What the heck is a tetromino?

Dominoes are a great game with rectangle tiles, composed of two adjacent squares with certain numbers of pips on them. A tetromino is a group of four adjacent squares, each sharing at least one side with at least one other square. In other words, those little falling shapes made popular in the game Tetris, and all of its knock-off variations, as seen below:

There are five basic arrangements, if you allow for reflection. (That is, if you allow for picking a piece up and flipping it over.) If you only allow for rotation, then there are seven shapes, each of which can be designated a letter of the alphabet to describe it.

In most games, the shapes are different colors because a) it's a great visual, and b) it's a clue to the player that, say, a "J" is falling not an "L". Ditto for the "S" and "Z" pieces.

As with any successful game, there have been many imitations and variations. Even games that are somewhat unrelated produce their own variations, which are suddenly similar to Tetris. I've seen a few of these where the pieces, for a multitude of reasons, are multicolored instead of monocolored, as shown below:

This lead me to thinking about the number of possible colored blocks that could fall in the game of varying shapes and color schemes. My only arbitrary limit was that each block had to contain each of the same four colors. (Naturally, I picked red, yellow, green, and blue, pretty much by default.)

First instinct is to use the Counting Principle: the number of shapes times the number of four-color arrangements. That would give us (7) X (4!), or 7 X 24 = 168.

Unfortunately, first instincts may put you on the right track, but they sometimes leave things out. In this case, we can't forget about rotational symmetry.

The I piece (the line) has rotational symmetry of Order 2. If you rotate it 180 degrees, it looks the same. That makes it the same twice in one 360-degrees rotation. The S and Z pieces also have Order 2 symmetry. The O piece (the square) has rotational symmetry of Order 4. If you rotate it 90 degrees, it looks the same. That makes it the same four times in one 360-degrees rotation.

So we have 3 shapes with 4! color variations, 3 with 4!/2 variations and 1 with 4!/4 variations: 3 X 24 + 3 X 12 + 1 X 6 = 72 + 36 + 6 = 114 possible tetrominoes.

For some reason, I feel better knowing this, and maybe it won't distract me so much next time I play one of these games on the train where I have no wifi. (A Tetris Offensive, perhaps?)

(As always, you're free to correct my math. In the event of an actual mistake, I'll edit my work and pretend I have no idea what you're talking about.)

No comments: