Probability & Combinatorics
Intermediate

Pigeonhole Principle

If n items go into k containers, some container holds at least this many.

Formula

⌈n/k⌉\lceil n/k \rceil

Variables

nItems
kContainers

Example

10 socks, 3 colors: some color has ≥ 4

Did You Know?

A simple idea that proves surprisingly deep results.

countingcombinatorics