# Pigeonhole Principle

Discussion in 'General Math' started by anheiserb, Oct 11, 2004.

1. ### anheiserbGuest

Wow am I not understanding this problem. The book doesn't have any
closely related examples. If someone can help me through this that
would be great. Thanks, here is the problem:

Let d be a positive integer. Show that among any group of d+1 (not
necessarily consecutive) integers there are two with exactly the same
remainder when they are divided by d.

Jeff

anheiserb, Oct 11, 2004

2. ### Tim BrauchGuest

wrote in 4ax.com:
Remainder when divided by d means we are looking at the numbers modulo d.
What are the possible residuals modulo d?

And an even better question, show that there is at least one pair whose sum
or difference is divisible by d (or is zero). Note, for this, d > 2.

- Tim

--
Timothy M. Brauch
NSF Fellow
Department of Mathematics
University of Louisville

email is:
news (dot) post (at) tbrauch (dot) com

Tim Brauch, Oct 11, 2004

3. ### anheiserbGuest

Thanks Tim. Is this the correct piece for the modulo d -
d+1 mod d

anheiserb, Oct 11, 2004
4. ### Tim BrauchGuest

wrote in
To use the PHP, you have to identift the holes and the pigeons, then
show that the number of holes is less than the number of pigeons. The
PHP will never tell you which hole has two pigeons, only that there is
such a hole. In fact, there might be one hole with all of the pigeons
and that does not violate the PHP.

To solve this problem, you have to decide what the holes are and what
the pigeons are.

A little hint: The pigeons are always what you are trying to say two of
which are related somehow and the holes are always how to partition the
relation.

Bigger hint: You are trying to show two integers are related with the
relation being the remainder after division by d.

- Tim

--
Timothy M. Brauch
NSF Fellow
Department of Mathematics
University of Louisville

email is:
news (dot) post (at) tbrauch (dot) com

Tim Brauch, Oct 12, 2004