Take the 2-minute tour ×  Prove that in any set of $n+1$
positive numbers not exceeding $2n$ there must be two that are
relatively prime.  share|improve this question This is an old
problem. Without giving too much away, have you thought about
how you could definitely tell that two numbers are coprime? And
maybe the bounds you are given may suggest using the pigeonhole
principle? I think this is one you should work at before asking
it. –  Mark Bennet Jul 2 '11 at 20:34 add comment  4 Answers  In
some circles at least this is as famous as the question of what
is the sum of the first $n$ positive integers. It is often
called the Posa Problem, because it was the problem that Erdos
asked of the (then) 12 year-old Lajos Posa upon first meeting
him. According to Erdos, Posa solved it in about $30$ seconds,
all the while eating a bowl of soup. An account of this story is
here; there must be a more primary source somewhere.  P.S.: I
have some colleagues who work in the branch of mathematics --
additive combinatorics