The Mathematics of Tetris

Question

I am a big fan of the old-school games and I once noticed that there is a sort of parity associated to one and only one Tetris piece, the $\color{purple}{\text{T}}$ piece. This parity is found with no other piece in the game.

Background: The Tetris playing field has width $10$. Rotation is allowed, so there are then exactly $7$ unique pieces, each of which is composed of $4$ blocks.

For convenience, we can name each piece by a letter. See this Wikipedia page for the Image ($\color{cyan}{\text{I}}$ is for the stick piece, $\color{goldenrod}{\text{O}}$ for the square, and $\color{green}{\text{S}},\color{purple}{\text{T}},\color{red}{\text{Z}},\color{orange}{\text{L}},\color{blue}{\text{J}}$ are the others)

There are $2$ sets of $2$ pieces which are mirrors of each other, namely $\color{orange}{\text{L}}, \color{blue}{\text{J}}$ and $\color{green}{\text{S}},\color{red}{\text{Z}}$ whereas the other three are symmetric $\color{cyan}{\text{I}},\color{goldenrod}{\text{O}}, \color{purple}{\text{T}}$

Language: If a row is completely full, that row disappears. We call it a perfect clear if no blocks remain in the playing field. Since the blocks are size 4, and the playing field has width $10$, the number of blocks for a perfect clear must always be a multiple of $5$.

My Question: I noticed while playing that the $\color{purple}{\text{T}}$ piece is particularly special. It seems that it has some sort of parity which no other piece has. Specifically:

Conjecture: If we have played some number of pieces, and we have a perfect clear, then the number of $\color{purple}{\text{T}}$ pieces used must be even. Moreover, the $\color{purple}{\text{T}}$ piece is the only piece with this property.

I have verified the second part; all of the other pieces can give a perfect clear with either an odd or an even number used. However, I am not sure how to prove the first part. I think that assigning some kind of invariant to the pieces must be the right way to go, but I am not sure.

Thank you,

Answer 1

My colleague, Ido Segev, pointed out that there is a problem with most of the elegant proofs here - Tetris is not just a problem of tiling a rectangle.

Below is his proof that the conjecture is, in fact, false.

Answer 2

There is in fact a straightforward invariant that works in this circumstance - the 'classic' invariant for tiling problems. Checkerboard-color the grid, and note that all other pieces (the $\color{cyan}{\text{I}}$, $\color{green}{\text{S}}$s, $\color{blue}{\text{J}}$s, and the square) take up an equal number of black and white squares in all orientations; by contrast, the $\color{purple}{\text{T}}$ always takes up three squares of one color and one square of the other. This implies that for any number of rows (each of which have an equal number of squares of each color) to be perfectly filled, an even number of $\color{purple}{\text{T}}$ pieces must be used.

EDIT: As pointed out by Gilad, this approach only solves the 'static' issue of tiling a rectangle with tetrominoes including the $\color{purple}{\text{T}}$, not the 'dynamic' region-filling that Tetris provides for; see his excellent solution for why this matters if intermediate rows can be cleared and partial-pieces left behind.

Answer 3

Does the usual checkerboard coloring resolve this? The $\color{purple}{\text{T}}$-shape covers $3$ squares of one color and one of the opposite. All the other shapes cover $2+2$.

Edit: Well, the same problem as with Steven's solution.

Answer 4

Edited to add: The following is only correct if you build up your four lines from 0 (or if you only eliminate four rows at once) which is the way to get maximal points in Tetris. For a counterexample in the general case of clearing the screen in any way you like, see (and vote for) the answer by Gilad Naor

My original answer:

Color the squares black and white in a chessboard fashion and regard the parity of black squares. This is your invariant.

(The $10\times 4$ rectangle has an even number of black squares, each $\color{purple}{\text{T}}$-piece has $3$ or $1$ black squares and all other pieces clearly have $2$ black squares, so not only do you have an even number of $\color{purple}{\text{T}}$s, you have the same number of predominantly black $\color{purple}{\text{T}}$s and predominantly white $\color{purple}{\text{T}}$s.)

There is a similar further relation for the combined number of $\color{orange}{\text{L}}$s and $\color{blue}{\text{J}}$s:

The number of $\color{orange}{\text{L}}$s, $\color{blue}{\text{J}}$s and $\color{purple}{\text{T}}$s with a horizontal line of three squares is even.

Instead of the checkboard colouring, you just look at the alternate coloring of whole rows and see that these pieces are exactly the ones that contribute an odd number of black squares.

Answer 5

It's been noted in the comments that modern Tetris uses 7-bag piece generation, per the Tetris Guideline. However, this restriction doesn't render the conjecture true, specifically because the line clears alter the assigned parity of the squares, which Gilad used in their solution.

One easy counterexample is Perfect Clear Opening, a standard opening in modern competitive Tetris. As the name suggests, it has a high but not 100% chance of allowing a PC. You can see the solutions to it here. (The 6-piece setup is a generalisation of the 7-piece setup; in both, the first T has already been dropped.) While most solutions do include a T, note the existence of solutions when the next pieces are, for example, (I)IOJ.

Unsurprisingly, Tetris players have thought about restrictions including exactly this one. :) There is discussion of parity and the T-piece on the same page, and parity also has its own page on the wiki, which you may be interested in.