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?

  • $\begingroup$ We have that $k|mn$ by an area argument, so if $k$ is prime the result is automatic. If $k$ divides neither $m$ nor $n$, then each row and each column must intersect at least one tile of each kind (vertical and horizontal). $\endgroup$ – Fimpellizieri Mar 10 '17 at 3:41
  • $\begingroup$ Good point. My problem is completing a proof showing that fancy things like herringbone patterns etc. will only work if the sides are divisible. $\endgroup$ – victoria Mar 10 '17 at 4:09
  • $\begingroup$ I have seen a paper with something like $40$ proofs of this theorem, but don't know where. It has been cited on this site, but maybe in a comment so it will be hard to find. $\endgroup$ – Ross Millikan Mar 10 '17 at 5:17
  • $\begingroup$ That paper, with fourteen very messy and complicated proofs of a more complicated version of this problem, was referenced as a link to the right of this question. Alas no help for my poor student. $\endgroup$ – victoria Mar 10 '17 at 5:42

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.


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

  • $\begingroup$ Also very cute but very much over the head of my student. Nothing I can give a beginner? $\endgroup$ – victoria Mar 10 '17 at 3:52

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$

  • $\begingroup$ Cute but I fear far over the head of my student. Nothing more basic? $\endgroup$ – victoria Mar 10 '17 at 3:50
  • $\begingroup$ I think that an analogous colouring with $k$ colours might be feasible. $\endgroup$ – tehjh Mar 10 '17 at 4:41
  • $\begingroup$ Interesting. Then we have to insist they are all in a row somehow. $\endgroup$ – victoria Mar 10 '17 at 4:52
  • $\begingroup$ Attempt at an elementary solution. We colour the board in $k$ colours according to the sum of the sum of the coordinates of each square (think of a colouring that goes RGBYRGBY... in the first row, GBYRGBYR... in the second and BYRGB... in the third and so on but with $k$ colours) The problem is to prove that the numbers of tiles of each colour are not all the same. This, however, does not appear to be trivial, and may not in fact be true... $\endgroup$ – tehjh Mar 10 '17 at 5:02
  • $\begingroup$ Not true if k is a composite number, say 6. Take a 20 x 15 board, area = 300 which is divisible by 6. But once you tile it out there will be a remainder area 3 x 2 which will require a cut tile. $\endgroup$ – victoria Mar 10 '17 at 5:39

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.