A function f: A  B,
where A and B are finite sets and B is smaller than A, cannot be one-to-one:
there must be at least two elements in the domain that have the same image
in the co-domain. |
The pigeonhole principle states that if n pigeons fly into m pigeonholes and n > m, then at least one hole must contain two or more pigeons. The formal definition is as follows:
| A function f: A B,
where A and B are finite sets and B is smaller than A, cannot be one-to-one:
there must be at least two elements in the domain that have the same image
in the co-domain. |
In terms of an arrow diagram for a function from a finite set to a smaller finite set, there must be at least two arrows from the domain that point to the same element of the co-domain, as illustrated below:
Set
A represents pigeons and set B represents
pigeonholes.
A function that demonstrates the pigeonhole principle
Example: If there are 367 people in a room, must there be at least two who were born on the same day? Why?
Solution: The answer is yes. In this example, people in the room represent pigeons and pigeonholes are all possible days in a year. Define a function D from the set of people in the room {x1, x2, ...., x367} to the set of days in a year {Jan 1, Jan 2, ...., Dec 31}, the arrow diagram is shown as below:
Since the number of people in the room is larger than the number of days in a year, the function D is not one-to-one; at least two arrows point to the same day. But that means that at least two people have the same birthday.
Example: Given a set X = {2, 3, 4, 5, 6, 7, 8, 9}:
| a) | If five distinct integers are selected from X, must at least one pair of the integers have a sum of 11? |
| b) | If less than five integers are selected from X, must at least one pair of the integers have a sum of 11? |
Solution:
| a) | The answer is yes. First of all, the set X can be partitioned into
four subsets:
{2, 9}, {3, 8}, {4, 7} and {5, 6} Each subset consists of two integers whose sum is 11. If five integers are selected from X, then by the pigeonhole principle at least two must be from the same subset, and the sum of these two integers is 11. Let the pigeons be the five selected integers, labelled x1, x2, x3, x4 and x5. Let the pigeonholes be the subsets of the partition. Define a function P from pigeons to pigeonholes such that P(x i ) is the subset that contains x i . The following diagram shows the function:
Because there are more pigeons than pigeonholes, at least two pigeons
must go to the same hole. Thus two integers are sent to the same set. It
impiles that two distinct integers in the set have the sum in 11. By the
pigeonhole principle, since P is not one-to-one, there are
integers xi and xj such that P(xi)
= P(xj) but xi |
| b) | The answer is no. In this case, the number of pigeons is less than the number of pigeonholes; therefore, the pigeonhole principle does not apply. For instance, if the numbers 2, 3, 4, and 5 are selected, then the largest sum of any two of these numbers is 9; there are no two integers which will add up to 11. |
Generalized Pigeonhole Principle
A generalization of the pigeonhole principle states that if n pigeons fly into m pigeonholes, and for some positive integer k, n > k * m, then at least one pigeonhole contains k + 1 or more pigeons.
For any function f: A B,
where A and B are finite sets and for any positive integer k, if
n(A) > k * n(B), then there is some b  B
such that b is the image of at least k + 1 distinct elements
of A. |
The following arrow diagram illustrates the case with seven pigeons and three pigeonholes.
In this case, m = 3, n = 7, and k = 2. Since 7 > 3 * 2, at least one pigeonhole contains 2 + 1 (k + 1) or more pigeons. In this example, pigeonhole c contains three pigeons.
Contrapositive Form of the Generalized Pigeonhole Principle
| For any function f: A B,
where A and B are finite sets and for any positive integer k, if
for each b B,
f -1(b) has at most k elements, then
A has at most k * n(B) elements. |
Consider the above example: suppose no more than 2 pigeons go to the same pigeonhole. Then at most 2 pigeons are in each pigeonhole. By the contrapositive form of the generalized pigeonhole principle, this would imply that the total number of pigeons is at most 2 * 3 (since there are 3 pigeonholes) = 6. But this contradicts the fact that there are 7 pigeons. Hence at least one pigeonhole contains 3 pigeons.
Let f : A B'
and g: B C
be functions such that B' B.
Define a new function g o f
: A C
as follows:
(g o f)(a) = g(f(a))
for all a The function g o f is called the composition of f and g. |
The following diagram demonstrates the composition of two functions.
Example: Let f: R
R
be defined by f(x) = x2 + 2, and
let g: R R
be defined by g(x) = 3x + 4.
a) Find the compositions g o f and f o g .
b) Does g o f = f o g? Explain.
There are several properties when using compositions in certain type functions.
Composition with the Identity Function
Composing a Function with Its Inverse
Composition of One-To-One Functions
xj.
By the definition of P, xi and xj
belong to the same subset. Since the elements in each subset add up to
11, xi + xj = 11. 
