Prove two numbers of a set will evenly divide the other

Solution 1:

Pick $101$ elements from $A$, label them $a_1,\ldots, a_{101}$. We can assume that $a_1 < \ldots < a_{100} < a_{101}$. Since we have $101$ distinct elements, $a_1 \leq 99$.

Consider the set of remainders upon division by $a_1$. Since $a_1 \leq 99$, there are at most $98$ such remainders. Let $r_2$ be the remainder upon dividing $a_2$ by $a_1$, $r_3$ the remainder upon dividing $a_3$ by $a_1, \ldots, r_{101}$ the remainder upon dividing $a_{101}$ by $a_1$.

We have $101$ remainders $r_1,\ldots ,r_{101}$ (pigeons), and at most $98$ possible remainders (pigeonholes) upon dividing by $a_1$. Thus, by the pigeonhole principle, $r_i = r_j$ for some $1\leq i < j \leq 101$. Now what can you say about the number $a_j - a_i$?

Solution 2:

Hint: The boxes will have labels $1$, $3$, $5$, and so on up to $199$. Odd labels! Note that there are $100$ boxes.

Box 1: Contains $1,2,4,8,16, 32,\dots$

Box 3: Contains $3,6,12,24, 48, \dots$

Box 5: Contains $5,10,20, 40,\dots$.

And so on.

Box 99: Contains $99,198$

Boxes 101, 103, and so on are pretty boring. Box 101 only contains the number $101$, Box 103 only contains $103$, and so on.