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?

  • 3
    $\begingroup$ 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}. $\endgroup$ – TonyK May 31 '13 at 12:09
  • $\begingroup$ Oh thanks. I got it. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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