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?

$\endgroup$
2
  • $\begingroup$ $2n$ and $n$ of course $\endgroup$
    – user
    Nov 13, 2018 at 13:21
  • 1
    $\begingroup$ You don't mean "size $\geq 2$", but "size $>n$" perhaps? $\endgroup$
    – B. Goddard
    Nov 13, 2018 at 13:24

1 Answer 1

Reset to default
2
$\begingroup$

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

$\endgroup$
2
  • $\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, 2018 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, 2018 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.