Six People at a Party: Three Mutual Friends or Three Mutual Strangers
Six people arrive at a party. For any two of them, either they had met before the party or they had not (the relation is symmetric: if A has met B then B has met A).
Prove that there must be either three people who had all met each other before the party, or three people no two of whom had met before. Also explain why the same claim can fail for five people.
Hints
- Fix one person and look at their relationships with the other five. Each relationship is one of two types, so by pigeonhole at least three of the five share the same type.
- Say person P has met A, B and C. Look at the three pairs among A, B, C. If any pair has met, that pair plus P forms a trio of mutual acquaintances.
- If none of the pairs among A, B, C has met, then A, B, C are three mutual strangers. The case where P has not met A, B, C is symmetric.
Worked Solution
How to Think About It: The two-valued relation on six people suggests a 2-coloured complete graph $K_6$. We want a monochromatic triangle. Pigeonhole on one vertex's five edges gives three edges of the same colour, and a short case split finishes the argument.
Approach: Pick any person, apply pigeonhole to their five relationships, then split into cases.
Formal Solution:
*Step 1 -- Setup.* Represent the six people as the vertices of the complete graph $K_6$. Colour the edge between two people red if they had met before and blue if they had not. Every one of the $\binom{6}{2} = 15$ edges gets exactly one colour. We must show there is a red triangle or a blue triangle.
*Step 2 -- Pigeonhole at one vertex.* Choose any person $P$. Five edges leave $P$, each red or blue. By the pigeonhole principle, at least $\lceil 5/2 \rceil = 3$ of them have the same colour. Without loss of generality (swap the colour names otherwise), $P$ is joined by red edges to three people $A$, $B$, $C$.
*Step 3 -- Case split on the triangle $ABC$.*
- If any of the edges $AB$, $BC$, $CA$ is red, say $AB$, then $P$, $A$, $B$ are pairwise joined by red edges: three people who had all met before.
- Otherwise all three edges $AB$, $BC$, $CA$ are blue, and $A$, $B$, $C$ are three mutual strangers.
Either way a monochromatic triangle exists, which proves the claim. (A brute-force check of all $2^{15} = 32768$ colourings of $K_6$ confirms that every one contains a monochromatic triangle.)
*Step 4 -- Five people are not enough.* Arrange five people in a circle and let each person have met exactly their two neighbours (a red 5-cycle); the remaining five pairs (the pentagram) are blue. Any three people include two non-adjacent ones in the cycle, so no three are mutual acquaintances, and any three include two adjacent ones, so no three are mutual strangers. Thus the claim fails for five people, and six is the smallest number that forces it: $R(3,3) = 6$.
Answer: Among any six people there are always three mutual acquaintances or three mutual strangers: pick one person, three of their five relationships share a type by pigeonhole, and those three people either contain a pair of the same type (completing a trio with the chosen person) or form a trio of the opposite type. Five people do not suffice, as a 5-cycle of acquaintances shows.
Intuition
Colour each of the 15 pairs red (met) or blue (strangers); the claim is that every 2-colouring of the complete graph on 6 vertices contains a single-colour triangle, which is the statement that the Ramsey number $R(3,3) = 6$. The proof is pigeonhole applied twice: one person has at least three edges of the same colour, and those three neighbours either complete a triangle with that person or form a triangle of the other colour among themselves. Ramsey-type reasoning shows up whenever you argue that structure is unavoidable in large enough systems, and the pigeonhole-then-case-split pattern is the standard template for such proofs.