8
$\begingroup$

We all know the classic puzzle of trying to tile a mutilated chessboard with $2\times1$ dominoes. Let's imagine that, instead of dominoes, we have $n^2$ L-shaped tetrominoes and we want to tile a $2n\times2n$ chessboard using them (in any orientation, i.e. we're allowed to turn and flip tetrominoes if required). For which values of $n$ is this possible?


I got the idea for this from a question in the Danish Mathematical Olympiad.

$\endgroup$
  • 3
    $\begingroup$ Well, this question has a checkered past... $\endgroup$ – Rubio Feb 10 '18 at 1:04
  • $\begingroup$ @Rubio no option to downvote comments :P $\endgroup$ – Quintec Feb 10 '18 at 1:11
12
$\begingroup$

First of all, notice that

we can put two L-tetrominoes together to make a 4x2 block, and that such blocks will do the job whenever $n$ is even.

Next,

suppose $n$ is odd; then we have an odd number of tetrominoes. Now, colour the rows of our chessboard alternately red and blue; however you place an L-tetromino it will cover either 1 or 3 red squares; therefore the number of red squares covered has the same parity as the number of tetrominoes and is therefore odd. But in fact there are $2n^2$ red squares, an even number. So the covering can't be done for odd $n$.

In conclusion, the covering is possible if and only if

$n$ is even.

$\endgroup$
  • $\begingroup$ Note: I changed the argument in my second spoiler block a bit a while after posting. I think the change is a small but definite improvement, but of course opinions may vary. $\endgroup$ – Gareth McCaughan Feb 10 '18 at 2:08
1
$\begingroup$

The total area will be $4n^2$, so the board is a $2nx2n$ one. If $2n$ is divisible by 4 ($n$ being even), it can be completed by building 4x2 rectangles to combine into such a board with 2 tetrominoes each.

Otherwise...

If $n$ is odd, an odd number of tetrominoes will be used. Paint the square this way:

....................
4...1...2...3...
3...4...1...2...
2...3...4...1...
1...2...3...4...

The different rotations and flips of the tetromino can be written like this:

image

In the shapes in the lower half of the picture, some numbers are repeated, but all the numbers must be distributed equally throughout the square. For every given $a$, there are two kinds of those shapes.

$m_1 = p_{-3} + p_{3}$
$m_2 = r_{-3} + r_{3}$
$m_3 = s_{-3} + s_{3}$
$m_4 = t_{-3} + t_{3}$

$p_{-3}+ p_{3} + 2r_{-3} + s_{-3} + s_{3} + 2t_{3} = s_{-3}+ s_{3} + 2t_{-3} + p_{-3} + p_{3} + 2r_{3}$
$2r_{-3} + 2t_{3} = 2r_{3} + 2t_{-3}$
$r_{-3} + t_{3} = r_{3} + t_{-3} => m_2 + m_4$ is even (by the same token, so is $m_1 + m_3$).

If the latter-half tetrominoes are used an even number of times, the number of the rest must be odd, but the opposite can be said when we flip the square vertically, creating a contradiction.

In short:

The square can be made if and only if $n$ is even.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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