We have this set : $$A=\{1,2,3, \dots , n\}$$

We choose $\left\lceil\frac{n}{2}\right\rceil+1$ numbers from $A$. Can we prove that at least two numbers exist that are divisible ? (In other words, either $a\mid b$ or $b\mid a$.)

Example : If $A = \{1,2,3,\dots ,20\}$ we must choose $11$ numbers to get at least two numbers divisible.

  • $\begingroup$ It is obvious that $1|3$ $\endgroup$ – S.H.W Dec 26 '16 at 8:50
  • $\begingroup$ My mean is GCD not HCF $\endgroup$ – S.H.W Dec 26 '16 at 8:51
  • 1
    $\begingroup$ Greatest Common Divisor (GCD) = Highest Common Factor (HCF). Your last statement (in brackets) has slightly different from the rest of the question. $\endgroup$ – Swapnil Rustagi Dec 26 '16 at 8:54
  • $\begingroup$ If $n$ is odd , for example $n=5$ we must choose $3$ numbers. $\endgroup$ – S.H.W Dec 26 '16 at 8:55
  • $\begingroup$ Don't you mean $a\mid b$ or $b\mid a$? $\endgroup$ – Darth Geek Dec 26 '16 at 8:55

Yes it is true, but only if $n$ is even. There are a lot of counterexamples which are clearly mentioned in comments and other answers too that explains why $n$ can not be odd.

HINT: Try pigeonhole principle.

By factoring out as many $2's$ as possible, any number from the given set can be written as $2^k.a$ where $a$ is odd number and $k\ge0$.

For example $12=2^2\times 3$ and $3$ is odd. $28=2^2\times 7$ and $7$ is odd. $33=2^0\times 33$ and $33$ is odd etc.

Now $a$ can be any odd i.e. $1,3,5...... $ From the given set and there will be $\frac{n}{2}$ of such numbers ($a$). So whenever you select $\frac{n}{2} + 1$th number there must be two numbers having the same value of $a$. For example $l=2^p\times a$ and $m=2^q\times a$.

When $p>q$ then $m|l$ and when $q>p$ then $l|m$.

  • $\begingroup$ Can you explain "By factoring out as many 2's as possible, any number from the given set can be written as $2^k$" ? $\endgroup$ – S.H.W Dec 26 '16 at 9:42
  • $\begingroup$ Can you determine $a$ and $k$ in your answer ? $\endgroup$ – S.H.W Dec 26 '16 at 9:47
  • $\begingroup$ I'm sorry but I'm still unable to understand your solution . $\endgroup$ – S.H.W Dec 26 '16 at 9:49
  • $\begingroup$ Okay , Thank you a lot. $\endgroup$ – S.H.W Dec 26 '16 at 9:59
  • $\begingroup$ @S.H.W, now see the answer $\endgroup$ – I am Back Dec 26 '16 at 10:05

No, let $n=3$ such that $A = \{1,2,3\}$. Now we pick $\lfloor \frac{3}{2} \rfloor + 1 = 2$ numbers from $A$, being $2$ and $3$. These are relatively prime hence not divisible.

  • $\begingroup$ Please check it again . $\endgroup$ – S.H.W Dec 26 '16 at 9:09
  • $\begingroup$ @S.H.W are you also including pair of (3,1)? $\endgroup$ – Kanwaljit Singh Dec 26 '16 at 9:16
  • $\begingroup$ Yes , (1,3) is valid $\endgroup$ – S.H.W Dec 26 '16 at 9:17
  • $\begingroup$ And you are only assuming continues numbers starting from 1? $\endgroup$ – Kanwaljit Singh Dec 26 '16 at 9:18
  • $\begingroup$ Your mean is natural numbers ? $\endgroup$ – S.H.W Dec 26 '16 at 9:18

For $n=2m+1>1$ choose $x$ for $m+1\leq x\leq 2m-1$ and choose $m$ and choose $2m+1.$ This gives $m+2$ numbers, no two of which are divisors of each other. For even $n,$ I dk.


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.