Section 4.3 Principle of Inclusion and Exclusion; Pigeonhole Principle
269
Pigeonhole Principle
The pigeonhole principle acquired its quaint name from the following idea: If
more than k pigeons fly into k pigeonholes, then at least 1 hole will end up with
more than 1 pigeon. Although this seems immediately obvious, we can belabor the
point. Suppose each of the k pigeonholes contains at most 1 pigeon. Then there are
at most k pigeons, not the more-than-k pigeons that supposedly flew in.
Now we’ll state the pigeonhole principle in a less picturesque way.
pRinciple PigeONhOle PRiNCiPle
If more than k items are placed into k bins, then at least 1 bin contains more than
1 item.
By cleverly choosing items and bins, a number of interesting counting problems can be solved (see Example 7 of Chapter 2).
example 43
How many people must be in a room to guarantee that 2 people have last names
that begin with the same initial?
There are 26 letters of the alphabet (bins). If there are 27 people, then there are
27 initials (items) to put into the 26 bins, so at least 1 bin will contain more than
1 last initial.
■
PraCtiCe 29 How many times must a single die be rolled in order to guarantee getting the same value
twice?
example 44
Prove that if 51 positive integers between 1 and 100 are chosen, then one of them
must divide another.
Let the integers be n 1 , …, n 51 . Each integer n i ≥ 2 can be written as a product
of prime numbers (fundamental theorem of arithmetic), every prime number except
2 is odd, and the product of odd numbers is odd. Therefore for each i, n i = 2
k i b i ,
where k i ≥ 0 and b i is an odd number. Furthermore, 1 ≤ b i ≤ 99, and there are 50
odd integers between 1 and 99 inclusive, but there are 51 b values. By the pigeonhole principle, b i = b j for some i and j, so n i = 2
k i b i and n j = 2
kj
b i . If k i ≤ k j , then n i
divides n j ; otherwise, n j divides n i .
S e c t i o n 4 . 3 review
tecHniQueS
• Use the principle of inclusion and exclusion to find
the number of elements in the union of sets.
• Use the pigeonhole principle to find the minimum
number of elements to guarantee two with a
duplicate property.
main iDea
• The principle of inclusion and exclusion and the
piegeonhole principle are additional counting
mechanisms for sets.
W
269
Pigeonhole Principle
The pigeonhole principle acquired its quaint name from the following idea: If
more than k pigeons fly into k pigeonholes, then at least 1 hole will end up with
more than 1 pigeon. Although this seems immediately obvious, we can belabor the
point. Suppose each of the k pigeonholes contains at most 1 pigeon. Then there are
at most k pigeons, not the more-than-k pigeons that supposedly flew in.
Now we’ll state the pigeonhole principle in a less picturesque way.
pRinciple PigeONhOle PRiNCiPle
If more than k items are placed into k bins, then at least 1 bin contains more than
1 item.
By cleverly choosing items and bins, a number of interesting counting problems can be solved (see Example 7 of Chapter 2).
example 43
How many people must be in a room to guarantee that 2 people have last names
that begin with the same initial?
There are 26 letters of the alphabet (bins). If there are 27 people, then there are
27 initials (items) to put into the 26 bins, so at least 1 bin will contain more than
1 last initial.
■
PraCtiCe 29 How many times must a single die be rolled in order to guarantee getting the same value
twice?
example 44
Prove that if 51 positive integers between 1 and 100 are chosen, then one of them
must divide another.
Let the integers be n 1 , …, n 51 . Each integer n i ≥ 2 can be written as a product
of prime numbers (fundamental theorem of arithmetic), every prime number except
2 is odd, and the product of odd numbers is odd. Therefore for each i, n i = 2
k i b i ,
where k i ≥ 0 and b i is an odd number. Furthermore, 1 ≤ b i ≤ 99, and there are 50
odd integers between 1 and 99 inclusive, but there are 51 b values. By the pigeonhole principle, b i = b j for some i and j, so n i = 2
k i b i and n j = 2
kj
b i . If k i ≤ k j , then n i
divides n j ; otherwise, n j divides n i .
S e c t i o n 4 . 3 review
tecHniQueS
• Use the principle of inclusion and exclusion to find
the number of elements in the union of sets.
• Use the pigeonhole principle to find the minimum
number of elements to guarantee two with a
duplicate property.
main iDea
• The principle of inclusion and exclusion and the
piegeonhole principle are additional counting
mechanisms for sets.
W