Prove at least two numbers $(a,b)$ exist such that $a|b$ or $b|a$.

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

The statement is true for odd n. We are asked to choose $\frac{n+1}{2}$ numbers from the set (the ceiling function). And so there are $\frac{n-1}{2}$ odd natural numbers not bigger than n, excluding 1 whose case is obvious.