Using Pigeonhole Principle to prove two numbers in a subset of $[2n]$ divide each other Let $n$ be greater or equal to $1$, and let $S$ be an $(n+1)$-subset of $[2n]$. Prove that there exist two numbers in $S$ such that one divides the other. 
Any help is appreciated!

I realize this question is old, but I solved it recently when someone else asked me how to prove it.
The proof I came up with doesn't use the pigeonhole principle, instead it uses Mathematical Induction:
Assume the statement is true for $[{1,2,....,2k}]$
Consider the set $P$= $[{1,2,.....,2k,2k+1,2k+2} ]$
Its easier if we partition it, so we have:
$P_1$ = $[{1,2,....,2k}]$ ,$P_2$ =$ [{2k+1,2k+2}]$
We have to select at least $k$ items from $P_1$ as if we select any less than $k$ items from $P_1$, say we select $k-1$, then the additional three items must come from $P_2$, but this is impossible, as $P_2$ only has two items , so we assume the worst case, and select exactly $k$ items from $P_1$. If we were to select more, by our inductive hypothesis, the proof would be complete.
Okay, lets say our selection is $S_k$ .
Now since it is the worst case, we select our remaining two items $2k+1$ and $2k+2$, as if we selected the remaining two items from $P_1$ we would already be done, by our inductive hypothesis.
Consider $2k+2 = 2(k+1)$ . Clearly $k+1 | 2k+2 $
If we choose $k+1$ as part of $S_k$, we are done.
If we did not choose $k+1$ as part of $S_k$ it is part of $P_1 - S_k$ .
Now consider $S_k \cup \ k+1 $
Something in $S_k$ MUST divide $k+1$ or $k+1$ MUST divide something in $S_k$. This is because $S_k \cup \ k+1$ contains $k+1$ items, so by our inductive hypothesis this must be the case. But if $k+1$ divides something in $S_k$, we have a contradiction, as the least multiple of $k+1$ is $2k+2$, which is certainly not in $S_k$.
So something in $S_k$ MUST divide $k+1$ .
If something in $S_k$ divides $k+1$, then something in $S_k$ divides $2k+2$, and the proof is complete.
