rec.puzzles Archive

Any group of 6 or more contains either 3 mutual friends or 3 mutual strangers.

logic/friends

Problem

Any group of 6 or more contains either 3 mutual friends or 3 mutual strangers.
Prove it.
Show solution
Take a person X.  Of the five other people, there must either be at least three
acquaintances of X or at least three strangers of X.  Assume wlog that X has
three strangers A,B,C.  Unless A,B,C is the required triad of acquaintances,
they must include a pair of strangers, wlog A,B.  Then X,A,B is the required
triad of strangers, QED.