Discrete Math · Undergraduate

The Pigeonhole Principle

Quick answer

If n + 1 or more objects go into n boxes, at least one box holds two or more. More generally, if N objects go into k boxes, some box holds at least ⌈N/k⌉ of them. The principle proves that something must happen without saying where: among 13 people two share a birth month, any 6 integers include two with the same remainder mod 5, and among 5 points in a unit square two lie within √2/2 of each other. The skill is choosing what the boxes are.

What you'll learn

  • State the pigeonhole principle and its general form
  • Choose objects and boxes to fit a problem
  • Find the smallest number that guarantees an outcome
  • Use the principle in number theory and geometry proofs

More pigeons than holes

If 1010 pigeons fly into 99 holes, some hole gets at least two pigeons. That is the whole pigeonhole principle:

If more than nn objects are placed into nn boxes, some box contains at least two objects.

It sounds almost too plain to be useful, but it proves things that are hard to see any other way, because it guarantees that something happens without needing to find where.

General form. If NN objects go into kk boxes, some box holds at least ⌈Nk⌉\left\lceil \tfrac{N}{k} \right\rceil objects, where ⌈ ⌉\lceil\ \rceil rounds up.

Why it must be true

Suppose every box held at most one object. Then nn boxes would hold at most nn objects in total, fewer than we placed. The total cannot fit unless some box takes more than its share. The general form is the same argument: if every box held fewer than Nk\tfrac{N}{k}, the boxes together would hold fewer than NN. It is a proof by contradiction, in one line.

Worked examples

Common mistakes

Practice problems

  1. How many people guarantee that two share a birthday, ignoring leap years?

    Answer

    366366

    Full solution

    There are 365365 possible birthdays, so 366366 people are needed for a guaranteed match.

  2. A bag has red, green, blue and yellow marbles. How many must you draw to be sure of two of the same color?

    Answer

    55

    Full solution

    Four colors are the boxes; four marbles could all differ.

  3. How many must you draw from the bag in Exercise 2 to be sure of three of the same color?

    Answer

    99

    Full solution

    Eight marbles could be two of each color. The ninth makes three of one color.

  4. Show that among any 1111 integers, two have the same last digit.

    Answer

    There are only 1010 possible last digits.

    Full solution

    The boxes are the digits 00 to 99, and 11>1011 > 10.

  5. 5050 students take a test graded A to F, with 55 possible grades. At least how many students get the same grade?

    Answer

    1010

    Full solution

    ⌈505⌉=10\left\lceil \tfrac{50}{5} \right\rceil = 10.

  6. Show that in any group of n≥2n \ge 2 people, two have the same number of friends in the group.

    Answer

    The possible counts are 00 to n−1n - 1, but 00 and n−1n - 1 cannot both occur, leaving n−1n - 1 boxes for nn people.

    Full solution

    If someone is friends with everyone, no one has 00 friends, and the reverse. So only n−1n - 1 values are possible.

  7. How many integers must be chosen from 11 to 2020 to guarantee two whose sum is 2121?

    Answer

    1111

    Full solution

    The boxes are the 1010 pairs {1,20},{2,19},…,{10,11}\{1, 20\}, \{2, 19\}, \ldots, \{10, 11\}. Ten numbers could take one from each pair; the eleventh completes a pair.

  8. A student says 1212 people guarantee a shared birth month. Correct the claim.

    Answer

    Twelve people can be born in twelve different months; it takes 1313.

    Full solution

    The principle needs more objects than boxes.

Frequently asked questions

What is the pigeonhole principle?

If more than n objects are placed in n boxes, at least one box contains two or more objects.

What is the generalized pigeonhole principle?

If N objects are placed in k boxes, at least one box contains at least ⌈N/k⌉ objects, where ⌈ ⌉ rounds up.

How do you choose the boxes?

Make the boxes the categories that the conclusion talks about: months for birthdays, remainders for divisibility, small regions for distances.

Does the principle say which box has two objects?

No. It guarantees that some box does, without identifying it. That is why it proves existence statements.

How many socks guarantee a matching pair from three colors?

Four. Three socks could all differ, but a fourth must match one of the three colors.

What to learn next