3
$\begingroup$

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!

$\endgroup$
5
  • 1
    $\begingroup$ +1 Interesting problem, nicely presented, good work shown, interesting approach, which I am clueless on. Question: At the start of your proposed proof to the lemma, you say "There are (m-1) and (n-1) vertical lines." Do you intend that "either there are (m-1) vertical lines and (n-1) horizontal lines, or vice-versa"? $\endgroup$ – user2661923 Oct 5 '20 at 17:49
  • $\begingroup$ Good catch. I've made some edits to make my approach more clear. $\endgroup$ – Math_Day Oct 5 '20 at 18:19
  • 1
    $\begingroup$ Can't a $3\times 3$ tile obstruct two horizontal and two vertical lines (for example) $\endgroup$ – Mark Bennet Oct 5 '20 at 18:23
  • $\begingroup$ Where do you get the lemma from, was this given has a hint? I'm wondering if this approach is working at all. Then you correctly count the horizonal and vertical potential cut lines, but why do you multiply them? You have exactly $m+n-2$ potential cut lines, each $a\times b$ block "blocks" exactly $a+b-2$ of them ($a-1$ in one direction and $b-1$ in the other). Showing $\frac{m+n-2}{a+b-2} > \frac{mn}{ab}$ would be necessary, which is incorrect for example for $m=4, n=9, a=6, b=1$. So I don't think the lemma can be proved this way (if it is even correct). $\endgroup$ – Ingix Oct 5 '20 at 19:57
  • $\begingroup$ The lemma wasn't a hint and so could be wrong $\endgroup$ – Math_Day Oct 5 '20 at 20:21
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks for the hint! $\endgroup$ – Math_Day Oct 5 '20 at 20:24
2
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ Brilliant solution! $\endgroup$ – Math_Day Oct 5 '20 at 20:25
  • $\begingroup$ @Will sorry the functions must be $\cos(\pi x / a)\cos(\pi y /a) $ and $\cos(\pi x / b)\cos(\pi y /b) $ $\endgroup$ – ne3886 Oct 6 '20 at 5:41
  • $\begingroup$ Thanks for making the edits! $\endgroup$ – Math_Day Oct 6 '20 at 21:18

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.