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.
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
No Subject
