One possible approach is generalizing the concept of coloring by using complex numbers (Yufei called them weights). Since often these "board" problems require coloring twice for each orientation, you might want some way to encode both configurations together.

First thing that came to mind was quaternions, but noncommutativity would probably make things fail. This problem of encoding two things at the same time is actually pretty interesting; going to keep working on that.

I was thinking the same thing about complex numbers. If you say is the root of unity and then assign the square in the row and column with the weight of , then when you sum all the weights and factor you get , but since the sum of all the weights covered by a single block is 0, the quantity is the same as the weight of the uncovered block.

You can probably get a lot with this. If the uncovered block is then



EDIT - it clearly is possible with even though, so something I did is completely wrong.
EDIT AGAIN - oh I confused two variables. fixed.

There's a more general way to assign weights: one assigns position the weight where are both relatively prime to . It becomes necessary to do this in the case (where there are only two different useful colorings). In the case, I used a slightly more general coloring (starting from a permutation matrix satisfying certain constraints) that I can't motivate by any nice patterns like .

Also: this is somewhat obvious from the complex number computation, but this problem is easier (say, in the two cases I gave) when either or . If neither is the case, I believe it is necessary to split up into the factors dividing and the factors dividing .

Also also: the big problem with coloring proofs in general is that they only give necessary conditions. Sufficient conditions are difficult; for example, has two obvious colorings which, put together, give you four extra squares that do not in fact satisfy the problem constraints (which is why I needed to use the slightly more general coloring). It might be possible to circumvent this difficulty by summing over all possible colorings in the appropriate way.

Hm, really? Because it seems to me that by my equation



we need to have absolute value of . But couldn't this only happen when or ?

I mean if such that (and for simplicity is odd) it might be necessary to superimpose -colorings and -colorings rather than consider -colorings.

Right, but didn't I just show that if any tiling is possible then we will always have or ? Perhaps I made a mistake...

Oh. Hmm. It looks like you're right. That enforces some very strong necessary conditions, but again the sufficient conditions are more elusive.

Okay then, onto the actual cases.

Case: .

Remember $ z=e^{\frac{2\pi i}{k}$, or .

So basically .

So . (Remember above, we said was the weight on the square that is not covered). Now, again, we labeled the square in the row and column with (rows and columns indexed starting with 0). Hence where and are the coordinates of the uncovered square. Looking from a different orientation (i.e., reflected) we get , or simply .

If is odd, we see that we must then have . It is easy to see that this is sufficient as well, it is very simple to come up with a valid tiling. (I'll try to describe it: just make tiles straight out from the uncovered block to the walls, then each side of this "wall" divides into two smaller grids, each with height divisible by , so these portions can be easily tiled.)

On the other hand if is even, we could also have . I haven't thought about this one much, but I will post more if I come to anything.