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

 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.

 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

 Search: Search body:
Forums (0)