Associated Topics || Dr. Math Home || Search Dr. Math

### 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 ?

some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search