Edos test

Let S be a set of n + 1 integers from {1, 2, . . . , 2n}.
Prove that two of them are relatively prime.
First show that this can be avoided if S has only n numbers

http://people.cs.uchicago.edu/~laci/REU07/reupuzzles2.pdf