Changes

Jump to: navigation, search

Friends at a party

887 bytes added, 05:46, 13 October 2010
Hint and solution.
An extremely popular mathematician threw a party. Including himself, there were 15 people at the party. Must there have been at least two people with the same number of friends present? Explain.
 
{{Hint | Assume friendship is mutual, i.e. if A is a friend of B then B is a friend of A.}}
 
{{Solution |
 
The least number of friends a person might have is 0 (gatecrasher) and the greatest is 14 (friends with everyone, excluding themselves). There are as many integers in that range as there are people at the party, so if everyone has a different number of friends, then every number from 0 to 14 must be equal to that number for some person.
 
But if some person (very likely the mathematician) has 14 friends, and we assume friendship is always mutual, then there can be no person with 0 friends. Everyone must have at least one friend, namely the person with 14 friends.
 
Therefore the assumption that everyone has a different number of friends leads to a contradiction, and by ''reducto ad absurdum'' we conclude that at least two people must have the same number of friends.
 
}}
[[Category: Graph theory]]
[[Category: Pigeonhole principle]]
51
edits

Navigation menu