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.