Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

2 Answers 2

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

share|improve this answer

Your Answer

 
discard

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.