Three friends or three strangers among six people
Question
Six people are at a party; any two of them have either met before or not. Prove that you can always find three who have all met each other, or three of whom no two have met.
Short answer
Pigeonhole on one person. Pick anyone, . Of the other five, at least three share the same relation with , say all have met . If any two of those three have met, they form a trio of acquaintances with ; if not, those three are mutual strangers. The other case is symmetric.
Adapted from Zhou, A Practical Guide to Quantitative Finance Interviews, sec. 2.6 The Pigeon Hole Principle, 'Have we met before?', p.20; question and answer rewritten by SelfMadeQuant.com.
See the hint and the full worked solution in the question bank (free account).
Open the worked solution