The Mutilated Chessboard
Two diagonally opposite corner squares are removed from a chessboard, leaving 62 squares. Can the remaining board be tiled exactly by 31 dominoes? Answer yes or no, and be ready to prove it.
Related problems
Source: Posed by Max Black (1946); the colouring argument is commonly credited to Ralph Gomory. Statement written for AxiomIQ.