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 thought it would be worthwhile to write out Brian's proof with more detail.  
Let $A=\{1,2,\dots,2n\}$.  Write $A=E\cup O$ where $E$ are the evens and $O$ are the odds.  Then $|O|$, the size of $O$, is $n$.  Now let $x\in A$.  Then by the unique factorization of integers we can write $x=2^ab$ where $b$ is odd.  The association $f:x\mapsto b$ therefore gives a well defined mapping $A\rightarrow O$. Since $|O|=n$, $|f(C)|\leq n$ for any subset $C\subseteq A$.  Therefore, if $C\subseteq A$ has $n+1$ elements, there must be two elements $c_1,c_2\in C$ such that $f(c_1)=f(c_2)$.  In other words $c_1=2^{a_1}b$ and $c_2=2^{a_2}b$.  So if $a_1<a_2$ then $c_1$ divides $c_2$.  Otherwise $a_1>a_2$ and $c_2$ divides $c_1$.  Q.E.D.
