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

  • 1
    $\begingroup$ Note: 'evenly divides' doesn't mean one of the numbers are even, it means that one divides another with 0 remainder. (I'm not sure if this is what you thought, but just in case). Pick 101 elements of $A$ (I'm assuming they're all distinct, otherwise the result is trivial). What can you say about the smallest number $x$ you've picked? It's at least ... Now can you apply the pigeonhole principle to remainders of the other 100 numbers modulo $x$? $\endgroup$ – ah11950 Apr 26 '14 at 7:10
  • $\begingroup$ @ah11950 Right. Major misunderstanding there! $\endgroup$ – user3511965 Apr 26 '14 at 7:10
  • 1
    $\begingroup$ No worries. 'Evenly divides' isn't ever a term I would use... Give the question another shot now! You at least have the right idea thinking you'll need to apply pigeonhole. $\endgroup$ – ah11950 Apr 26 '14 at 7:11
  • $\begingroup$ @ah11950 Ok, but can I still do the worst case of 100 even + 1 odd and 100 odd + 1 even or does that not matter at all? $\endgroup$ – user3511965 Apr 26 '14 at 7:13
  • 1
    $\begingroup$ Why 100 boxes? (This is pretty much correct, but needs a bit of justification - it's actually at most 100 boxes). If $S$ is your subset of 101 numbers in $A$, $x$ the minimal element of $S$, and $m, n \in S\setminus \{x\}$, what can you conclude if $m \equiv n\; (\text{mod}\; x)$? Indeed, does this necessarily occur? $\endgroup$ – ah11950 Apr 26 '14 at 7:18

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

  • $\begingroup$ but how to show that there will be two such that one evenly divides the other $\endgroup$ – user469065 Oct 1 '19 at 16:22

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.

  • $\begingroup$ Hmmm... why no even boxes? $\endgroup$ – user3511965 Apr 26 '14 at 7:24
  • $\begingroup$ These are just labels for the boxes. They happen to be convenient. Note that (for example) if $a$ and $b$ are in box 5, then $a$ divides $b$ or $b$ divides $a$. Same with the other boxes. $\endgroup$ – André Nicolas Apr 26 '14 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.