Question

Pigeonhole Principle

2. (10 pts) Using the Pigeonhole Principle, show that in every set of 100 integers, there exist two whose difference is a multiple of 37.

Answer 1

The pigeonholes in this case can be considered as buckets numbered from 0 to 36 .

Basically if a number n%37 = r where 0<=r<=36 then we place the number n into the bucket numbered r.

Now we have 100 such numbers.

But we have only 37 buckets (0 to 36) to place all of these numbers.Thus it is obvious that many of the buckets (at least one for sure) will store more than 1 number.

Let's say that we have a bucket numbered r which has stored numbers n1 and n2. (As shown above there has to be at least one bucket with more than 1 number stored in it)

Now as the numbers n1 and n2 are stored in the bucket numbered r, it implies that n1%37 = n2%37 =r

So we can express n1 as n1 = p*37+r

Similarly n2 = q*37+r

Without loss of generality lets assume that n1>n2 (n1 cannot be equal to n2 as it is a set of 100 integers)

Therefore n1-n2 = ( p*37+r )- ( q*37+r )

                        = (p-q)*37     where p>q since n1>n2

                        = some multiple of 37

Thus we have proven that there exists two integers in a set of 100 integers whose difference is a multiple of 37 using pigeonhole principle