Thread: PigeonHole Principle

Show that in any set of n integers, n>= 3, there always exists a pair of integers
whose dierence is divisible by n - 1. (Use the pigeonhole principle.)


I can never seem to figure out how to do these pigionhole principle problems. Every one of them seems different to the last one I looked at. Is there some kind of process to it? How would you do the one above?

Originally Posted by nukenuts

Show that in any set of n integers, n>= 3, there always exists a pair of integers
whose dierence is divisible by n - 1. (Use the pigeonhole principle.

The key to understanding this is: If (all of these are positive integers) have the same remainder when divided by then is divisible by .

The only remainders when dividing by are those are the pigeonholes and the n integers are the pigeons.

OK what about this one-
Show that in any set X of two or more people, there are two people who have
the same number of friends in X. (Use the pigeonhole principle.)

I can see that this is the case if I write out several sample sets. I figure the people are the pigeons and the number of friends are the holes. But I dont know how to write this down mathematically?

What about
The amount of possible friends for each person in the set X will be between 0 and X-1...Actually wont work because there are X pigeon (people) in the set X, and there are also X holes (number of friends) in the set 0 - X-1.

So if X is 3
Each person could either have 0, 1 or 2 friends. So 3 pigeons into 3 holes...that is not going to work.

Originally Posted by nukenuts

So if X is 3
Each person could either have 0, 1 or 2 friends. So 3 pigeons into 3 holes...that is not going to work.

But if someone has 2 friends, this involves all people in the group, so no person can have 0 friends (presumably, friendship is symmetric).

OK, but would I write that down in a mathematical form? And I need to write it so that it holds for all X, not just X = 3... I just cant see how to write an answer.

Originally Posted by nukenuts

OK, but would I write that down in a mathematical form?

I hope you would.

Originally Posted by nukenuts

And I need to write it so that it holds for all X, not just X = 3... I just cant see how to write an answer.

Consider the same situation for a group of 4 people and try to extend the reasoning from the case of 3 and 4 to n.

You are considering functions from {1, ..., |X|} to {0, ..., |X| - 1} that map people to the number of their friends. You can show that |X| - 1 or 0 is not in the range of such function. This makes pigeonhole principle applicable: the set of pigeons is the domain and the set of holes is the range. More formally, pigeonhole principle says that any function with domain A and range B where |A| > |B| cannot be an injection, and this is precisely the situation that you have here.

Originally Posted by emakarov

I hope you would.

Consider the same situation for a group of 4 people and try to extend the reasoning from the case of 3 and 4 to n.

You are considering functions from {1, ..., |X|} to {0, ..., |X| - 1} that map people to the number of their friends. You can show that |X| - 1 or 0 is not in the range of such function. This makes pigeonhole principle applicable: the set of pigeons is the domain and the set of holes is the range. More formally, pigeonhole principle says that any function with domain A and range B where |A| > |B| cannot be an injection, and this is precisely the situation that you have here.

Cheers for showing me the proper way to view it mate. Ok so I have the two ranges {1, ..., |X|} to {0, ..., |X| - 1} that map people to the number of friends.

If a person has |X| - 1 friends that means they are friends with everyone else in the group, hence nobody will have 0 friends so the range of friendships will be 1 to |X| - 1.

If a person has 0 friends that means there will be nobody in the group who will be be friends with everybody else (nobody will have |X| - 1 friends), so the range will be from 0 to |X| - 2.

In either of these cases the number of possible friendships is |X|-1. Generally, the range of number for friendships will always be of size |X|-1. So putting |X| pigeons into |X|-1 holes means that at least hole will contain more than two items.

Is that a decent way of answering it or is it a bit messy?

Originally Posted by nukenuts

Ok so I have the two ranges {1, ..., |X|} to {0, ..., |X| - 1} that map people to the number of friends.

The word "range" has a specific meaning with respect to functions.

The set of all inputs to a particular function is called its domain. The set of all outputs of a particular function is called its image. In modern mathematics functions also have a codomain. For every function, its codomain includes its image... The word range is used in some texts to refer to the image and in others to the codomain, in particular in computing it often refers to the codomain. (Wikipedia)

I should have used the word "image" in post #7. So, {1, ..., |X|} is the domain and {0, ..., |X| - 1} is the codomain, but the actual image is smaller than the codomain because it does not include 0 or |X| - 1 (or both).

Originally Posted by nukenuts

If a person has |X| - 1 friends that means they are friends with everyone else in the group, hence nobody will have 0 friends so the range of friendships will be 1 to |X| - 1.

If a person has 0 friends that means there will be nobody in the group who will be be friends with everybody else (nobody will have |X| - 1 friends), so the range will be from 0 to |X| - 2.

In either of these cases the number of possible friendships is |X|-1.

And, of course, the same conclusion holds when there are no people with 0 or |X| - 1 friends to begin with.