# Proving there exists a multiple which is not also a multiple of another given integer

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?

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

This is false. Take $$n=10$$ and pick $$\{3, 7\}$$. None of them divide each other.
• Yes, sorry, I made a typo in the question. It should say "any subset of size $n+1$". Could you have a look again? – Prasiortle Nov 13 '18 at 15:27
• @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. – Ovi Nov 13 '18 at 17:09