Tiling a rectangular checkerboard with one arbitrary square removed

Question

Assume that there's a rectangular board of dimension $ab$, and one square is arbitrarily removed. Assume that $d | (ab -1)$. Does this imply that there exists some tiling of the rectangle -- with the square removed -- using some combination of the various polyominos of size $d$? It feels intuitive that this should be true, as it hits very close to what division "means" (visually), but not obvious as regards proof.

Answer 1

Here is a solution when at least one of $a$ and $b$ is even (and both are $>1$).

In this case, it is possible to draw a closed path through the $a \times b$ rectangle that visits each square once. Deleting a square means we're left with an open path. Just take the squares in order along this path, $d$ at a time, to get a tiling with size-$d$ polyominoes. Here's an illustration when $a=b=8$ and $d=9$:

---

Here is a solution when $a$ and $b$ are both odd, $a,b>1$, and $d \ne 2$.

In this case, we take a closed path that visits each square once and almost always goes from a square to an adjacent square, except in one case where it takes a step from square $(1,1)$ to square $(2,2)$. Such a path always exists (exercise) by generalizing the $7\times 7$ solution below.

If necessary, rotate the board so that the deleted square is not one of the squares $\{(1,1),(1,2),(2,1),(2,2)\}$ in the top left corner. This is possible except when $a=b=3$, but we can solve the $3 \times 3$ case easily :)

Now, once again, the deleted square splits the closed path into an open path, and we try to take squares along that path, $d$ at a time, to be our polyominoes.

Earlier, $d$ consecutive squares of the path would always form a polyomino because any two consecutive squares of the path are adjacent. Here, that's not true in one place, because $(1,1)$ is not adjacent to $(2,2)$. However, when $d\ne 2$, if we are taking $d$ consecutive squares of the path including $(1,1)$ and $(2,2)$, we also take either $(1,2)$ or $(2,1)$, which makes a connected shape again. So we're still fine.

---

As already mentioned in comments, there might not be a solution in the following cases:

• when $a=1$ or $b=1$ (because the deleted square might split the rectangle into two parts, neither of which has area divisible by $d$)
• when $a$ and $b$ are both odd and $d=2$ (because, if we take a checkerboard coloring of the rectangle, the deleted square might leave more white squares than black squares, but a domino always covers one square of each color).

So we've covered all the cases in which a solution is guaranteed to exist.