Basics 0/129

Numbers and arithmetic · 4 of 4 Advanced

Pigeonhole principle

Use the pigeonhole principle to show that a value must repeat, to bound how long a loop can run before it does, and to find the repeat.

2,222 words · 10 min read

Part 1 of 5 Pigeonhole principle

More items than boxes

Among any 13 people, at least two have their birthday in the same month. Nobody has to be asked: there are 12 months, and 13 people cannot all have different ones. The pigeonhole principle is this argument in general, with items in place of people and boxes in place of months.

The argument says that two people share a month. It does not say which month or which two people. Some problems only need to know that a repeat exists. When a problem asks for the repeat itself, we still have to search for it, and the principle can tell us how long the search takes or where to look.

Definition

If m+1m + 1 or more items are placed in mm boxes, at least one box holds two or more items.

The principle needs strictly more items than boxes. Twelve people can have twelve different birth months, and only the thirteenth forces a shared one.

The count scales up as well. With more than k×mk \times m items in mm boxes, some box holds more than kk. Among 25 people, some month has at least three birthdays, because two per month accounts for only 24 people.