Home > Logic
| Mutually friendly 3 (Posted on 2012-08-05) |
 |
Prove that if any two people are either friends or strangers, then any group of 18 people contains either 4 mutual friends or 4 mutual strangers.
|
|
Submitted by Math Man
|
|
Rating: 5.0000 (1 votes)
|
|
|
Solution:
|
(Hide)
|
Take any person X. They are either friends with at least 9 people or strangers with at least 9 people. Suppose X is friends with at least 9 people. Let S be a set of 9 of these people.
Take any person A in S. If A has less than 3 friends in S, then there are at least 6 people in S that are strangers with A. By Mutually friendly, these 6 people contain either 3 mutual friends or 3 mutual strangers. If they contain 3 mutual friends, then these 3 and X are 4 mutual friends. If they contain 3 mutual strangers, then these 3 and A are 4 mutual strangers. If A has at least 4 friends in S, then there are 4 people that are friends with both X and A. If any two of these people are friends, then these two, X, and A are 4 mutual friends. If they are all strangers, then they are 4 mutual strangers. Therefore, to avoid 4 mutual friends or 4 mutual strangers, A has to have exactly 3 friends in S.
There are 9 people in S, and each person has 3 friends in S. Therefore, there are 27 friendships in S. However, friendships are symmetric, so there must be an even number of friendships. That is a contradiction, so if X is friends with at least 9 people, then there are either 4 mutual friends or 4 mutual strangers.
A similar argument works if X is strangers with at least 9 people. Therefore, any group of 18 people contains either 4 mutual friends or 4 mutual strangers.
|
Comments: (
You must be logged in to post comments.)
|
|
Please log in:
Forums (0)
Newest Problems
Random Problem
FAQ |
About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On
Chatterbox:
|
