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

Home > Logic
Mutually friendly 3 (Posted on 2012-08-05) Difficulty: 4 of 5
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.)
  Subject Author Date
re: I think I have it now!Chris, PhD2012-08-09 22:54:13
SolutionI think I have it now!Caleb2012-08-07 13:08:15
Some Thoughts5 mutual friends or 5 mutual strangersSteve Herman2012-08-07 12:59:13
re(4): No SubjectCaleb2012-08-07 12:33:13
re(3): No SubjectChris, PhD2012-08-07 11:36:30
re(2): No SubjectCaleb2012-08-07 10:58:20
re: No SubjectMath Man2012-08-07 09:25:32
Hints/TipsHintMath Man2012-08-07 09:14:37
Some ThoughtsConfirmed: 18 is the minimumSteve Herman2012-08-07 09:03:44
SolutionNo SubjectChris, PhD2012-08-07 06:46:43
Some Thoughts"Solution"....but only for a total of 20 peopleCaleb2012-08-07 04:07:58
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