Tutorial

*If there are n+1 pigeons roosting in n pigeonholes, then at least one pigeonhole is occupied by at least two pigeons.*

As devilishly simple as the statement sounds, it turns out the the **pigeonhole principle** can be used to solve a wide array of problems. This is the basic idea behind the children's game musical chairs: there is always one less chair than there are players, so that every turn, one player is cast out.

Consider a pentagon sitting in the plane. If its center is the origin, and no vertex sits on an axis, then at least two vertices sit in the same quadrant.

Why? Because there are four quadrants and five points, and since none of the vertices are allowed to be on the quadrant boundaries (the y-axis or the x-axis) then two of them have to be in one quadrant.

In this video we see two examples of how the pigeonhole principle may be applied.