Using Pigeonhole Principle to prove two numbers in a subset of $[2n]$ divide each other

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$.

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.

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.