Tiling problem: 100 by 100 grid and 1 by 8 pieces

Solution 1:

(from the Comments)

David A. Klarner's paper (1969), Packing a Rectangle with Congruent N-ominoes, surveys a number of problem areas for tiling rectangles with congruent polyominoes. He writes, in part:

There are a few theorems which characterize the rectangles that can be packed with a particular $n$-omino $X$; the simplest case is when $X$ is itself a rectangle and here the problem is completely solved.

THEOREM 5. An $a \times b$ rectangle $R$ can be packed with a $1 \times n$ rectangle if and only if $n$ divides $a$ or $b$.

PROOF: If $n$ divides $a$ or $b$ an $a \times b$ rectangle can be cut into $1 \times n$ rectangles in an obvious way.

Suppose an $a \times b$ rectangle has been packed with a $1 \times n$ rectangle and that $a = qn+r$, $0 \lt r \lt n$; also, number the columns of cells perpendicular to the side of length $a$, $1, 2,\ldots, a$, from left to right. Let $f_1,f_2, \ldots, f_n$ denote distinct colors and color the $c$-th column $f_i$ if $c \equiv i \pmod{n}$. Let $c_i$ denote the number of cells in the rectangle colored $f_i$, then $c_i = qb + b$, $1 \le i \le r$, and $c_i = qb$, $r + 1 \le i \le n$. Let $x$ denote the number of $1 \times n$ rectangles such that each rectangle has exactly one cell colored $f_i$ ($i = 1, 2,\ldots, n$); also, let $y_i$ denote the number of $1 \times n$ rectangles with every cell colored $f_i$ ($i = 1, 2, \ldots, n$). Now, since $c_i = x + ny_i$, we have $$ c_i = x + ny_i \equiv x + ny_j = c_j \pmod{n}; $$ in particular, $c_1 = qb+b \equiv qb = c_{r+1} \pmod{n}$, so $b \equiv 0 \pmod{n}$.

For the sake of completeness we note the following:

COROLLARY. An $a \times b$ rectangle $R$ can be packed with $c \times d$ rectangles if and only if $c$ divides $a$ or $b$, $d$ divides $a$ or $b$, and if $cd$ divides one side of $R$ then the other side can be expressed in the form $cx + dy$ with $x, y \ge 0$.

whose short proof is given in the above paper (free PDF download).

Solution 2:

Here is another neat proof of Klarner's theorem, which I extracted from the proof of Proposition 2.10 of Michael Reid's paper Tile homotopy groups.

Consider a rectangle $R$ which occupies cells $a_{i,j}$ where $0\leq i\leq a-1$ and $0\leq j\leq b-1$ in the infinite square grid. Suppose $R$ is tiled by tiles of the form $1\times n$ or $n\times 1$. Now color the cells $a_{i,j}$ where $i\equiv -1\text{ or }0 \bmod n$ and $j\equiv -1 \text{ or } 0\bmod n$ black. Notice that every tile will meet an even number of black cells! The number of cells in $R$ can be calculated modulo $2$ as follows. Subdivide $R$ into pieces gotten by taking the $n\times n$ fundamental domain near the origin and tiling the plane with it. (Some of these translates will only meet $R$ in strict subsets.) If they are entirely contained in $R$, they each have 4 black corners, and so contribute an even number of dark squares. They may also have one side of dimension $n$ and the other strictly less. These regions will contain 2 black squares. Finally, the region in the corner furthest from the origin may contain two sides of length less than $n$, contributing $1$ black cell. This would yield a total odd number, which implies that to have a tiling, one of the sides of this corner region must have dimension $n$. This implies that either $a$ or $b$ is divisible by $n$.

I've illustrated this method in the picture below, which represents a 100 by 100 square with some grid cells colored black via the prescription above. The big dark squares are actually clusters of four. Visually, it is quite clear that there are an odd number of dark squares. They come in clusters of 4 or 2, except the one in the lower left. I've also included a few possible tile positions to convince you that they will always hit an even number of dark squares. The possibilities are that they can hit no dark squares, they can hit two squares right next to each other, or they can hit two squares of distance 8 apart on two separate clumps. So a tiling by 1x8 tiles of the 100x100 grid would yield an even number of squares covered by all tiles, contradicting the fact that there are an odd number total.