Is it possible to fully tile an 8 by 8 square grid using only Z-tetrominoes? (I don't know the answer...)
$\begingroup$
$\endgroup$
0
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
7
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.
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.
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'.
-
$\begingroup$ The question specifies $8 \times 8$, not $4 \times 4$. $\endgroup$– RobPrattCommented 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$ Commented 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$– RobPrattCommented Mar 10, 2023 at 1:10
-
3$\begingroup$ @RobPratt see edit, pretty sure the answer doesn't change. $\endgroup$ Commented Mar 10, 2023 at 1:22
-
3
$\begingroup$
$\endgroup$
2
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$).
-
4$\begingroup$ Cool graph. How did you discover it? Does it generalize? $\endgroup$ Commented 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$– RobPrattCommented Mar 10, 2023 at 4:21
$\begingroup$
$\endgroup$
1
Answer:
If the chessboard edges loop into each other (like a torus):
.
answered Mar 10, 2023 at 17:22
-
2$\begingroup$ One could argue that “square” implies boundaries, but I’m a fan of the lateral thinking here. $\endgroup$– SneftelCommented Mar 11, 2023 at 11:37