How might I prove that an n-length subset of {1,2,..2n-2} must have at least 2 consecutive members?

Question

I am trying to prove that at least 2 members of an n-length subset of {1,2,...2n-1} will be relatively prime. The way I am thinking about it is that if 1 is included, then 1 is relatively prime with any other member. If 1 is not included, then there are only 2n-2 choices. Because of spacing, two of these must be consecutive and since any two consecutive numbers are relatively prime, this proves the original theorem. I will prove that any two consecutive numbers are relatively prime with Euclidean algorithm, but I don't know how to prove that there must be consecutive numbers even though I know its true.

Answer 1

The result follows from considering the consecutive pairs $$\{2, 3\}, \{4, 5\}, \ldots, \{2n-4, 2n-3\}, \{2n-2, 2n-1\}.$$ Clearly, there are $n-1$ such sets, so by the pigeonhole principle, choosing $n$ numbers from the set $\{2, 3, \ldots, 2n-1\}$ must mean choosing both numbers from one of these pairs.

Think of the maximum number of numbers you can choose from the above pairs such that no pair has both of its numbers selected. This means choosing one number from each pair, but there are only $n-1$ such pairs. If we choose one more number, it will mean it must be taken among one of the pairs already chosen.