How many numbers does one need to pick from the set 2 3 200

How many numbers does one need to pick from the set {2, 3, ..., 200} to make sure that at least two of the picked numbers have a common divisor greater than 1?

Solution

First we count number of prime numbers in this set ie 2,3,5,7,... so on till 199. There are 46 prime numbers in this set.

Now for any two numbers to have common divisor greater than 2 means not both can be prime.

So since we need to find minimum numbers to be picked so that we can be sure

Note we can first pick only the prime numbers till 199 and then pick any other number from the set. All these other numbers are composite so must share factor with one of these prime numbers, in particular with prime numbers from,2 upto 97 since primes larger than 97 will not have multiples less than equal to 200

SO a minimum of 46+1=47 numbers need to be picked.