Triomino problem

This is similar to the domino problem (I also posted this in the forum at 'I luv 2 do maths', but they don't seem to be very keen at solving it):

We have a chess board (64 squares) and 21 triominos (63 squares, the triominos has the "I" shape). It is possible to cover the chess board with all the triominos, meaning only one square will be uncovered. Prove that this square is always one of the red squares:

Just to make things clear, these are triominos:

http://upload.wikimedia.org/wikipedia/commons/2/22/Trominoes.svg

The shape we are using is the left one.

I've seen several n-omino puzzles, but not this one. But once you know how to solve one, you know how to solve all I guess. Spoiler:

This one involves two different colorings of the chess board, which both limit the possible remaining square to a set of 22 squares. Since the square must be in both sets, it must be in the intersection of the sets, which only contains these four squares.

And to prove that these are actually possible remaining squares, one obviously only has to prove one case because of symmetry. If we take the upper-left red square, then we can first complete the upper-left 5x5 block with 8 triominoes (4 blocks of 2x3 wrapped around the middle), and then we can fill the a1-e3 block with five vertical triominoes and the f1-h8 block with eight horizontal triominoes.

Phobetor, I think you're right about knowing one pretty much means knowing all...

The solution is correct as well.

Also interesting is the same problem, but with the other piece from your URL (the l-shaped piece). Can you cover 63 squares of the board with 21 pieces? And which squares can be the remaining, non-covered square?

With a certain mathematical problem-solving strategy, you can also find the solution for general 2^n x 2^n boards, for n = 1, 2, ... easily. Then of course taking n = 3 you also get the solution for the 8x8 chessboard.