# Tiling a diamond-shaped grid with tetrominoes

You have a grid like this: (The entire grid isn't shown as it would be too large, but the number of squares in each row are as follows: $2, 4, 6, \ldots, 96, 98, 100, 100, 98, 96, \ldots, 6, 4, 2$.)

We define this grid as $G(100)$, as it is 100 squares across at its widest point and 100 squares high at its tallest point.

You want to tile it with only copies of this tetromino: You may rotate or flip the tetromino.

1. Is it possible? Why or why not? An explanation in your answer is required.

2. For which even positive integer values of $n$ is tiling the grid $G(n)$ with only the tetromino possible? (Again, you must provide an explanation.)

note: I will post my own solution after either two days have passed or two distinct correct answers (for each question 1 and 2) have been provided.

• Sanity check: $G(100)$ has $4\cdot \binom{50+1}{2}=5100$ squares? – Mike Earnest Apr 25 '15 at 21:28
• @MikeEarnest Correct. (Alternatively, $4 \cdot \sum_{n=1}^{50}n = 5100$.) – Doorknob Apr 25 '15 at 21:34
• In general $G(N)$ has $2⋅N⋅(N+1)$ squares – Ivo Beckers Apr 25 '15 at 22:15
• @IvoBeckers Don't think that's right; it should be $N \cdot (\frac{n}{2}+1)$ (note that there are $5100$ squares for $N = 100$), or equivalently $\frac{N^2+2N}{2}$. – Doorknob Apr 25 '15 at 22:19
• you're right. I was thinking of half the value of $N$ – Ivo Beckers Apr 25 '15 at 22:20

$G(100)$ cannot be tiled.

Divide an infinite checkerboard into $2\times 2$ blocks, then color each block alternately white and black, as shown: $$\begin{array}{ccccc|ccccc} &&\vdots&&\vdots&&\vdots&&\vdots&&\\ \cdots & B & B & W & W & B & B & W & W &\cdots\\ \cdots & B & B & W & W & B & B & W & W &\cdots\\ \hline \cdots & W & W & B & B & W & W & B & B &\cdots\\ \cdots & W & W & B & B & W & W & B & B &\cdots\\ &&\vdots&&\vdots&&\vdots&&\vdots&\\ \end{array}$$ Then, place the $G(100)$ array on top of this so that its axes of symmetry are the two lines (one horizontal, the other vertical) above, and let $G(100)$ be colored to match the the board below it.

No matter how a tile is placed, it will cover either 3 whites and a black, or 3 blacks and a white. This means that whenever an odd number of tiles are placed, the area they cover will be unbalanced between black and white. But covering $G(100)$ entails placing $1275$ tiles, and $G(100)$ itself is white/black balanced, so it cannot be covered. This proof also shows that $G(2n)$ is not tileable whenever $n\equiv 1$ or $2$ (mod $4$), since there are $1+2+\dots+n$ tiles to be placed, which is odd whenever $n=4k+1$ or $4k+2$.

We cannot tile the given grid.

Below is an example coloring of $G(12)$. Notice that a rotation of 180° about the central green dot swaps the colors, thus we have an equal amount of red and white tiles, and we can extend this coloring to any $G(2n)$, in particular, $G(100)$. Let's consider the S and Z tetrominoes separately. Notice that no matter where an S tetromino is placed, it covers either 4-0, 0-4, or 2-2 of white-red. Thus when we place an S tetromino we do not change the difference between the amounts of red and white tiles modulo 4. Similarly any Z tetromino covers 3-1 or 1-3, thus adding 2 to the difference modulo 4. To end with 0 red and 0 white tiles (ie to cover the entire board) we must have the difference be 0 mod 4, and thus we must have an even number of Z tetrominoes.

This argument is completely symmetrical; there is no real difference between S and Z tetrominoes. If we can tile the board using an odd number of S tetrominoes, simply mirror the board turning all S into Z and vice versa and we have tiled the board using an odd number of Z tetrominoes, which we know is impossible. Thus we have an even number of both S and Z tetrominoes, and an even number of tetrominoes overall. This means that the area of the board must be divisible by 8. But in the case of $G(100)$, it's not.

The size of $G(2N)$ is $4(1 + \dots + N) = 4\frac{N(N+1)}{2} = 2N(N+1)$. If 8 divides this then $8 | 2N(N+1) \iff 4|N(N+1) \iff 4|N$ or $4|N+1$.

• Cool argument! We used different colorings, yet proved that the tiling is impossible for the same values of $n$. I've checked $G(2\cdot 3)$ is not tileable, I guess the next step is to check $G(2\cdot 4)$. – Mike Earnest Apr 26 '15 at 0:06
• @MIkeEarnest, Just case checked. $G(8)$ is impossible as well. – Ben Frankel Apr 26 '15 at 0:17