Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question

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

share|cite|improve this answer
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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.