Pigeonhole Principle Explained with Worked Examples

If items are put into boxes, some box contains at least items. In particular, if , some box holds two or more.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

  • counting
  • ceiling function
  • division with remainder

What Pigeonhole principle means

Among 13 people at least two share a birth month (). If 100 items are placed in 7 boxes, some box has at least of them. Choosing 51 numbers from 1 to 100, two must be consecutive: pair the numbers as , 50 boxes, and . A drawer of black and white socks needs only 3 socks to guarantee a matching pair (, ). The ceiling function is the rounding up of division with remainder.

The proof is by contradiction: if every box held fewer than items, the total would be less than . The principle is non-constructive: it proves that a box exists without saying which one. It is the key step in the Ramsey argument (Ramsey numbers: a vertex in has 5 edges in 2 colours, so 3 share a colour) and bounds in coding theory (the Singleton bound).

Pigeonhole arguments prove existence results in number theory (two of any integers have the same remainder modulo , see congruences) and graph theory (two vertices of equal degree, using the handshaking lemma). The average argument behind it is the same as the first moment method.

What is it used for?

If there are more items than boxes, some box must hold more than one item.

How to use pigeonhole principle

  1. Identify the items (pigeons) and the categories (holes).
  2. Compute .
  3. Conclude that some box has at least that many.
  4. Design the boxes cleverly so that two items in one box give the desired property.

Graph

Least number in the fullest of 7 boxes: ⌈n/7⌉ for n items100 items: at least 151020304050607080901000246810121416Least number in the fullest of 7 boxes: ⌈n/7⌉ for n itemsnitems per boxaverage n/7Graph with x from 1 to 100 and y from 0 to 16. Shows the curve average n/7; point 100 items: at least 15 at (100, 14.29).

The fullest box holds at least the average, rounded up.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: birth months

How many of 13 people must share a birth month, at least?

Worked example
Answer
22
  1. Formula

Example 2: 100 items, 7 boxes

What is the least number in the fullest of 7 boxes holding 100 items?

Worked example
Answer
1515
  1. Formula

Example 3: consecutive numbers

Show that 51 numbers chosen from 1–100 include two consecutive ones. How many pairs (boxes)?

Worked example
Answer
50 boxes50\ \text{boxes}
  1. Boxes

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

25 items, 8 boxes

⌈25/8⌉

4.

13 people, 12 months

⌈13/12⌉

2.

100 days into 7 weekdays

⌈100/7⌉

15.

Socks, 2 colours

3 socks guarantee a pair

Boxes + 1.

Word problems

Putting n items in m boxes forces some box to hold at least ⌈n/m⌉ items; if n > m, some box holds two or more.

Boxes

25 items in 8 boxes. Minimum in the fullest box.

  1. ⌈3.125⌉
  2. Check: ✓4

Birthdays

13 people. Guaranteed to share a birth month?

  1. ⌈13/12⌉
  2. Check: 2 ✓2

Weekdays Higher

100 events on 7 weekdays.

  1. ⌈100/7⌉
  2. Check: ✓15

Socks Higher

Two colours: how many socks guarantee a pair?

  1. 2 + 1
  2. Check: ✓3

Common mistakes

Floor instead of ceiling

⌊25/8⌋ = 3 ✗

⌈25/8⌉ = 4 ✓

At least.

Needing equality

exactly n/m ✗

at least ✓

Lower bound.

Wrong box count

forgetting categories ✗

count the boxes ✓

Define them.

Which box

predicts the box ✗

only existence ✓

Not constructive.

Exam tips

  1. ⌈n/m⌉.
  2. Define the boxes.
  3. n > m: a repeat.
  4. Worst case + 1.
  5. Existence only.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. ⌈30/4⌉ Foundation

8

2. ⌈51/50⌉ Foundation

2

3. ⌈100/9⌉ Foundation

12

4. Socks with 5 colours guaranteeing a pair Higher

6

5. ⌈367/366⌉ Higher

2

6. ⌈50/7⌉ Higher

8

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Pigeonhole principle
Some box has ⌈n/m⌉.
Ceiling
Round up.
Boxes
Categories.
Items
Objects placed.
Existence proof
Shows something exists.
Generalised pigeonhole
⌈n/m⌉ version.

Frequently asked questions

What is the pigeonhole principle?

n items in m boxes put ⌈n/m⌉ in some box.

Why a ceiling?

The fullest box has at least the average.

How many socks guarantee a pair of two colours?

3.

Does it tell me which box?

No.

Which page covers Ramsey numbers?

Ramsey numbers.

Which page covers Catalan numbers?

Catalan numbers.

More in Discrete maths and number theory and the formula sheets.