You are about to erase your work on this activity. Are you sure you want to do this?
Updated Version Available
There is an updated version of this activity. If you update to the most recent version of this activity, then your current progress on this activity will be erased. Regardless, your record of completion will remain. How would you like to proceed?
Pigeonhole Principle If pigeons are nesting in pigeonholes, then at least two pigeons
are nesting in the same pigeonhole.
A drawer contains blue socks and brown socks. How many socks must be selected to
ensure that there are two of the same color? The two different colors represent the pigeonholes and the socks themselves represent
the pigeons. According to the PHP, if 2+1 = 3 socks are selected, then at least two of
them must be the same color.
(problem 1) A drawer contains red, green and purple socks. How many socks must be
selected to ensure that there are two of the same color?
example 2 How many people are required to ensure that there are two with the same
birthday in the group? The different possible birthdays are the pigeons and the people are the pigeonholes.
There are 366 possible birthdays (including leap day), so by the PHP, 367 people
are required to be in the group to ensure that two of them have the same
(problem 2) Humans are known to have at most 200,00 hairs on their heads. How
large must the population of a city be in order to ensure that at least 2 people have
the same number of hairs on their heads?
If is the number of hairs on a persons head, then
example 3 Use the Pigeonhole Principle to explain why in any graph with vertices
(and no loops), there are always two vertices with the same degree. The degree of a vertex in a graph with vertices is a whole number from 0 to . Hence,
it appears that there are possibilities for the degrees of our vertices. However,
noting that it is impossible for the graph to have both a vertex of degree 0 and a
vertex of degree , we see that there are really only possibilities for the degrees of our
vertex. In other words, there are pigeonholes (the possible vertex degrees) and there
are pigeons (the vertices), so by the PHP, there must be at least two vertices of the
(problem 3) A group of people convenes and they begin shaking hands. Each pair
of people can shake hands 0 or 1 times. Use the Pigeonhole Principle to
explain why there must be at least 2 people who shake the same number of
Pigeonhole Principle, Strong Form If pigeons are nesting in pigeonholes, then at
least pigeons are nesting in the same pigeonhole.
Suppose not. That is, suppose that each of the pigeonholes contains
fewer than pigeons. Then the number of pigeons in each pigeonhole is no more
than and the total number of pigeons is no more than . But this contradicts the
assumption that there are pigeons. Hence, there must be at least one pigeonhole
containing (or more) pigeons.
example 4 The edges of a graph are colored using 4 different colors. How many edges
must the graph have to ensure that there are at least 6 edges of the same
color? The 4 colors represent the pigeonholes and the edges represent the pigeon holes. By
the strong form of the PHP, the graph must contain edges to ensure that there are
of the same color.
(problem 4) The edges of a graph are colored using 5 different colors. How many
edges must the graph have to ensure that there are at least 4 edges of the same