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

This completes the proof.

-
+1 Nice one.Good thinking. –  shaswata May 31 '13 at 13:43
Thanks @shaswata –  Abhra Abir Kundu May 31 '13 at 13:44