0
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.