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