perplexus.info :: Logic : Mutually friendly 2

Mutually friendly 2 (Posted on 2011-07-01)

In Mutually friendly, we proved that if any two people are either friends or strangers, then any group of six people either contains 3 mutual friends or 3 mutual strangers, or both. Now, they can also be enemies.

Suppose that any two people are either friends, enemies, or strangers. Prove that any group of 17 people either contains 3 mutual friends, 3 mutual enemies, or 3 mutual strangers.

Submitted by Math Man

Rating: 5.0000 (1 votes)

Solution: (Hide)

Take any person X. X is either friends with at least 6 people, enemies with at least 6 people, or strangers with at least 6 people. Suppose X is friends with at least 6 people. Take 6 of these people. If any two of them are friends, then these two and X are three mutual friends. If no two of them are friends, then any two are either enemies or strangers. Then, by Mutually friendly, there are either three mutual enemies or three mutual strangers.

A similar proof happens if X is enemies with at least 6 people, or X is strangers with at least 6 people. Therefore, any group of 17 people either contains 3 mutual friends, 3 mutual enemies, or 3 mutual strangers.

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
Confirmed: 17 is the minimum	Steve Herman	2011-07-02 22:18:46
Proof (spoiler)	Steve Herman	2011-07-01 17:31:51
re: The enemy of my enemy is my friend?	Math Man	2011-07-01 17:21:26
The enemy of my enemy is my friend?	Steve Herman	2011-07-01 14:43:25

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info