An interesting problem using Pigeonhole principle I saw this problem: Let $A \subset \{1,2,3,\cdots,2n\}$. Also, $|A|=n+1$.
Show that There exist $a,b \in A$ with $a \neq b$ and $a$ and $b$ is coprime.
I proved this one very easily by using pigeon hole principle on partition on $\{1,2\},\{3,4\},\dots,\{2n-1,2n\}$.
My question is How can I prove or disprove that:
Let $A \subset \{1,2,3,\cdots,2n\}$. Also, $|A|=n+1$.
Show that There exist $a,b \in A$ with $a \neq b$ and $a|b$.
I can't make suitable partition. Is this true?

Any number from the set $A$ is of the form $2^{k}l$ where $k\ge 0,0\le l\le (2n-1)$ and $l$ is odd.
Number of odd numbers $l\le (2n-1) $ is $n$.
Now if we select $(n+1)$ numbers from the set $A$ then there must be two numbers(among the selected numbers) with the same $l$.
That is, we must get $a,b$ with $a=2^{k_1}l$ and $b=2^{k_2}l$ now as $a\ne b$ so $k_1\ne k_2$.Now if $k_1>k_2$ then $b|a$ else $a|b$.
This completes the proof.
