Pigeon hole (1)

Question

Prove that out of hundred whole numbers one will always have $15$ of them such that the difference between any two of these $15$ numbers is divisible by $7$.

Answer 1

Look if out of 100 given numbers if we get 15 numbers such that the difference between any two of them is divisible by 7 then the remainder given by these 15 numbers when divided by 7 will be same.

Now,when a number is divided by 7 the remainder belong in the set {0,1,2,......,6}

Now, consider the numbers 0,1,...,6 as holes and pigeons be the 100 given numbers.

Now, among the given 100 numbers

the nos. of the form 7k are put in hole 0

numbers of the form 7k+1 are put in hole 1.

.......numbers of the form 7k+6 are put in hole 6.

Note that if we can prove that any one of the holes contain 15 numbers then we are done.

So, suppose none of the holes contain 15 nos. then there could be at most 14 numbers in each hole and then the number of pegions could be at most 14 * 7 = 98.

But we know that there are 100 pegions. Hence contradiction.

So,there must exist atleast one hole which contains 15 nos.

So, out of given 100 numbers we will always find 15 nos. such that the difference between any two of them will be divisible by 7.