How many people?

What this combinatorial puzzle tests

This is an easy-to-medium puzzle that probes reasoning about graph theory and the pigeonhole principle. It asks you to find the minimum group size that guarantees a specific structure must exist, regardless of how relationships are arranged.

The question is a classic application of Ramsey theory: given a set of people and a binary relationship (know / don't know), you must determine when you can always find three people who form either a "clique" (all know each other) or an "independent set" (all are mutual strangers). The key insight is that as the group grows, it becomes mathematically impossible to avoid one of these patterns.

• Graph coloring and vertex connectivity
• Exhaustive case analysis and proof by contradiction
• Ramsey numbers and combinatorial guarantees