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 '15 at 3:09
• @Gregory: Well, it was intended just to be a (fairly generous) hint. – Brian M. Scott May 29 '15 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 '15 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.

• Sorry for reviving this thread. I wish to understand why we can write $x = 2^ab$ based on the unique factorization of integers. – LanceHAOH Nov 27 '17 at 16:21
• @LanceHAOH Because $2$ is prime. We can factor any positive integer into a product of powers of distinct primes $p_1^{a_1}\cdots p_n^{a_n}$. At most one of those primes can be $2$. – Gregory Grant Nov 27 '17 at 16:42
• If I understood you correctly, we multiply all $p_i^{a_i}$ where $p_i^{a_i}$ is odd. This result, b, is still odd. Since factorization of integers is unique, only integers with the same b and conseqentially $2^ab$ will be mapped to the same partition. – LanceHAOH Nov 27 '17 at 23:35
• @LanceHAOH Sounds good – Gregory Grant Nov 28 '17 at 2:46

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.