12
$\begingroup$

Is it possible to tile a $10\times10$ chessboard with (non-overlapping) T-tetrominos?

If so, how? If not, prove it's impossible.

Bonus: Which Tetris pieces can used to tile a 10$\times$10 board, allowing reflections?

It is certainly posssible to tile a regular $8\times 8$ chessboard. Below is a failed attempt to extend that tiling to a $10\times 10$ board, which misses some squares in the upper left and lower right. The colors don't matter, they're just there to make the picture more clear.

$\qquad\qquad\qquad\qquad$enter image description here

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
24
$\begingroup$

It is not possible. The area of a $10 \times 10$ checkerboard is $100$, so it takes $25$ T pieces to have the same area. The checkerboard has the same number of red and black squares, but each piece covers three of one color and one of the other. $25$ pieces cannot cover $50$ squares of each color, the most even they can get is $51-49$

Improve this answer
$\endgroup$
2
  • $\begingroup$ very well said :) $\endgroup$
    – Mike Earnest
    Commented Mar 26, 2015 at 22:32
  • $\begingroup$ Wow, I was expecting this to be more complex xD $\endgroup$
    – David Mulder
    Commented Mar 27, 2015 at 1:03
14
$\begingroup$

For additional reference, here are tilings of the other tetrominos or proofs that it's impossible.

1. 2x2 blocks (O pieces)

This one is easy — a 5x5 arrangement of 2x2 blocks tiles a 10x10 checkerboard perfectly.

2. L-shaped blocks (L pieces)

Suppose the checkerboard is painted alternating white and black by columns rather than squares. Then each L piece occupies either 3 white squares and one black square, or three black squares and one white square, regardless of its rotation state:

x . .    . . .    x o .    . . .
x . .    . . x    . o .    x o x
x o .    x o x    . o .    x . .

By the same argument as the T-pieces when the checkerboard was painted in a checker pattern, you can't have 25 of the these pieces on the board, because you could only get a 51/49 split.

3. 4x1 blocks (I pieces)

The area of a 10x10 checkerboard can be divided into four colours of diagonal stripes, starting from the top left and working your way down to the bottom-right:

x o + . x o + . x o
o + . x o + . x o +
+ . x o + . x o + .
. x o + . x o + . x    1. x
x o + . x o + . x o    2. o
o + . x o + . x o +    3. +
+ . x o + . x o + .    4. .
. x o + . x o + . x
x o + . x o + . x o
o + . x o + . x o +

These colours have the following numbers of squares:

1. 1 + 5 + 9 + 7 + 3 = 25
2. 2 + 6 + 10 + 6 + 2 = 26
3. 3 + 7 + 9 + 5 + 1 = 25
4. 4 + 8 + 8 + 4 = 24

But notice that any 4x1 block in the checkerboard must contain exactly one square of each colour, so 25 of them would occupy 25 of each. This is impossible, so the board cannot be tiled with 4x1 blocks.

4. Squiggly blocks (S pieces)

This one is a case analysis. Consider the S piece that covers the bottom-left square of the checkerboard. It must be in one of these two configurations:

. . . .     . . . .
. x . .     . . . .
x x . .     . x x .
x . . .     x x . .

Since these configurations are symmetric across the main diagonal, they're equivalent. So, consider the latter case. Then, the only place an S piece could go to cover the crevice in the third square on the bottom is in the exact same orientation:

. . . . . .
. . . . . .
. x x o o .
x x o o . .

And the only place that another S piece could go to cover that crevice is to the right of that, et cetera, until they stick out of the board.

You can actually use this to prove that the S piece can't tile any rectangular checkerboard perfectly. Moral of the story: S pieces suck.

But! An interesting property of this proof is that it doesn't apply to toroidal checkerboards. All of the other invariants continue to apply even when the board wraps around on itself, but the S piece can indeed tile the grid perfectly in this case.

So it turns out that out of all the tetrominos, only the square can tile a 10x10 grid perfectly.

Improve this answer
$\endgroup$
5
  • $\begingroup$ And what about L pieces? That case is a very fun problem as well! $\endgroup$
    – Mike Earnest
    Commented Mar 26, 2015 at 23:19
  • $\begingroup$ Got it. A little Googling brought up research papers on the subject (but not a direct solution to the problem), and I simply applied the same invariant. $\endgroup$
    – user88
    Commented Mar 26, 2015 at 23:20
  • 1
    $\begingroup$ I like the observation about toruses! A fellow grad student pointed out that the T tiling is possible when the board is a Möbius strip; in fact the incomplete tiling I showed can be completed provided the right side wraps around to the left with a twist $\endgroup$
    – Mike Earnest
    Commented Mar 26, 2015 at 23:38
  • 1
    $\begingroup$ I didn't notice the Möbius strip until you said it, but that does work. I'd imagine it works simply because it violates the invariant condition by allowing black squares to become white squares and vice versa. $\endgroup$
    – user88
    Commented Mar 26, 2015 at 23:54
  • $\begingroup$ You can also do the 4x1 tiling on a Möbius strip, since you essentially have five strips of 20 squares each. $\endgroup$
    – user88
    Commented Mar 27, 2015 at 1:21
1
$\begingroup$

Think ' coloring ' . If u color the squares black & white like a checkerboard and seeing that the T tetrominos cover an ODD number of either color , there are exactly 50 black and 50 white ..EVEN number of each, so no such tiling exists .

Improve this answer
$\endgroup$

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