|
|
|
|
|
|
|
|
Pigeonhole Among Friends
 A tacit assumption in the formulation of the problem is that the relationship of friendship is symmetric: two people are friends iff each is a friend of the other. (However, friendship is not reflexive: no one is his own friend.) Solution 1A person at the party can have 0 up to N-1 friends at the party. However, if someone has 0 friends at the party, then no one at the party has N-1 friends at the party, and if someone has N-1 friends at the party, then no one has 0 friends at the party. Hence the number of possibilities for the number of friends the N people at the party have must be less than N. Hence two people at the party have the same number of friends at the party. Solution 2(This solution appears in Smullyan.) Note, as in the first solution, that in general, in a group of N people, a fellow may have 0, 1, 2, ..., N-1 friends. Assume to the contrary that all N people have different number of friends. Then for each number in the sequence 0, 1, 2, ..., N-1 there must be a fellow with exactly this number of friends. In particular, there is at least one with N-1 friends. But, if so, all others have this fellow as a friend, implying that there is no one with no friends at all. Therefore, the only possible numbers of friends come from the shortened sequence: 1, 2, 3, ..., N-1. By the Pigeonhole Principle, there are at least two with the same number of friends, so that our assumption that this is not true proved wrong, thus it must be indeed true. Solution 3This solution is due to Vitaly Bergelson of Ohio State University and was communicated to me by Prof. William McWorter: Let P be a person with the most friends, say k friends. If one of P's friends has k friends at the party, we are done. Otherwise, each of P's k friends have fewer than k friends at the party; hence some two of P's friends have the same number of friends at the party. Reference
|
| 33062278 |  |
