We have a set A of numbers 1, 2, 3… to 200
The question is asking me to prove that if I choose 101 numbers from the set, there will be two such that one evenly divides the other.
I know this could be the pigeonhole principle question. I could prove by contradiction that no two numbers will evenly divide each other. Assume I take 101 numbers, I can't take all the odd numbers because there is only 100 of them, so there will be an even number. I think this goes no where.
Using a direct proof if I choose 101 numbers, I will get either 100 even + 1 odd or 100 odd + 1 even. In order for two numbers to evenly divide each other I would choose the 100 even, and there is a big probability that two will be even, but if I have 100 odd + 1 even, there will be only 1 even… So I'm not sure how to solve this…
Best Answer
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$?