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?
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.
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?
The word "range" has a specific meaning with respect to functions.
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).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)
And, of course, the same conclusion holds when there are no people with 0 or |X| - 1 friends to begin with.