8
$\begingroup$

You have a grid like this:

grid

(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:

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.

$\endgroup$
  • $\begingroup$ Sanity check: $G(100)$ has $4\cdot \binom{50+1}{2}=5100$ squares? $\endgroup$ – Mike Earnest Apr 25 '15 at 21:28
  • $\begingroup$ @MikeEarnest Correct. (Alternatively, $4 \cdot \sum_{n=1}^{50}n = 5100$.) $\endgroup$ – Doorknob Apr 25 '15 at 21:34
  • $\begingroup$ In general $G(N)$ has $2⋅N⋅(N+1)$ squares $\endgroup$ – Ivo Beckers Apr 25 '15 at 22:15
  • $\begingroup$ @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}$. $\endgroup$ – Doorknob Apr 25 '15 at 22:19
  • $\begingroup$ you're right. I was thinking of half the value of $N$ $\endgroup$ – Ivo Beckers Apr 25 '15 at 22:20
13
$\begingroup$

Answer to part 1:

$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$.

$\endgroup$
7
$\begingroup$

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)$.

enter image description here

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$.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Mike Earnest Apr 26 '15 at 0:06
  • $\begingroup$ @MIkeEarnest, Just case checked. $G(8)$ is impossible as well. $\endgroup$ – Ben Frankel Apr 26 '15 at 0:17

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.