There is a well known problem and impossibility proof concerning a 2m by 2n array of squares, with two opposite corner squares missing.
Prove that this deficient array cannot be covered by dominoes each of which is the size of two such squares.
The proof requires coloring the array as a checker board.
Assume that the missing squares are red.
Any set of dominoes covers just as many black as red squares, but there are fewer red squares to be covered.
I think this example is due to John McCarthy, or at least he considered what sorts of artificial intelligence might find the short proofs. This is a marvelously simple yet in-obvious proof. It is often stated as an 8 by 8 board but that already suggests a board with a checker pattern. These proofs are a wonderful examples of a mathematical proof that anyone can understand.
Here is another such problem with another in-obvious proof that is nearly as simple but with a twist.
This time you have a full 2n by 2n array of squares. You have n2−1 L shape pieces thus:
and a 2 by 2 piece thus:
The L’s can be rotated and flipped.
Prove that the 2n by 2n array cannot be covered.
This is not my invention.