Formulas for predicting when it's possible to tile defective squares

It's rather difficult to give exact rules (and prove they're right) for when it's impossible to tile a defective square without knowing the answer to begin with. Instead it's much easier to come up with (and prove) a rule that shows that certain squares are impossible to tile, but not necessarily show that all the other ones can be tiled.

One such rule is actually pretty simple. If you're going to tile a defective square with trominos, that means that you're going to cover all the unit squares with the trominos except one. This gives the rule that n² = 3k +1 or that

$$n^2 -1 \mbox{ mod }3 = 0$$ (1)

where n is the length of a side of the defective square that you're going to tile, and k is the number of trominos. Obviously you can't tile a defective square that's 6x6 because it has area 35 (since it's defective there's one square that won't be covered) and 35 isn't divisible by 3. And since $6^2 -1 \mbox{ mod }3 = 2$ our formula says it's impossible to tile the defective square of 6 on a side.

This equation can be simplified slightly

$$n^2 -1 \mbox{ mod }3 = 0$$ (2)

$$(n+1)(n -1) \mbox{ mod }3 = 0$$ (3)

Note that this doesn't prove that if $n^2 -1 \mbox{ mod }3 = 0$ then you can tile it, just that if $n^2 -1 \mbox{ mod }3 \neq 0$ then you definetly can't. In other words we've only proven, formula 1 is a necessary condition, but we haven't shown it's a sufficient condition.

To show it's a sufficient condition (and prove that we've found the exact rule), it's possible to tackle the problem from the other direction: i.e. prove that whenever formula 1 holds that it's possible to tile the system.

To do this, I'm going to show how to extend a smaller solution into a more complex solution, and thus give an algorithm for tiling a defective square of size n whenever $n^2 -1 \mbox{ mod }3 = 0$. Specifically I'm going to show how to extend the tiling of a defective square of size n with the hole in the corner to a tiling of a defective square of size n+3 with a hole in the corner.

First, notice that it's easy to tile a 2x3 square so that there are no spaces left open:

+--+--+
|     |
|  +--+
|  |  |
+--+  |
|     |
+-----+

This is important because I'm going to extend the smaller squares by adding a border that's three wide around the edges of the existing defective square in such a way that the hole remains in the corner. There are two cases: