Show that there exists $i$ and $j$ with $1 \leq i<j \leq 51$ satisfying $a_i$ divides $a_j$.

Question

Let $a_1<a_2<...<a_{51}$ be the given distinct natural numbers such that $1 \leq a_i \leq 100$ for all $i=1,2,....,51$. Then show that there exists $i$ and $j$ with $1 \leq i<j \leq 51$ satisfying $a_i$ divides $a_j$.

There are $25$ primes less than $100$. So we must take the set $\{a_1,...,a_{51}\}$ such that the set does not contain all $25$ primes. Because if the set contains all $25$ primes then any number other than these prime would divisible by one of the prime. But from here I can not proceed further. Please help me to solve this.

Answer 1

We can divide the numbers $1$ to $100$ into $50$ different sets. First, put each odd number into a different set. Then, for some set with an odd number $n$, also place all numbers of the form $2^k n$ in the set, where $2^k n$ is between $1$ and $100$. Note that for any pair of numbers in the same set, one divides the other (as one of them will be $2^a$ times the other for some $a$).

Now by the pigeonhole principle, some set must contain $2$ numbers from $a_i$ since there are 50 sets. But then one of these divides the other, finishing the problem.

Answer 2

Thinking in terms of prime numbers is not the way to attack this question. Instead:

Hint: Partition $\{1,2,\dots,100\}$ into sets of the form $\{m,2m,4m,8m,\dots\}$ where $m$ is odd. There are 50 odd numbers between 1 and 100 inclusive, so ...