Six People at a Party

  • Hard
  • Arrangement puzzles
  • Tests: Forcing a structure out of pure size

The puzzle

Any two people either know each other or do not. Show that among any six people there must be three who all know one another, or three who are mutual strangers.

And show that five people are not enough to force it.

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

Pick one person. They have five relationships, each of two kinds.

Hint 2

Five things in two boxes means one box holds at least three.

Show the answer Hide the answer

True for six, false for five. Pick anybody: of their five relationships, at least three are of one kind, and those three people settle it.

How to get there

Take any person, A. A has five relationships, each either "knows" or "does not". By the pigeonhole principle at least three fall into one category - at least (5+1)/2 = 3.

Say A knows B, C and D. If any two of B, C, D know each other, they and A form a mutual triple. If none of them do, then B, C and D are three mutual strangers. Either way the claim holds. The argument is identical with "knows" and "does not" swapped.

Five is not enough: seat five people in a circle, each knowing only their two neighbours. No three are mutual acquaintances and no three are mutual strangers. So 6 is exactly the threshold - written R(3,3) = 6. R(4,4) is 18, and R(5,5) is still unknown, somewhere between 43 and 48.

The technique worth keeping

The pigeonhole principle forces structure from size alone. Fix one element, split its relationships into categories, and the majority category is large enough to argue about - then check both outcomes within it.