Chapter 14 Cardinality Rules612
Exam Problems
Problem 14.45.
A standard 52 card deck has 13 cards of each suit. Use the Pigeonhole Principle to
determine the smallestksuch that every set ofkcards from the deck contains five
cards of the same suit (called aflush). Clearly indicate what are the pigeons, holes,
and rules for assigning a pigeon to a hole.
Problem 14.46.
Use the Pigeonhole Principle to determine the smallest nonnegative integernsuch
that every set ofnintegers is guaranteed to contain three integers that are congruent
mod 211. Clearly indicate what are the pigeons, holes, and rules for assigning a
pigeon to a hole, and give the value ofn.
Problems for Section 14.9
Practice Problems
Problem 14.47.
LetA 1 ,A 2 ,A 3 be sets withjA 1 jD 100 ,jA 2 jD1;000, andjA 3 jD10;000.
DeterminejA 1 [A 2 [A 3 jin each of the following cases:
(a)A 1 A 2 A 3.
(b)The sets are pairwise disjoint.(c)For any two of the sets, there is exactly one element in both.(d)There are two elements common to each pair of sets and one element in all
three sets.
Problem 14.48.
The working days in the next year can be numbered 1, 2, 3,... , 300. I’d like to
avoid as many as possible.
On even-numbered days, I’ll say I’m sick. On days that are a multiple of 3, I’ll say I was stuck in traffic. On days that are a multiple of 5, I’ll refuse to come out from under the
blankets.