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?
Best Answer
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
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.