Pigeons in holes principle

# Pigeonhole principle

In mathematics, the pigeonhole principle states that if {isplaystyle n}n items are put into {isplaystyle m}m containers, with {isplaystyle n>m}n>m, then at least one container must contain more than one item.[1] In layman’s terms, if you have more “objects” than you have “holes,” at least one hole must have multiple objects in it. A real-life example could be, “if you have three gloves, then you have at least two right-hand gloves, or at least two left-hand gloves,” because you have 3 objects, but only two categories to put them into (right or left). This seemingly obvious statement, a type of counting argument, can be used to demonstrate possibly unexpected results. For example, if you know that the population of London is greater (by at least two people) than the maximum number of hairs that can be present on a human’s head, then the pigeonhole principle requires that there must be (at least) two people in London who have the same number of hairs on their heads.

Examples

Sock-picking Assume a drawer contains a mixture of black socks and blue socks, each of which can be worn on either foot, and that you are pulling a number of socks from the drawer without looking. What is the minimum number of pulled socks required to guarantee a pair of the same color? Using the pigeonhole principle, to have at least one pair of the same color (m = 2 holes, one per color) using one pigeonhole per color, you need to pull only three socks from the drawer (n = 3 items). Either you have three of one color, or you have two of one color and one of the other.

Hand-shaking If there are n people who can shake hands with one another (where n > 1), the pigeonhole principle shows that there is always a pair of people who will shake hands with the same number of people. In this application of the principle, the ‘hole’ to which a person is assigned is the number of hands shaken by that person. Since each person shakes hands with some number of people from 0 to n − 1, there are n possible holes. On the other hand, either the ‘0’ hole or the ‘n − 1’ hole or both must be empty, for it is impossible (if n > 1) for some person to shake hands with everybody else while some person shakes hands with nobody. This leaves n people to be placed into at most n − 1 non-empty holes, so that the principle applies.

The birthday problem The birthday problem asks, for a set of n randomly chosen people, what is the probability that some pair of them will have the same birthday? By the pigeonhole principle, if there are 367 people in the room, we know that there is at least one pair who share the same birthday, as there are only 366 possible birthdays to choose from (including February 29, if present). The birthday “paradox” refers to the result that even if the group is as small as 23 individuals, the probability that there is a pair of people with the same birthday is still above 50%. While at first glance this may seem surprising, it intuitively makes sense when considering that a comparison will actually be made between every possible pair of people rather than fixing one individual and comparing them solely to the rest of the group.

• 2021 18
• 2020 29
• 2019 8
• 2018 41
• 2017 40
• 2016 54
• 2007 1