Remainders, Pigeons, and Pigeonholes

Date: 03/26/2003 at 18:05:29
From: Stephanie
Subject: Pigeonhole Principle

Seventeen integers are given. Prove that it is always possible to 
select five of the seventeen whose sum will be divisible by 5.

I'm just not sure how to use PHP with this problem. When you divide by 
5, there are 5 possible remainders: 0,1,2,3,4. Then these are the 
pigeonholes. But I'm confused; are the 17 integers the pigeons or are 
they the 5 you choose?

Date: 03/27/2003 at 10:18:46
From: Doctor Nbrooke
Subject: Re: Pigeonhole Principle

Hi Stephanie, and thanks for writing to Dr. Math.

By the division algorithm, every integer has a unique remainder when 
divided by 5. As you said, the possible remainders are 0, 1, 2, 3, 
and 4: these are your pigeonholes.  The 17 integers are your pigeons.

Notice that if any remainder appears five or more times in your list 
of seventeen integers, then you can choose those 5 integers and take 
their sum, and it will be divisible by five. Observe:

Let A, B, C, D, and E be integers all divisible by r, where r is 
between 0 and 4, inclusive. By the division algorithm, let A = 5a + 
r, B = 5b + r, and so on. Then A + B + C+ D + E = (5a + r) + (5b + 
r) + (5c + r) + (5d + r) + (5e + r). Since addition is commutative, 
we regroup to get (5a + 5b + 5c + 5d + 5e) + (r + r + r + r + r) = 5
(a + b + c + d + e) + 5r = 5((a + b + c + d + e) + r), which is 
divisible by 5.  

So now we know that if we have more than five in a pigeonhole, then 
your sum is divisible by 5. What other situation can you find where 
we know that we can find a sum divisible by 5, but there are still 
fewer than five pigeons in each hole? Figure this out, and the proof 
should practically finish itself for you.

I hope this helps.  If you have any more questions, please feel free 
to write back.

- Doctor Nbrooke, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 03/23/2003 at 07:24:44
From: Doctor Jacques
Subject: Re: The pigeonhole principle

Hi Jillian,

We have indeed 17 pigeons and 5 holes. In this case, the holes are 
residue classes modulo 5. We want to show that we can find 5 numbers 
whose sum is congruent to 0 modulo 5.

However, we must extend the pigeonhole principle to use the fact that  
we have "many" more pigeons than holes in this case.

Assume first that one residue class (say k) contains at least 5 
numbers. We can then select 5 numbers from that class, and the sum 
will be:

  5k = 0 (mod 5)

and we are done.

We can now assume that no hole contains more than 4 pigeons.

In such a case, no hole can be empty - can you show it?

Now, we can pick one number from each residue class modulo 5 (as no 
such class is empty). The sum of these numbers is:

  0 + 1 + 2 + 3 + 4 = (5*4)/2 = 0 mod 5

In general, if p is odd, and we have a set of N > (p-1)^2 numbers, we 
can always select p of them whose sum is a multiple of p. The argument 
is exactly the same.

This problem raises some interesting questions:

  * Is it true for any even p (it is false for p = 2) ?
  * Is this the best possible bound ? For example, with p = 5,   
    would it still be true for N = 16 ?

Does this help?  Write back if you'd like to talk about this 
some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/