Given the set of S natural numbers S = {1, 2, 3, . . . , 200} select one hundred and one numbers from S.

Question

Given the set of S natural numbers S = {1, 2, 3, . . . , 200} select one hundred and one numbers from S. Prove that at least one of the numbers you chose is a multiple of another number that you chose.

I know that you are supposed to use the Pigeon Hole Principle, but I don't know how to set up the equation to solve it.

Answer 1

Consider integers equivalent if their ratio is a power of $2$. There are $100$ equivalence classes, one per odd number.