Pigeonhole Principle

Math for CS · Axiom Academy

When there are more items than containers, some container must hold at least two The pigeonhole principle is one of the simplest yet most powerful tools in combinatorics. It proves that something must exist without telling you how to find it. 4 suits (containers). We need N/4 3 , so N 4 2 + 1 = 9 . Draw 9 cards, and at least one suit appears 3 or more times. The pigeonhole principle is the fundamental reason hash collisions are unavoidable . The birthday problem asks: how many people do you need in a room before there's a >50% chance two share a birthday? The probability no two share a birthday: 365 365 365 365

This is the written version of the interactive lesson above. See the full Math for CS course.