Sign up ×
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.

We have n+1 numbers from the set {1...2n} and prove that there are 2 such that one divides the other... I just could not understand the solutions that already exist some

share|cite|improve this question

marked as duplicate by Pedro Tamaroff, Old John, Dan Rust, Stefan Hamcke, T. Bongers Nov 8 '13 at 2:50

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

The question appears to be verbatim from some source. Is it homework? What have you tried? –  Jonathan Y. Nov 8 '13 at 1:59
Look at the list on the right side of the page, you will see your question, with answer. It has also been asked and answered several other times on MSE, a search should do it. –  André Nicolas Nov 8 '13 at 2:00
Hint: Use the hint. If $x$ is in your set, write $x=2^ky$. What are the possible values of $y$? –  bof Nov 8 '13 at 2:00

2 Answers 2

Do what the hint says.

Write each number as $2^k m$ for some odd number $m$ between $1$ and $2n - 1$.

How many odd numbers ($m$) are there here? How many total numbers are in your set?

Now apply the pigeon hole principle.

share|cite|improve this answer
I don't see it yet. what is k? –  user103082 Nov 8 '13 at 2:34
We're just taking each number and factoring out all powers of $2$. –  Deven Ware Nov 8 '13 at 5:58

Well, we can divide your set to two separate sets: $ A=\{1,\,3\,,\,..., \,n\} $ and $ B=\{2,\,4\,,\,..., \,2n\} $.

Providing that $ n\in\mathbb{N}$ those two sets have equal sizes, and we notice that each element from $ B $ is some element of $ A $ multiplied by $ 2 $ or some other element of $B$ multiplied by $2$, hence if we remove powers of $ 2 $ from each element (that means, we divide each element named $a$ by $2^k$ where $k$ is $\lfloor\log_2a\rfloor$ and take rest) of $A$ and $B$ we will receive 2 sets, $A'$ and $B'$ such that $A'\cup B'=A'$.

Now we use pigeonhole principle - $A'$ has $n$ elements, we "mark" all of them, +1 addional, but since we have no other elements that those of $A'$ and $B'$ we have to mark one that we already have, QED.

Edit: Sets were not divided well, thanks @Henry Swanson

share|cite|improve this answer
If $n$ is $10$, $11 \in B$, but $11$ is certainly not an element of $A$ multiplied by $2$. –  Henry Swanson Nov 8 '13 at 2:26
that was a great observation thanks Mr. @HenrySwanson –  user103082 Nov 8 '13 at 2:35
could you expand a little on "... of them, +1 addional, but ..." –  user103082 Nov 8 '13 at 2:50
$A'$ has $n$ elements. You have to choose $n+1$ elements from $A\cup B$, but if we think about what $A'$ consists of, we see that we have only $n$ elements that do not divide one another in whole $A\cup B$. –  Annisar Nov 8 '13 at 2:58
now I totally understand this question. thank you very very much Mr. @KamilSołtysik –  user103082 Nov 8 '13 at 3:01