Friends at a party: Difference between revisions
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 05: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.
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.