Prove that there are two numbers among them such that one divides the other [duplicate]

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

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

• 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

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

• 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

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.

• 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