0

The problem:

How many minimum number of integers must be selected from the set $\{1, 2, 3, 4,\dots,99, 100\}$ to ensure that there are at least two integers in the selection such that one divides the other.

My sloppy thinking: If we select $25$ primes, none of them of course will divide the other. If, however, we choose a $26^{th}$ number, it must divide some or the other. So the answer is 26.

The actual answer, however was 51. Hints?

Akshat Vats
  • 183
  • 6
  • have you considered coprimes? – Aatmaj Jan 14 '21 at 14:18
  • Does this answer your question? [Choosing $101$ numbers from $\{1, 2, \dots , 200\}$.](https://math.stackexchange.com/questions/2271176/choosing-101-numbers-from-1-2-dots-200). Note there are quite a few other similar questions here, e.g., [Prove using induction that from a set of $n+1$ numbers from $\{1,2,..2n\}$, at least one number will evenly divide another.](https://math.stackexchange.com/q/1493253/602049), [$n + 1$ numbers are picked at random from $2n$ integers $1, 2, 3,\dots , 2n$?](https://math.stackexchange.com/q/3588969/602049), etc. – John Omielan Jan 14 '21 at 14:21

0 Answers0