Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am a big fan of the oldschool games and I once noticed that there is a sort 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,

share|improve this question
7  
That's an interesting question! I don't see any special reason for this, though. –  FUZxxl Nov 8 '11 at 16:58

4 Answers 4

up vote 128 down vote accepted

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.

Counter proof

share|improve this answer
14  
+1 to Ido Segev –  Graphth Nov 10 '11 at 17:09
    
It seems, in light of this counterexample (+1 btw), that the conjecture could be refined to improve the notion of "number of pieces" involved in a perfect clear, where the involvement of partial pieces was made more explicit. Although I wonder if allowing partial pieces makes for too many degenerate cases, destroying the hopes for any meaningful conjecture about partial piece perfect clears. –  Greg L Nov 10 '11 at 18:43
4  
@Graphth Would someone explain the picture Gilad has shown and how this answers Eric's question? –  user17762 Dec 14 '11 at 0:32
5  
@SivaramAmbikasaran The question is, can we have an odd number of T pieces at the time that everything is cleared. The pictures show that if you start with 5 Ts and then 5 Ls, and play them just right, you will have a perfect clear. So, this answers the question, yes, it is possible to have an odd number of Ts before a perfect clear. –  Graphth Dec 14 '11 at 1:08
    
@Graphth: Thanks. I got it. –  user17762 Dec 14 '11 at 1:20

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.

share|improve this answer
2  
Switching to CW. Gone too far IMHO. –  Jyrki Lahtonen Nov 10 '11 at 7:15
    
I'm a little boggled by the volume of response to this question, I have to admit - AFAICT it wasn't getting published anywhere else, so I'm really not sure why it's generating so many votes... –  Steven Stadnicki Nov 10 '11 at 8:51
    
Congrats on the century mark @StevenStadnicki ! Probably I am worrying about it too much. You were the first to hit the send button, so you have to stand up and face the music :-) –  Jyrki Lahtonen Nov 10 '11 at 9:13
3  
Too bad I CWified this before we all learned about the "misinterpretation" bit. Now what? How to rake in the downvotes? –  Jyrki Lahtonen Nov 11 '11 at 4:12

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.

share|improve this answer
    
Can you elaborate on the combined number of Ls and Js? –  LarsH Nov 8 '11 at 17:38
    
@Phira: I think something similar to Gilad Naor's solution will also disprove your second fact regarding $L$, $J$ and $T$. –  Eric Naslund Nov 10 '11 at 17:49
    
@EricNaslund That is not how I interpreted the question. –  Phira Nov 10 '11 at 17:53
    
@Phira: Ok, that is fair, there are several interpretations. Since there are disagreeing answers, it might a good idea to mention this very briefly. –  Eric Naslund Nov 10 '11 at 18:06
    
@EricNaslund You are right, I have added an intro that points to the other answer. –  Phira Nov 10 '11 at 18:12

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.

share|improve this answer
11  
But life is never as simple as it seems. The conjecture is in fact false. See math.stackexchange.com/questions/80246/…. –  Gilad Naor Nov 10 '11 at 10:48
1  
This is true only if the perfect clearis the first clear in the game. –  Benoit Nov 10 '11 at 12:42
8  
Since this answer is not correct, it should start receiving downvotes to indicate this. Allow me to start. As is, it is probably one of the top 10 most upvoted answers in the history of this site and it's wrong. –  Graphth Nov 10 '11 at 17:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.