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.

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