DSAverse

Initializing Sorting Algorithms...

Sorting

Trees

Graphs

Preparing interactive visualizations...

Back to Combinatorics

The Pigeonhole Principle

Put more pigeons than holes and two must share. Obvious — and yet it proves that something exists without ever finding it, from matching socks to people who shook the same number of hands.

Step 1 of 15

Speed

Five pigeonholes. Pigeons arrive one at a time, and each is as kind as possible: it takes the emptiest hole, so collisions are put off as long as they can be.

\text{fullest hole} \ge \left\lceil \frac{n}{m} \right\rceil = \left\lceil \frac{0}{5} \right\rceil = \mathbf{0}\qquad \text{since } 5 \times 0 = 0 < 0

n (pigeons)0Adds to the emptiest hole, removes from the fullestm (holes)5

The Pigeonhole Principle

Put more pigeons than holes and two must share. Obvious — and yet it proves that something exists without ever finding it, from matching socks to people who shook the same number of hands.

Step 1 of 15

Speed

Five pigeonholes. Pigeons arrive one at a time, and each is as kind as possible: it takes the emptiest hole, so collisions are put off as long as they can be.

\text{fullest hole} \ge \left\lceil \frac{n}{m} \right\rceil = \left\lceil \frac{0}{5} \right\rceil = \mathbf{0}\qquad \text{since } 5 \times 0 = 0 < 0

n (pigeons)0Adds to the emptiest hole, removes from the fullestm (holes)5

DSAverse

The Pigeonhole Principle

See also

The Pigeonhole Principle

See also