Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer
+1 Nice one.Good thinking. – Shaswata May 31 '13 at 13:43
Thanks @shaswata – Abhra Abir Kundu May 31 '13 at 13:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.