Q:

Prove of distinct a and b given a set

Given a positive integer $n$, suppose $S$ is a subset of $(1, 2,..., 2n)$ with $|S| = n + 1$. Prove that there are distinct $a$,$ b$ in $S$ such that $a$ divides $b$. 
So i know that we have a set of (1,2,3...n+n)
Subset has n+1 elements of the set
So we have a|b or a *something = b
so for example if n=1 then set is 2 and the subset is also 2, but how to show the proof of this specific problem?

A:

This one is a classic.
Write each member of $S$ as $c\cdot 2^k$, where $c$ is odd.  Since there are exactly $n$ odd numbers in $S$, there are exactly $n$ possible values of $c$.
So an $n+1$ element subset must contain two elements $a=c \cdot 2^k$ and $b=c \cdot 2^l$ with the same odd part.  Then either $a|b$ or $b|a$.

