Combinatorics Principles: Pigeonhole Principle

Combinatorics Principles: Pigeonhole Principle

Author: c o

To introduce the pigeonhole principle
To see some examples of its application

This packet introduces the learner an idea from combinatorics called the "pigeonhole principle".

See More
Introduction to Psychology

Analyze this:
Our Intro to Psych Course is only $329.

Sophia college courses cost up to 80% less than traditional courses*. Start a free trial now.




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.

Applying The Principle

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