All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Logic
Mutually friendly 2 (Posted on 2011-07-01) Difficulty: 3 of 5
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
SolutionConfirmed: 17 is the minimumSteve Herman2011-07-02 22:18:46
SolutionProof (spoiler)Steve Herman2011-07-01 17:31:51
re: The enemy of my enemy is my friend?Math Man2011-07-01 17:21:26
Some ThoughtsThe enemy of my enemy is my friend?Steve Herman2011-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 (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2018 by Animus Pactum Consulting. All rights reserved. Privacy Information