Tiling a board with domino pieces

Question

Let $m$ and $n$ be natural numbers such that $m\geqslant n>1$ and that the numbers $m$ and $n$ are not both odd. Consider a board with $m$ columns and $n$ rows. Obviously, the board can be tiled with domino pieces (as usual, I am assuming that each domino piece has the size of two squares of the board).

My question is:

For which values of $m$ and $n$ can we tile the board with domino pieces in such a way that, if we split the original board into two rectangular boards, then we must split at least one of those pieces?

Of course, for this to happen, we must have $n>2$. On the other hand, if $m=n=8$, then such a tiling exists:

I remember finding the answer to this question in a text that I read years ago, but I can't remember anymore whether it was an article or part of a textbook.

Answer 1

The necessary and sufficient conditions are

1. $mn$ is divisible by $2$.
2. $m, n \ge 5$
3. $(m,n) \ne (6,6)$.

This is a result by R.L.Graham.

• R.L. Graham Fault-Free Tilings of Rectangles, In The Mathematical Gardner: A Collection in Honor of Martin Gardner (Ed. D. A. Klarner). Belmont, CA: Wadsworth, 120–126, 1981
  (an online copy? can be found here)