Can you prove that:
- if you have integers less than or equal to then there are always two of them which are relatively prime?
This problem comes from the biography of Paul Erdös, The Man Who Loved Only Numbers. Erdös posed this problem to Louis Pósa, who was 12 at the time and a child prodigy, and who solved it in about 10 minutes.
This is one of those problems where you can spend hours getting nowhere, and yet the proof is actually very simple 😕