Pigeon Hole Principle

Combinatorics Progress

Completed0/11

0 completed0 in progress

The piegon hole principle and its applications in combinatorics.

Author: Jaden Park

Introduction

The Pigeon Hole Principle states that if you have $n$ items and $m$ containers, where $n > m,$ then one hold must contain more than $1$ item. Now, this might seem useless, but it's pretty useful in the context of olympiad level problems.

In a more formal way,

For any non-negative integers $n$ and $m,$ if $n$ items are distributed into $m$ containers and if $n > m,$ then at least one container must contain at least $\lceil\frac{n}{m}\rceil$ items, where $\lceil\cdot\rceil$ denotes the ceiling function, which rounds a number up to the nearest integer.

Here are some basic examples.

Example

Suppose there are $10$ people at a party. Prove that there are at least two people who have shaken hands with the same number of people at the party.

Solution

In this case, if everyone shakes hands with everyone else, each person can shake hands with $0$ to $9$ people. However, if someone shakes hands with $9$ people, nobody can have $0$ handshakes, and vice versa. Thus, the number of possible handshake counts is actually $9$ (from $0$ to $8$ , or from $1$ to $9$ ), but there are $10$ people, so at least two must have shaken hands with the same number of other guests.

Example

Imagine you have a drawer containing $10$ pairs of socks, each pair a different color. If you choose socks in the dark, how many socks must you pull out to guarantee you have at least one matching pair?

Solution

Since there are $10$ different colors, pulling out $11$ socks guarantees that at least two of them will be of the same color.

Here's another example.

Example

In a round table with $20$ seats, prove that if $21$ guests need to be seated, at least one seat must accommodate two guests.

Solution

We have $20$ seats (pigeonholes) and $21$ guests (pigeons) that need to be seated.

According to the Pigeonhole Principle, if there are more pigeons than pigeonholes, at least one pigeonhole must contain more than one pigeon. Applying this to our scenario:

Pigeonholes (Seats): $20$
Pigeons (Guests): $21$

Since we have $21$ guests and only $20$ seats, at least one seat must accommodate two guests to seat everyone.

Here are some harder problems.

Practice Problem

Suppose a soccer team scores at least one goal in $20$ consecutive games. If it scores a total of $30$ goals in those $20$ games, prove that in some sequence of consecutive games it scores exactly $9$ goals.

Practice Problem

Prove that there exist two powers of $7$ whose difference is divisible by $2003.$

Final Notes and Tips

If it's a proof question, there's a good chance you'll need to reference this principle.

Principle of Inclusion-Exclusion

Recursion

Combinatorics Progress

Counting

Principles

Miscellaneous

Introduction

Example

Solution

Example

Solution

Example

Solution

Practice Problem

Practice Problem

Final Notes and Tips

Introduction

Example

Solution

Example

Solution

Example

Solution

Practice Problem

Practice Problem

Final Notes and Tips