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

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.

  • $\begingroup$ The question appears to be verbatim from some source. Is it homework? What have you tried? $\endgroup$ – Jonathan Y. Nov 8 '13 at 1:59
  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Nov 8 '13 at 2:00
  • $\begingroup$ Hint: Use the hint. If $x$ is in your set, write $x=2^ky$. What are the possible values of $y$? $\endgroup$ – 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

  • $\begingroup$ If $n$ is $10$, $11 \in B$, but $11$ is certainly not an element of $A$ multiplied by $2$. $\endgroup$ – Henry Swanson Nov 8 '13 at 2:26
  • $\begingroup$ that was a great observation thanks Mr. @HenrySwanson $\endgroup$ – user103082 Nov 8 '13 at 2:35
  • $\begingroup$ could you expand a little on "... of them, +1 addional, but ..." $\endgroup$ – user103082 Nov 8 '13 at 2:50
  • $\begingroup$ $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$. $\endgroup$ – Annisar Nov 8 '13 at 2:58
  • $\begingroup$ now I totally understand this question. thank you very very much Mr. @KamilSołtysik $\endgroup$ – 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.

  • $\begingroup$ I don't see it yet. what is k? $\endgroup$ – user103082 Nov 8 '13 at 2:34
  • $\begingroup$ We're just taking each number and factoring out all powers of $2$. $\endgroup$ – Deven Ware Nov 8 '13 at 5:58