# Proof using an application of Pigeonhole Principle

Prove that every $$(n+1)$$-element subset of $$\{1,2,3,\dots,2n\}$$ contains $$2$$ distinct integers $$p$$ and $$q$$, such that gcd$$(p,q)=1$$.

Here's my attempt:

Let $$X \subseteq \{1,2,3,...,2n\}$$ be the set of choices for $$p$$.

Let $$Y = \{p+1 \ | \ p \in X\} \subseteq \{2,3,4,...,2n+1\}$$ be the set of choices for $$q$$.

We will take $$p$$ and $$q$$ to be consecutive since that's one way to ensure their greatest common divisor is $$1$$.

Then $$X \cup Y \subseteq \{1,2,3,4,...,2n,2n+1\}$$

Now I know I'm supposed to infer something from the sizes of these sets, but I can't put it all together.

Any help is appreciated, thanks!

You have actually proved it already. Since you are taking more than half from $$\{1,2,\cdots,n\}$$, by Pigeonhole Principle, there must be neighboring numbers $$p$$, and $$p+1$$ present in the subset you take. And $$GCD(p,p+1)=1$$
Add: Suppose not, i.e., you can take $$n+1$$ distinct numbers from the set $$\{1,2,\cdots,2n\}$$ and each number is 2 (or more) bigger than the number precedes it, the biggest number will be (at least) $$(n+1-1)*2=2n$$ bigger than the smallest one. While in our set, the biggest, which is $$2n$$ is only $$2n-1$$ bigger than the smallest, which is $$1$$. This is a contradiction.