The Pigeonhole Principle

definitions
discrete-math
counting

If more objects are put into boxes than there are boxes, some box gets two. That is the pigeonhole principle, and it proves that something must exist (two chosen numbers that are consecutive, two subsets with the same sum, two vertices with the same degree) without finding it. This note states the principle, gives its form for functions and its generalised form, explains how to choose the pigeons and the holes, and works through the standard arguments. Counting the pigeons and the holes uses counting-principles and counting-selections. First met in 2026-10-22-pigeonhole-principle-introduction-to-graph-theory.

The principle

The pigeonhole principle. If \(n\) pigeons fly into \(m\) pigeonholes and \(n > m\), then at least one pigeonhole contains two or more pigeons.

Proof. Suppose every hole contains at most one pigeon. Then the \(m\) holes contain at most \(m\) pigeons in total. But there are \(n > m\) pigeons, a contradiction. So some hole contains at least two. \(\square\)

Three things about it:

  • It says some hole has two, not which hole. A pigeonhole proof is an existence proof.
  • It needs \(n > m\) strictly. Nine pigeons in nine holes can sit one per hole.
  • It says nothing when \(n \le m\). Then two pigeons might share a hole or might not, and the principle gives no information either way.

Figure 1: Ten pigeons, numbered, in nine holes. However the ten are placed, the nine holes cannot each hold at most one, since that accounts for only nine pigeons. Here pigeons 3 and 10 share the top-right hole. A different placement would make a different pair share a hole, but some hole always holds two.

As a statement about functions

Putting each pigeon in a hole is a function from the set of pigeons to the set of holes, and “two pigeons in one hole” says two inputs have the same output. So:

Pigeonhole principle, function form. If \(X\) and \(Y\) are finite sets with \(|X| > |Y|\), then no function \(f : X \to Y\) is one-to-one: there are \(x_1 \neq x_2\) in \(X\) with \(f(x_1) = f(x_2)\).

This is the first of the facts about finite sets in cardinality, and “one-to-one” is defined in one-to-one-and-onto-functions. Read this way, a pigeonhole proof has three parts: say what \(X\) is (the pigeons), say what \(Y\) is (the holes), and say what \(f\) does (which hole each pigeon goes to). Then count both sets.

Figure 2: The function form on a small case: six numbers chosen from 1 to 10. \(X\) is the set of chosen numbers, the pigeons. \(Y\) is the set of five pairs of neighbours \({1, 2}, {3, 4}, \dots, {9, 10}\), the holes. \(f\) sends each chosen number to the pair it lies in. Since \(|X| = 6 > 5 = |Y|\), \(f\) cannot be one-to-one, so two chosen numbers, here 9 and 10, go to the same pair, and two numbers in one pair are consecutive. A different choice of six moves the collision to a different pair but cannot avoid one.

The generalised principle

Sometimes two in a hole is not enough, and the argument needs three, or more. The same proof gives the standard generalisation:

Generalised pigeonhole principle. If \(n\) pigeons fly into \(m\) pigeonholes and \(n > k \cdot m\), then at least one pigeonhole contains \(k + 1\) or more pigeons.

Proof. If every hole contained at most \(k\) pigeons, there would be at most \(k \cdot m\) pigeons, and there are more. \(\square\)

With \(k = 1\) it is the ordinary principle. An equivalent way to say it: some hole contains at least \(\lceil n/m \rceil\) pigeons, the average rounded up. If \(n > k \cdot m\) then \(n/m > k\), so \(\lceil n/m \rceil \ge k + 1\).

Example: birth months. Among any 25 people, at least 3 were born in the same month. The people are the pigeons and the 12 months are the holes. \(25 > 2 \cdot 12\), so some month has at least \(\lceil 25/12 \rceil = 3\) of them. 24 people are not enough: two born in each month have no three in the same month.

Figure 3: The generalised principle with 25 people and 12 months. Up to 24 people can be spread so that no month has more than 2, two in every month. That fills every month to its limit, so the 25th person, in red, must make some month’s count 3. In general, more than \(k \cdot m\) pigeons in \(m\) holes force some hole to hold \(k + 1\).

Choosing the pigeons and the holes

The principle is easy. The work is in choosing what the pigeons and the holes are.

  • The pigeons are usually the objects the problem chooses: the numbers selected, the subsets, the people, the vertices.
  • The holes must cover everything. Every pigeon has to land in some hole, and in exactly one. When the pigeons are elements of a set, the holes are a partition of that set (sets-and-set-notation).
  • Two pigeons in one hole must give exactly what is wanted. This is what decides the holes. To force two consecutive numbers, make the holes pairs of consecutive numbers. To force a sum of 101, make the holes pairs that sum to 101. To force a common remainder, make the holes the remainders.
  • Count both. The argument works only if there are more pigeons than holes. If the first choice of holes gives too many, look for a way to merge them, as in equal degrees, or a better bound, as in subset sums.

Many problems ask for the largest (or smallest) number with some property. The answer always has two halves:

  1. An example. Show that the number can be reached, by writing down a selection of that size.
  2. A pigeonhole argument. Show that one more forces the property to fail.

The pigeonhole half on its own proves only a bound. Without the example, the true answer might be smaller.

Worked: no two consecutive

What is the largest number of integers that can be chosen from \(\{1, 2, \dots, 100\}\) with no two consecutive?

50. The odd numbers \(1, 3, \dots, 99\) are 50 numbers with no two consecutive. For the bound, the holes are the 50 pairs \(\{1, 2\}, \{3, 4\}, \dots, \{99, 100\}\). Each pair is two consecutive numbers, so a good selection takes at most one from each pair. Choosing 51 or more puts two in some pair, and they are consecutive.

In general, from \(\{1, 2, \dots, 2m\}\) the largest selection with no two consecutive has \(m\) numbers. The holes are pairs of neighbours, \(\{2i - 1, 2i\}\).

The full question, with the wrong options, is in 2026-10-22-pigeonhole-principle-introduction-to-graph-theory.

Worked: a pair with a given sum

Prove that if 51 numbers are chosen from \(\{1, 2, \dots, 100\}\), then two of them sum to 101.

The holes are the 50 pairs \(P_i = \{i, 101 - i\}\) for \(i = 1, \dots, 50\):

\[\{1, 100\},\ \{2, 99\},\ \dots,\ \{50, 51\}.\]

Each number from 1 to 100 is in exactly one of them. 51 chosen numbers in 50 pairs put two in one pair \(P_i\), and \(i + (101 - i) = 101\).

The same holes answer any question of this shape. From \(\{1, 2, \dots, 2m\}\), any \(m + 1\) numbers include two that sum to \(2m + 1\), using the pairs \(\{i, 2m + 1 - i\}\). And \(m\) numbers are not enough: \(1, 2, \dots, m\) have no two summing to more than \(2m - 1\).

The drawing of these pairs is in 2026-10-22-pigeonhole-principle-introduction-to-graph-theory.

Worked: no three consecutive

What is the largest number of integers that can be chosen from \(\{1, 2, \dots, 60\}\) with no three consecutive?

40.

  • Example. Choose everything except the multiples of 3, the numbers congruent to 1 or 2 mod 3. Any three consecutive integers include a multiple of 3, so no three chosen numbers are consecutive. That is \(60 \cdot \frac23 = 40\) numbers.
  • Bound. The holes are the 20 blocks \(\{1, 2, 3\}, \{4, 5, 6\}, \dots, \{58, 59, 60\}\). A block with all three chosen is three consecutive numbers. With 41 numbers in 20 blocks, \(41 > 2 \cdot 20\), so by the generalised principle some block holds \(\lceil 41/20 \rceil = 3\) chosen numbers.

This is the generalised principle with \(k = 2\): the property needs three in one hole, not two.

Worked: two subsets with the same sum

Show that if \(A\) is any 6-element subset of \(\{1, 2, \dots, 12\}\), then \(A\) has distinct subsets \(X\) and \(Y\) with the same sum.

  • Pigeons: the subsets of \(A\). There are \(2^6 = 64\) of them, including \(\emptyset\) and \(A\) (sets-and-set-notation, binomial-coefficients).
  • Holes: the possible sums. Every element is positive, so a subset’s sum is between 0 (for \(\emptyset\)) and the sum of all of \(A\). Six different integers from 1 to 12 add up to at most \(7 + 8 + 9 + 10 + 11 + 12 = 57\). So there are at most 58 possible sums, \(0, 1, \dots, 57\).
  • Conclusion. \(64 > 58\), so two different subsets have the same sum.

The pigeons here are not the elements of \(A\) but its subsets, which are far more numerous than the possible sums: the number of subsets doubles with each extra element, while the largest possible sum grows by at most 12. That gap is what makes the argument work. The bound on the sum has to be the tight one. Using the sum of all of \(\{1, \dots, 12\}\), 78, as the bound gives 79 holes for 64 pigeons, and the argument fails.

Leaving out \(\emptyset\) works too: 63 non-empty subsets and 57 possible sums, \(1, \dots, 57\). Either way, count the pigeons and the holes over the same collection.

The figure for \(A = \{2, 4, 6, 8, 10, 12\}\) is in 2026-10-22-pigeonhole-principle-introduction-to-graph-theory.

Worked: two with the same remainder

Show that among any \(n + 1\) integers there are two whose difference is divisible by \(n\).

The holes are the \(n\) possible remainders on division by \(n\), \(0, 1, \dots, n - 1\). Each integer has exactly one, by the quotient-remainder theorem (modular-arithmetic). \(n + 1\) integers and \(n\) remainders put two integers \(a\) and \(b\) in one hole. They have the same remainder \(r\), so \(a = nq_1 + r\) and \(b = nq_2 + r\), and \(a - b = n(q_1 - q_2)\) is divisible by \(n\).

\(n\) integers are not enough: \(0, 1, \dots, n - 1\) have all their differences between \(-(n-1)\) and \(n - 1\), and none of those but 0 is divisible by \(n\).

For example, among any 4 integers, two differ by a multiple of 3. From \(\{1, 2, \dots, 100\}\) that means 4 picks guarantee such a pair, while the 3 picks \(1, 2, 3\) do not.

Worked: two vertices of equal degree

Show that in any simple graph with at least two vertices, two vertices have the same degree.

Graphs, simple graphs and degree are in graphs. Said with people: in any group of two or more people, two of them have the same number of friends within the group, if friendship goes both ways.

Let the graph have \(n \ge 2\) vertices. In a simple graph a vertex is joined to at most each of the other \(n - 1\) vertices once, so every degree is one of the \(n\) values \(0, 1, \dots, n - 1\). That is \(n\) pigeons and \(n\) holes, which is not enough. The extra step is that 0 and \(n - 1\) cannot both occur. A vertex of degree \(n - 1\) is joined to every other vertex, so no vertex has degree 0. So the degrees all lie in \(\{0, 1, \dots, n - 2\}\) or all lie in \(\{1, 2, \dots, n - 1\}\). Either way there are only \(n - 1\) holes for \(n\) vertices, and two vertices share a degree.

This is the problem about five friends in 2026-07-27-welcome-and-intro-problems.

Figure 4: Why two vertices of a simple graph on 5 vertices have equal degree. The possible degrees are 0 to 4, five holes for five vertices, which forces nothing. But a vertex of degree 4 is joined to all four others, left, so each of them has degree at least 1 and none can have degree 0. So either no vertex has degree 4, top right, or none has degree 0, bottom right. In both cases only four degrees are available for five vertices, and two vertices share one.

Common mistakes

  • Using it with too few pigeons. If the number of pigeons is not more than the number of holes, the principle proves nothing. It does not make the statement false either: every 5-element subset of \(\{1, \dots, 12\}\) also has two subsets with equal sums, but with 32 subsets and up to 51 possible sums the pigeonhole argument cannot show it.
  • Holes that overlap. Pairs like \(\{1, 2\}, \{2, 3\}, \{3, 4\}, \dots\) share numbers, so a pigeon is in two holes and the count no longer works. The holes must split the set: every pigeon in exactly one hole.
  • Holes that don’t force the property. Two pigeons in one hole must give what is wanted. Pairs \(\{1, 2\}, \{3, 4\}, \dots\) force two consecutive numbers but not two that sum to 101.
  • Only half an answer. For “what is the largest”, the pigeonhole bound needs an example of that size as well, and the example needs the bound.
  • Off by one in the generalised form. \(k \cdot m\) pigeons can sit \(k\) to a hole. It takes \(k \cdot m + 1\) to force \(k + 1\) in one hole: 24 people can have no three sharing a birth month, 25 cannot.
  • A loose bound on the holes. Counting more holes than can actually be used (sums up to 78 rather than 57, or degrees 0 to \(n - 1\) when 0 and \(n - 1\) exclude each other) can make an argument that should work fail.
  • Claiming to know which hole. The principle says some hole has two pigeons. It does not say which.

See also