Friends at a party: Difference between revisions
Jump to navigation
Jump to search
Oscarlevin (talk | contribs) |
Hint and solution. |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
==Puzzle== | ==Puzzle== | ||
An extremely popular mathematician threw a party. Including himself, there were 15 people at the party. Must there have been two people | 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: Graph theory]] | ||
[[Category: Pigeonhole principle]] | [[Category: Pigeonhole principle]] | ||
Current revision as of 06:46, 13 October 2010
Puzzle
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
Solution