5
$\begingroup$

Is it possible to fully tile an 8 by 8 square grid using only Z-tetrominoes? (I don't know the answer...)

$\endgroup$
0

3 Answers 3

19
$\begingroup$

If reflections are not allowed:

It's impossible.

The figures below show why.

Concentrate on one of the corners of the square. There are two orientations of the z tetromino (assuming no reflection), and only one of these orientations can fill the corner, shown below.

z tetrominos on the corner

Now note that in the valid configuration, the square marked 'A' is impossible to fill. Therefore, the 8x8 grid can't be tiled.

If reflections are allowed:

It is still impossible.

See figure below showing the top three rows of the 8x8 square.

top row argument

The red tetromino is placed without loss of generality (from the argument above, rotations/reflections won't help). The only way to cover the cell marked 'B' is with the yellow tetromino, and similarly for the orange tetromino over 'C'. It is then impossible to fill cell 'D'.

$\endgroup$
7
  • $\begingroup$ The question specifies $8 \times 8$, not $4 \times 4$. $\endgroup$
    – RobPratt
    Mar 10, 2023 at 0:59
  • 3
    $\begingroup$ @RobPratt yes, but the same argument is going to hold if the grid is expanded downward and leftward. $\endgroup$ Mar 10, 2023 at 1:09
  • $\begingroup$ I agree, but the statement that A cannot be covered is false. Note that I'm assuming that Z can be both rotated and flipped. $\endgroup$
    – RobPratt
    Mar 10, 2023 at 1:10
  • 3
    $\begingroup$ @RobPratt see edit, pretty sure the answer doesn't change. $\endgroup$ Mar 10, 2023 at 1:22
  • 3
    $\begingroup$ Looks better now. $\endgroup$
    – RobPratt
    Mar 10, 2023 at 2:00
17
$\begingroup$

Here's a "coloring" proof of impossibility.

\begin{matrix} 9 &1 &9 &5 &5 &9 &1 &9 \\ 1 &-11 &-3 &-7 &-7 &-3 &-11 &1 \\ 9 &-3 &5 &1 &1 &5 &-3 &9 \\ 5 &-7 &1 &-3 &-3 &1 &-7 &5 \\ 5 &-7 &1 &-3 &-3 &1 &-7 &5 \\ 9 &-3 &5 &1 &1 &5 &-3 &9 \\ 1 &-11 &-3 &-7 &-7 &-3 &-11 &1 \\ 9 &1 &9 &5 &5 &9 &1 &9 \end{matrix}

The sum of the matrix entries is $48$, but each possible placement of a Z-tetromino covers a nonpositive sum ($0$, $-4$, or $-8$).

$\endgroup$
2
  • 4
    $\begingroup$ Cool graph. How did you discover it? Does it generalize? $\endgroup$ Mar 10, 2023 at 3:47
  • 3
    $\begingroup$ Thanks. It arises from linear programming dual variables, which provide a general approach for certifying infeasibility of linear systems of equalities and inequalities. For another example, see math.stackexchange.com/questions/4354682/… $\endgroup$
    – RobPratt
    Mar 10, 2023 at 4:21
5
$\begingroup$

Answer:

If the chessboard edges loop into each other (like a torus): you can.

$\endgroup$
1
  • 2
    $\begingroup$ One could argue that “square” implies boundaries, but I’m a fan of the lateral thinking here. $\endgroup$
    – Sneftel
    Mar 11, 2023 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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