Pigeonhole principle- Show that two co-prime integers exist

Question

Suppose that you are given $n + 1$ different positive integers less than or equal to $2n$. Show that there must exist two which are relatively prime.
The book provides a nice hint which is difficult to come up with : Prove instead that there are two consecutive numbers. So, my solution differs a bit.
It would be great if someone could proof-read my solution which goes as follows:

If two numbers $a,b$ are not co-prime, then $\exists$ prime $p : p|a, p|b$. Therefore, both the elements must be two of $\lceil{\frac{2n}{p}}\rceil < \frac{2n}{p}$. Now, as we are counting pairs, and the $n+1$ numbers are unique, we can count $\frac{n}{p}$ slots for the pairs corresponding to p. So, overall we have $\frac{n}{2}+\frac{n}{3}+\frac{n}{5}+\cdots+\frac{n}{q}$ such that $q$ is the last prime less than $2n$ (actually $\sqrt{2n}$ should suffice) Now, we have $ {n+1 \choose 2 } = \frac{n*(n+1)}{2}$. So, as the above summation is less than $n+1 \choose 2$(every prime after 3 is greater than 2 and there are at most n terms), we must have some pair outside these multiplication tables hence two co-prime numbers among these must exist.

Answer 1

If I understand what you've done correctly, it doesn't work. You can certainly have a lot more than $\frac n2$ pairs which have a factor of $2$ in common: in fact you can have $\binom n2$ since all the even numbers could be in your set.

Answer 2

$n$ numbers can be chosen out of $2n$ numbers with a gap between any two numbers. So by the pigeon hole principle the $(n+1)$th number will be adjacent to one of the $n$ numbers. Hence there is at least one pair that is consecutive hence co-prime.

Answer 3

Partition the set of numbers from $1$ to $2n$ into $n$ subsets $\{ \{2i-1,2i\}: 1\leq i\leq n\}.$ By the Pigeon-Hole Principle, if $n+1$ numbers are chosen from $1,..., 2n$ then for some $i$ the set $\{2i-1,2i\}$ will contain $2$ of them.