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.

See The Solution Submitted by Math Man    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution I think I have it now! | Comment 10 of 11 |
I'm going to use mostly the same logic (and the same shorthand/notation) as before, look at my original "Solution" for a total of 20 people for reference if needed.

Again, we take some A from the 18, he's got at least nine friends or at least nine strangers.  Without loss of generality we suppose he has nine friends.  And again, if there is a trio among those nine, then that trio combines with A to form our quartet.

Otherwise, observe only this group of nine which must contain no trio of friends.  Call one of them B and consider three cases:

1) If B has at least four friends, then those friends must be a quartet of strangers, as before, since there can be no trio of friends here.

2) If B has at least six strangers, then that group of six strangers contains a trio of strangers (again, by the original "Mutual Friendly" and since there can be no trio of friends), and B and that trio of strangers form a quartet.

3) Here's where we need to get clever(er)....if *neither* of those is the case, then there is only one possibility, since there are eight people besides B: B must have exactly 3 friends and 5 strangers, since he does not have at least 6 strangers and he does not have at least 4 friends.  But what we have said applies in general to any person taken from the group of 9.  Therefore, if no one person from the group of 9 fulfills the at-least-6-strangers-case or the at-least-4-friends case, then *every* person among these 9 has exactly 3 friends among them.  But this is impossible!  3 friends for each of 9 people would mean a total of 3 * 9 = 27 "friend connections" where a "friend connection" is a single person's existence in a single friendship.  27 friend connections would mean 13 1/2 friendships, which is impossible because it is not an integer.  Therefore one of the earlier cases must have been fulfilled, and the group of 18 contains a quartet, QED!

  Posted by Caleb on 2012-08-07 13:08:15
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 (2)
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