Tiling with 1 x k tiles; if you can tile n x m rectangle, k|n or k|m

Question

Tiling with 1 x k tiles;prove that if you can tile n x m rectangle, k|n or k|m (assuming k, n, m integers).

It is obvious that you get down to the remainders of n and m divided by k. Experience and logic say we can shift all the tiles to line up in blocks parallel to one side and if there are non-zero remainders less than k, the tiling fails. But how do I demonstrate that formally and mathematically?

Answer 1

There are other approaches to this problem, but one that I particularly like (which I first learned for another, slightly harder problem) is to consider the double integral of the function $e^{2\pi i(x/k+y/k)}$ and show that the integral is zero over a rectangle (with sides parallel to the axes) if and only if one of the sides is a multiple of $k$. Then, by assumption, the existence of a tiling shows that the integral over the entire rectangle must be zero (by additive of integration over disjoint regions).

Answer 2

This has a well-known method, I believe. Assuming the centres of squares have integer coordinates with the bottom left corner square on $(0,0)$, assign the square with coordinates $(a,b)$ the complex number $e^{\frac{2i\pi(a+b)}{k}}$. The sum of the weights of all the squares is clearly the product of the sum on each of the axes, and since each tile has weight 0, the total weight of the rectangle must be 0 as well, and thus either one of the axes has weight 0 i.e. $k|m$ or $k|n$

Answer 3

I believe I've found a solution that is quite basic and should be approachable by people with an elementary understanding of mathematics. Color each square of the grid with colors $1$ through $k$, as follows. In the image below, $k=7$.

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c} \hline 1&2&3&4&5&6&7&1&2&3&\dots\\\hline 2&3&4&5&6&7&1&2&3&4&\dots\\\hline 3&4&5&6&7&1&2&3&4&5&\dots\\\hline \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\\ \end{array}$$

Then each tile will contain exactly one color of each kind. It follows that

If the grid can be tiled by $k\times 1$ rectangles, then it contains the same number of squares of each color.

---

Let's agree that the grid is $m$ rows by $n$ columns.

If $m$ is divisible by $k$, say $m=ck$, then for each color and each column there will be exactly $c$ squares of that color in that column. Hence, the total number of squares of each color is the same. Something similar holds when $n$ is divisible by $k$.

Now, suppose neither $m$ nor $n$ is divisible by $k$, and write $m=ck+r$ and $n=dk+q$, with $1\leq r,q\leq k-1$. The subgrid $ck\times n$ contains an equal number of squares of each color, by the previous argument. Consider then the bottommost strip, of size $r\times n$.

Once again, the subgrid of size $r\times dk$ contains an equal number of squares of each color. We are finally left with a subgrid of size $r\times q$.

Assume without loss of generality that $r\leq q$. Renumbering if needed, it should look something like this:

$$\begin{array}{|c|c|c|c|} \hline 1&2&\dots&q\\\hline 2&3&\dots&q+1\\\hline \vdots&\vdots&\ddots&\vdots\\\hline r&r+1&\dots&r+q-1\\\hline \end{array}$$

Since $r\leq q$, it's easy to see that color $q$ shows up in exactly $r$ squares -- once on each row (consider the antidiagonal). On the other hand, color $1$ definitely does not show up on the second row, so it can appear at most $r-1$ times.

This shows that, as a whole, the $m\times n$ grid does not contain the same number of squares of each color. Therefore, if $k$ divides neither $m$ nor $n$, the $m\times n$ grid cannot be tiled by $k\times 1$ rectangles.