Here's one of the first puzzles I remember trying to solve. I failed to solve it and "looked up the answer." The answer required insight; it required making a connection that I don't think I ever would have seen on my own. Here's the puzzle:

You have a checkerboard with the usual 64 black and red squares except that two squares (opposite corners) have been removed. You also have a large supply of dominoes. Each of the dominoes is a size that exactly covers two of the checkerboard's squares. Can you cover the 62 squares with 31 dominoes? If so, how? If not, explain how you know it is impossible.