Question: Consider an $N$ by $N$ checkerboard.
i) For what values of $N$ can the board be tiled by non-overlapping $4$ by $1$ tiles?
ii) For what values of $N$ can the board not be tiled by non-overlapping $4$ by $1$ tiles?
So for i), it is quite easy to see that for any $N$ that is a multiple of $4,$ we can do this tiling – simply fill the first now with $\frac{N}4$ tiles and repeat for the other rows as well.
For ii) Clearly, odd $N$ do not work, as each tile can only cover an even number of squares so the sum of the number of tiles covered will always be even.
The second bit of the proof is where I have trouble. By trying small cases like $2, 6$ and $10,$ I believe that for any N that leaves a remainder of $2$ when divided by $4,$ this tiling is also not possible. However, I am unable to make any advances in trying to prove it.
Any hints or tips will be appreciated.
Best Answer
Let's number the cells of the board as follows
$$1234123412\dots$$ $$2341234123\dots$$ $$3412341234\dots$$ $$4123412341\dots$$ $$1234123412\dots$$ $$\dots$$
Now, each $4\times 1$ tile covers exactly one $1,2,3$ and $4$. So if the board can be tiled by these tiles, it must contain the same number of $1,2,3$ and $4$. Is this true when $N$ leaves a remainder of $2$ when divided by $4$?