Tiling $m \times n$ board by $a \times b$ tiles implies at least one of $m$ and $n$ is divisible by $a$

Question

Let $a, b, m, n$ be positive integers. Suppose that an $m \times n $ checkerboard can be tiled with $a \times b$ boards (in any orientation), i.e., the $a \times b$ boards can be placed on the $m \times n$ board to cover it completely, with no overlapping of the interiors of the $a \times b$ boards. Show in fact that at least one of $m$ and $n$ is divisible by $a$. (Thus by symmetry, at least one of $m$ and $n$ is divisible by $b$.) For instance, a $6 \times 30$ board cannot be tiled with $4 \times 3$ boards.

Below was my following attempt at a solution:

We will prove by strong induction on $m$ and $n$ that if neither of $m, n$ was a multiple of $a$ then no such tiling exists. Our base case is $m, n < a$. It is obvious in this situation that no tiling exists. We shall show the following lemma:

Lemma: Given any tiling, there is a vertical line or a horizontal line that cuts through the board without cutting any of the tiles.

With this lemma, we can cut the board into 2 smaller boards which share a side. By induction hypothesis, for each of these boards, at least one of the sides is a multiple of $a$. If it's the side that they share, then we are done since the side they share must be of length $m$ or $n$. Otherwise it will be the other side and the original side will be the sum of these two. Adding 2 multiples of $a$ will still give a multiple of $a$ as desired.

Proof of lemma:

There are $m - 1$ horizontal and $n - 1$ vertical lines that go through the board. If there was no such line going through the board that didn't cut any of the tiles, then each line must be obstructed by at least $1$ $a \times b$ board. A tile can obstruct at most a+b-2 lines so that we have at least $\frac{(m-1)(n-1)}{a+b-2}$ tiles. There are exactly $\frac{mn}{ab}$ tiles. Now we shall show that $\frac{(m-1)(n-1)}{a+b-2}> \frac{mn}{ab}$ to obtain a contradiction...

Any tips would be greatly appreciated!

Answer 1

In the tile at $i$-th row and $j$-th column of the $m \times n$ board (where $m$ is the number of rows), we write the number $(j - i) \mod a$.

Any $a\times b$ board, in any orientation, covers an equal number (i.e. $b$) of $0, 1, \dots, a - 1$.

It is then a simple exercise to show that, if none of $m, n$ is divisible by $a$, then some numbers occur more than others in the $m \times n$ board.

Hint: it suffices to consider the case $0 < m \leq n < a$. In that case, pair every tile numbered $(a - 1)$ with the tile above it, which is numbered $0$.

Answer 2

Let be $\mathcal{T}$ the set of tilings $a\times b$ or $b\times a$ of the $[0,m]\times [0,n]$. Let consider the function $\cos\left(\frac{\pi x}{a}\right)\cos\left(\frac{\pi y}{a}\right)$, we have: $$\iint_{[0,m]\times [0,n]}\cos\left(\frac{\pi x}{a}\right)\cos\left(\frac{\pi y}{a}\right)\,dxdy = \frac{a^2}{\pi^2}\sin\left(\frac{m\pi}{a}\right)\sin\left(\frac{n\pi}{a}\right)$$ but also $$\iint_{[0,m]\times [0,n]}\cos\left(\frac{\pi x}{a}\right)\cos\left(\frac{\pi y}{a}\right)\,dxdy = \sum_{T\in\mathcal{T}}\iint_{T}\cos\left(\frac{\pi x}{a}\right)\cos\left(\frac{\pi y}{a}\right)\,dxdy = 0$$ so $a\mid n$ or $a\mid m$

by changing $a$ to $b$ in the function we deduce $b\mid m$ or $b\mid n$