Harvard-MIT Mathematics Tournament

Solution:

We prove the following lemma.

Lemma. Let $k$ be a positive integer such that $k \mid a$ and $k \mid b$. Then an $m \times n$ rectangle is $(a, b)$-tileable if and only if an $m' \times n'$ rectangle is $\left(\frac{a}{k}, \frac{b}{k}\right)$-tileable for $\left\lfloor\frac{m}{k}\right\rfloor \leq m' \leq \left\lceil\frac{m}{k}\right\rceil$ and $\left\lfloor\frac{n}{k}\right\rfloor \leq n' \leq \left\lceil\frac{n}{k}\right\rceil$. (Here, $\lfloor x\rfloor$ denotes the greatest integer less than or equal to $x$, while $\lceil x\rceil$ denotes the least integer greater than or equal to $x$.)

Proof. Number the rows and columns in order. For each pair $0 \leq i, j < k$, consider the set of squares in a row congruent to $i$ modulo $k$ and in a column congruent to $j$ modulo $k$. If one square of a type $(a, b)$ domino lies in this set, then so does the other. We can therefore partition the rectangle into these sets and then tile these sets instead. Each such set is a rectangular array of dimensions $m' \times n'$, with $\left\lfloor\frac{m}{k}\right\rfloor \leq m' \leq \left\lceil\frac{m}{k}\right\rceil$ and $\left\lfloor\frac{n}{k}\right\rfloor \leq n' \leq \left\lceil\frac{n}{k}\right\rceil$, and a type $(a, b)$ domino on the original rectangle is a type $\left(\frac{a}{k}, \frac{b}{k}\right)$ domino on this new array. Since all possible pairs $(m', n')$ occur, the result follows.

Suppose $2k \nmid m$ and $2k \nmid n$. Then at least one of $\left\lfloor\frac{m}{k}\right\rfloor$ and $\left\lceil\frac{m}{k}\right\rceil$ is odd, so we can choose $m'$ odd. Likewise we can choose $n'$ odd. But then an $m' \times n'$ rectangle has odd area and so cannot be tileable, implying that the $m \times n$ rectangle is not tileable.