Pigeonhole Principle Applications

The basic principle, stated precisely

The basic pigeonhole principle says that if n objects are placed into k boxes and n is greater than k, then at least one box contains at least two objects. Phrased in the language of functions, if a function maps a finite set of size n into a finite set of size k with n greater than k, the function cannot be injective, so two distinct inputs must share an output. That reformulation is worth remembering, because many textbook problems are really about showing some map fails to be one-to-one.

Notice what the principle does not give you. It guarantees some box is crowded, but never identifies which box, and never produces the two colliding objects. This is why pigeonhole proofs feel slightly magical: they establish existence without construction, so the conclusion always reads something must repeat, never here is the repeat.

• n objects in k boxes with n greater than k forces some box to hold at least two.
• Equivalently, no injective function exists from a larger finite set to a smaller one.
• The principle proves existence, never location.
• The whole skill is choosing what the objects are and what the boxes are.

The generalized principle

The generalized pigeonhole principle sharpens the conclusion. If n objects are distributed among k boxes, then some box contains at least the ceiling of n divided by k objects. The basic form is the special case where n is greater than k, since then the ceiling of n over k is at least 2. The reason the ceiling appears is a proof by contradiction: if every box held at most the ceiling of n over k minus one objects, the total across all boxes would fall short of n, which is impossible because every object sits in some box.

A concrete instance: among 100 people, some birth month is shared by at least 9 of them. The pigeons are the 100 people, the holes are the 12 months, and the ceiling of 100 divided by 12 is 9 because 100 divided by 12 is a little over 8.3. The bound is also the best you can claim from counting alone, since 100 people can be spread so that no month holds more than 9. Claiming 10 would be wrong, which is the usual error when people round instead of taking the ceiling.

• With n objects in k boxes, some box holds at least the ceiling of n divided by k.
• The proof is by contradiction: otherwise the totals cannot reach n.
• Take the ceiling, never the nearest whole number and never the floor.
• The bound is tight, so do not claim more than the ceiling.

Application: two people with the same number of acquaintances

At a party of n people, with n at least 2, and acquaintance being mutual, two people must know the same number of others present. The pigeons are the n people. The natural holes are the possible acquaintance counts, which range from 0 to n-1, giving n holes for n pigeons, and that is not enough to conclude anything yet.

The extra step is to notice that the holes 0 and n-1 cannot both be occupied. If someone knows nobody, then no one knows everybody; if someone knows everybody, then nobody knows nobody. So at most n-1 of the n possible counts actually occur, and n people distributed among at most n-1 usable holes forces two people into the same hole. Restated in graph language, every finite simple graph on at least two vertices has two vertices of the same degree.

Application: one number dividing another

Choose any n+1 distinct numbers from 1 through 2n. Then one of them divides another. The clever move is the choice of holes. Write every integer uniquely as a power of 2 times an odd number, its odd part. The odd numbers available in the range 1 through 2n are 1, 3, 5, and so on up to 2n-1, and there are exactly n of them, so there are n holes.

The pigeons are the n+1 chosen numbers, each dropped into the hole labelled by its odd part. With n+1 pigeons and n holes, two chosen numbers share the same odd part m, so they are 2^i times m and 2^j times m with i not equal to j. Whichever exponent is smaller gives a number that divides the other, since their quotient is a power of 2. The proof is complete and, characteristically, tells you nothing about which pair it is.

• Pigeons: the n+1 chosen numbers.
• Holes: the n odd numbers 1, 3, ..., 2n-1, used as odd parts.
• Two numbers sharing an odd part differ by a factor that is a power of 2.
• The bound is tight: the n numbers n+1 through 2n contain no such pair.

Application: remainders and geometry

Two of the most reused pigeonhole set-ups are remainders and subdivided regions. For remainders: given any n+1 integers, two of them leave the same remainder on division by n, because the pigeons are the n+1 integers and the holes are the n possible remainders 0 through n-1. Their difference is then divisible by n, which is how many divisibility results get proved in one line. This is also the argument behind the fact that the decimal expansion of a fraction must eventually repeat, since only finitely many remainders can occur during long division.

For geometry: place any 5 points inside a unit square and two of them lie within distance sqrt 2 divided by 2, about 0.707, of each other. Cut the square into four smaller squares of side one half; these are the holes, and the 5 points are the pigeons, so two points land in the same small square. The greatest distance between two points of a square of side one half is its diagonal, which is sqrt 2 over 2, so those two points are at most that far apart.

How to set up a pigeonhole proof

A reliable procedure keeps these proofs honest. Start from the conclusion you want, which will always be of the form two things share some property or some category is crowded. That shared property is your hole. Then the objects you are choosing among are your pigeons. Count both sets explicitly, confirm the pigeons outnumber the holes, or apply the ceiling bound if you need a stronger conclusion, and state the mapping in one sentence.

Two mistakes account for most failed attempts. The first is holes that are not exhaustive, so some pigeon has nowhere to go and the count collapses. The second is quoting a ceiling bound larger than the arithmetic supports. Working through several applications end to end builds the instinct fastest, because the modelling step transfers between problems even when the subject matter does not.

• Name the holes from the property you want two objects to share.
• Name the pigeons as the objects you are choosing among.
• Check the holes are exhaustive, so every pigeon has one.
• Use the ceiling bound when the conclusion needs more than a pair.