# 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!

-

HINT: Create a pigeonhole for each odd positive integer $2k+1<2n$, and put into it all numbers in $[2n]$ of the form $(2k+1)2^r$ for some $r\ge 0$.

-
Ok, so for any set S=(1, 2, ..., 2n), we choose all odd numbers from that S, so So=(1, 3,...,2k+1) such 2k+1 < 2n. For each element in S choose those that satisfy (2k+1)2^r, which are multiples of each element in So. Let this set be S2 = (2, 6,...,(2k+1)2^r), as long as (2k+1)2^r < 2n. S2 is necessarily bigger than So, and thus, each element in So can be 'mapped' to multiple multiples of itself. Consequently, any set bigger than S, of size n+1, must also have this property. Is this reasoning correct? –  user64093 Feb 26 '13 at 18:38
I just love this proof, I saw it in 1999 but forgot how to do it so I'm glad to find it here. Your answer is a bit terse tho, I had to stare at it for a while, a novice might have trouble following it. –  Gregory Grant May 29 at 3:09
@Gregory: Well, it was intended just to be a (fairly generous) hint. –  Brian M. Scott May 29 at 3:19
@BrianM.Scott I got ya. I did go ahead and post an answer with more details. Hope you don't take that wrong, it's not criticism of your answer, it's homage to it. –  Gregory Grant May 29 at 3:22

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.

-