Skip to content

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, PP. Of the other five, at least three share the same relation with PP, say all have met PP. If any two of those three have met, they form a trio of acquaintances with PP; 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