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 have tried extensively and am having an awfully hard time convincing myself that this is true of a group of 18 (I haven't completely given up yet).  But I can prove it given a total of 20 people, as follows:

Shorthand: I will call a set of three mutual friends/strangers a "trio" and a set of four mutual friends/strangers a "quartet."  The claim, then, is to find a quartet of either type.

Let A be one of the 20 people.  Then there are 19 besides A, so A necessarily has at least 10 friends *or* at least 10 strangers, since A's friends and strangers must total 19.  Without loss of generality, suppose A has at least 10 friends (if A has at least 10 strangers, then "friends" and "strangers" can be swapped throughout the rest of the proof, and the same logic will apply).  If any of these 10 friends form a trio of friends, then A and those particular three of his friends form a quartet of friends, and we are done.  On the other hand, if none of these 10 form a trio of friends, then observe these 10 people with no trio of friends existing among them.

This paragraph's logic is confined to that set of 10 people -- that is, what we say here only applies to A's minimal 10 friends, and nobody else.  Let B be one of them.  There are 9 others.  If B is friends with any two of them, then those two cannot be friends of each other, otherwise we have a trio of friends, and we already said there is no trio of friends here.  Thus, any friends of B must be strangers to each other, so if B has any four friends, then those four friends must form a quartet of strangers, and we are done.  Otherwise, B has a maximum of three friends, and therefore a minimum of six strangers (there are 9 others besides B).  Now, observe those six strangers of B; we already know that they cannot contain a trio of friends (or they'd have formed a quartet of friends with A), and we also know that a group of six people, given only two types of relationships, *must* contain a trio of one type or the other; this was proven in the original "Mutually Friendly," but I will provide the proof in my own words after this one as support/reminder.  Therefore, this set of six must contain a trio of strangers, and since these six are all strangers to B, B and those three people form a quartet of strangers, QED.

I have tried to apply the above logic to only 18 people, but I wind up with a group of only 5 in the end, not enough to necessitate a trio and complete the quartet.  Perhaps there is some black magick-logic that I cannot see, to re-involve other people (perhaps even the 10 that I dropped by the way-side at the get-go) and make it happen.  Anyone?

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Following is my proof (a re-hashing of the original "Mutually Friendly") that with six people and only two types of relationships, a trio must be present.

Let A be one of these six.  Since there are only five other people, A either has at least three friends or at least three strangers.  Without loss of generality, suppose A has at least three friends.  Then if *any* two of those are friends, then A and those two form a trio of friends.  Otherwise, all three of those people are strangers, so they form a trio of strangers.  Thus one or the other type of trio is present, QED.

Posted by Caleb on 2012-08-07 04:07:58