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

 Mutually friendly 3 (Posted on 2012-08-05)
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.)
 No Subject | Comment 2 of 11 |

In my solution I have used "enemies" instead of strangers to make it clearer to myself.  I also use the term quartet to refer to a group of 4 people who are all friends with everyone else in the group, or who are all enemies with everyone else in the group.

Let A be one of the 18 people.  There are 17 people besides A.  Therefore A either has at least 9 enemies, or at least 9 friends.  We will consider the case that A has at least 9 friends (without loss of generality), but all arguments would equally apply if you substitute friends with enemies.

We consider the 9 friends A has.  Let B, be a member of this group of friends.  There are thus 8 other people in this group that B can interact with.  Therefore B either has at least 4 friends in this group, or at least 4 enemies. (Or exactly 4 enemies and 4 friends).

We consider the case where B has 4 friends in this group.  If one of these 4 people is friends with another of the 4, then a quartet of friends is formed (with A and B, and the two from the group of 4).  If however none of the 4 people are friends, they are all enemies with each other, forming a quartet of enemies.  Therefore if B has at least 4 friends (or more) then a quartet is formed.

All that is left to consider is the case that B has 4 or more enemies in this group of 9.  Since we have already considered the case of 4 enemies (which overlaps with 4 friends or more friends in the above paragraph), we simply must consider the case that B has 5 or more enemies.

We consider the case that B has 5 enemies in this group of 9 people under consideration.  As a reminder, A is friends with all of these 5 people, and A is friends with B.  If these 5 people are all friends with each other, then there will be some quartets formed.  Therefore, we must consider the case where there is at least 1 enemy between this group of 5.  Let C be a member of the group of 5 and D be another member.  We assume C and D are enemies.  If C is enemies with another member in the group of 5 besides D, a quartet of enemies is formed.  Similarly for D.  Therefore we consider the case when C and D are friends with all other members in the group of 5 (which we will label as E,F and G).  Therefore E and G (or any combinations of E,F,G without loss of generality) must be friends with C and A.  Therefore if E and G are friends with each other, a quartet is formed.  So we consider the case that E and G are enemies.  Thus we next consider the case where E and G are friends with all other members of this group of 5, using the same logic as used for C and D earlier.  However this means that G and F must be friends or another quartet is formed.  We already know that D and G, and D and F are friends, and they are all friends with A, therefore a quartet of friends is thus formed.

Therefore in the case that B has 5 or more enemies, a quartet is also formed.

Therefore there will always be a quartet of enemies or a quartet of friends if there are 18 people in the group.

Edited on August 7, 2012, 6:58 am
 Posted by Chris, PhD on 2012-08-07 06:46:43

 Search: Search body:
Forums (0)