How to use the Pigeonhole Principle to solve combinatorial problems?

**General strategy:** Identify what you're putting (pigeons) and where you're putting them (holes). The holes should be categories such that if two items share a hole, the desired property holds. **Problem 1: 5 points in a unit square.** Divide the square into 4 smaller squares of side $1/2$. By the pigeonhole principle, at least one small square contains at least $\lceil 5/4 \rceil = 2$ points. The maximum distance between any two points in a $1/2 \times 1/2$ square is the diagonal: $\sqrt{(1/2)^2 + (1/2)^2} = \sqrt{2}/4 = 1/\sqrt{2}$. So the two points in the same small square are at most $1/\sqrt{2}$ apart. **Problem 2: 13 integers, difference divisible by 12.** When divided by 12, any integer leaves a remainder $0, 1, \ldots, 11$ (12 possible remainders). With 13 integers, by pigeonhole, at least two have the same remainder. Their difference is divisible by 12. **Problem 3: Subset of size 6 from $\{1, \ldots, 10\}$ contains two summing to 11.** Create 5 "pairs": $(1,10), (2,9), (3,8), (4,7), (5,6)$. Each pair sums to 11. By picking 6 numbers from $\{1, \ldots, 10\}$, by pigeonhole, at least two must come from the same pair, and those two sum to 11. **Key insight:** The pigeonholes are often not obvious — look for the property you want to prove and work backward to create appropriate categories.