This is a classic of course, but there is a lesser known extension to this problem (to be read only after this problem has been solved), which also has a beautiful "proof without words":

> an 8x8 board in which squares at opposite corners have been removed cannot be tiled with dominoes, [...]. But what if two squares of different colours are removed? Ralph E. Gomory showed that it is always possible, no matter where the two removed squares are

Proof/spoiler: https://mathoverflow.net/a/17328/111