# 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}...{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?

• Hint: There are $n$ pigeonholes, but they are not all the same size. For instance, if $n=5$, the pigeonholes contain {1,2,4,8}, {3,6}, {5,10}, {7}, and {9}. – TonyK May 31 '13 at 12:09
• Oh thanks. I got it. – Maddy May 31 '13 at 12:13

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$.