The renowned mathematician Paul Erdős told this story about the 12-year-old Louis Pósa

While Pósa was eating his soup, I asked him the following question. Prove that if you have n + 1 positive integers less than or equal to 2n, some pair of them are relatively prime.

Here's the very neat proof Pósa came up with in about half a minute. I like it because it uses a sort of reverse pigeonhole principle.

Imagine we have boxes and we put the integers into the boxes like this

Now we try to choose the integers. Since we want more integers than there are boxes we are bound to empty at least on box and so our selection will include a pair of consecutive integers.

But a pair of consecutive integers, say and must always be relatively prime; that have no common factor greater than , because any such factor of would leave a remiander of when divided into .

For more about Pósa see his Wikipedia biography.