Question

use the pigeonhole principle to show that if one picks nine numbers between 2 and 22 at least two of the numbers chosen must have common divisor d>2..

hint: how many primes are there between 2 and22.?

Answer 1

Number of primes between 2 and 22

= 3,5,7,11,13,17,19

Let assume we have choosen all of these..

Now only 2 numbers remain to be choosen between [4,6,8,9,10,12,14,15,16,18,20,21]

But any prime number divisior satisfy the condiotion(means if we choose 6 then 6 and 3 both are divisor of 3)

Hence numbers remain[4,8,16]

As you can see if we choose any two they would have common divisor..

Hence if one picks nine numbers between 2 and 22 at least two of the numbers chosen must have common divisor d>2..

Please revert back in case of any doubt.

Please upvote. Thanks in advance.