### Free Educational Resources

• > Mathematics
• > Combinatorics Principles: Pigeonhole Principle
+

# Combinatorics Principles: Pigeonhole Principle

(4)
• (1)
• (2)
• (0)
• (0)
• (1)
Author: c o
##### Description:

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".

(more)

Sophia’s self-paced online courses are a great way to save time and money as you earn credits eligible for transfer to many different colleges and universities.*

No credit card required

28 Sophia partners guarantee credit transfer.

281 Institutions have accepted or given pre-approval for credit transfer.

* The American Council on Education's College Credit Recommendation Service (ACE Credit®) has evaluated and recommended college credit for 25 of Sophia’s online courses. Many different colleges and universities consider ACE CREDIT recommendations in determining the applicability to their course and degree programs.

Tutorial

# Definition

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.

# Example

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.