The 6-People Theorem

Axiom. Any 2 given distinct people are either mutual acquaintances, or mutual strangers.

 

Theorem. In any group of 6 or more people, there will be at least 3 that are mutual acquaintances, or at least 3 that are mutual strangers.

 

Note that the logical connective is ‘or’ (not ‘and’). The theorem guarantees only ONE of the two possibilities. So, it could be called a ‘double rule of 3’.

 

Note: This is a result in what is called ‘Ramsey Theory’, and is well-known in the literature. It is often stated in terms of people at a party, such as a birthday party: “Among any 6 people at a party, there will be at least 3 that are mutual acquaintances, or at least 3 that are mutual strangers.” (The title of the theorem has various formulations. Search strings likely to return this result include “mutual acquaintances”, “Ramsey number”, and “party problem”.)

 

Proof: Let 6 of the people be denoted by A, B, C, D, E, and F. (Our proof strategy is to use A as a ‘pivot’ to find 3 people who are either mutual acquaintances or mutual strangers.) Then, clearly (or, more formally, by the Pigeonhole Principle), among the 5 other people B, C, D, E, and F, there exist 3, whom we will call U, V, and W, who are either all mutual acquaintances of A, or none of whom is a mutual acquaintance of A.

Case 1. All of U, V, and W are mutual acquaintances of A. Then if any 2 of U, V, and W are mutual acquaintances, then those 2, along with A, are 3 that are mutual acquaintances. If no 2 of U, V, and W are mutual acquaintances, then they are, of course, 3 that are mutual strangers. And so, in this case, the conclusion follows.

Case 2. None of U, V, and W is a mutual acquaintance of A. Then if any 2 of U, V, and W are mutual strangers, then those 2, along with A, are 3 that are mutual strangers. If no 2 of U, V, and W are mutual strangers, then they are, of course, 3 that are mutual acquaintances. And so, in this case, too, the conclusion follows.

Since the above 2 cases are exhaustive, the conclusion follows. Q.E.D.

 

Note that if we consider 3 mutual acquaintances to be a ‘triangle’, and three mutual strangers to be a ‘triad’, then we can state the theorem colloquially as: “Any group of 6 or more people contains either a triangle or a triad.”

 

Note that all that really matters is the symmetrical relationship (as formalized by the axiom). Therefore, making the situation more specific actually makes the concept more difficult, because any specific reference acts as a red herring, tending to derail the succinct analysis of the situation. Indeed, the above formulation is merely the anthropomorphic version of the abstract result that if any complete graph having at least 6 vertices is edged-colored with 2 colors, then there will always exist within it a monochromatic triangle. This of course is equivalent to the statement that if a graph having at least 6 vertices contains no triangle, then its dual does.

 

(end of document)

keywords: Ramsey Theory, self-organization

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s