This other answer shows that an 8x8 board with opposite squares removed cannot be tiled with dominoes, as they are of the same "colour". But what if two squares of opposite colours are removed? Ralph E. Gomory showed that it is always possible, no matter where the two removed squares are, and this is his proof.
alt text http://shreevatsa.files.wordpress.com/2010/03/tiling-gomory.png
(Imagine A and B are the squares removed.) The image is from Honsberger's Mathematical Gems I.
