(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?
We use the Pigeon Hole Principle
Pigeon Hole Principle
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.
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.
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 birthday.
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 birthday.
(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?
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 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 same degree.
(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
hands.
Pigeonhole Principle, Strong Form If pigeons are nesting in pigeonholes, then at
least pigeons are nesting in the same pigeonhole.
- Proof
- 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.
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.