1
$\begingroup$

I am attempting to prove the statement: "If $n$ is a positive integer, and you choose any subset of size $n+1$ from the set $\{1,2, \cdots, 2n\}$, it will always be possible to find two distinct elements in the subset such that one is a factor of the other".

I have found a method which works provided that the following proposition is true: if $a < b \leq n$ and $a$ does not divide $b$, then there exists some multiple of $a$ within the set $\{n+1,n+2,...,2n\}$ which is not also a multiple of $b$. How can I prove this proposition?

|cite|improve this question
$\endgroup$
  • $\begingroup$ $2n$ and $n$ of course $\endgroup$ – gimusi Nov 13 '18 at 13:21
  • 1
    $\begingroup$ You don't mean "size $\geq 2$", but "size $>n$" perhaps? $\endgroup$ – B. Goddard Nov 13 '18 at 13:24
2
$\begingroup$

This is false. Take $n=10$ and pick $\{3, 7\}$. None of them divide each other.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Yes, sorry, I made a typo in the question. It should say "any subset of size $n+1$". Could you have a look again? $\endgroup$ – Prasiortle Nov 13 '18 at 15:27
  • $\begingroup$ @Prasiortle Sure. I've already tried to think of a solution to that problem using the pigeonhole principle, but I've concluded that you can't solve it using just a simple pigeonhole. The idea is to make $n$ pairs of two, and in each pair one element divides the other. But you cannot make such pairs; for example, if $n = 10$, you must put $17$ with $1$, but then you don't have anything to put $13$ with. $\endgroup$ – Ovi Nov 13 '18 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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