+
Combinatorics Principles: Pigeonhole Principle

Combinatorics Principles: Pigeonhole Principle

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)
See More

Try Our College Algebra Course. For FREE.

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

Begin Free Trial
No credit card required

25 Sophia partners guarantee credit transfer.

221 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 20 of Sophia’s online courses. More than 2,000 colleges and universities consider ACE CREDIT recommendations in determining the applicability to their course and degree programs.

Tutorial

Introduction

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.