Section 6.1- An Introduction to Discrete Probability-Discrete Mathematics and Its Applications - 1

Rosen, Discrete Mathematics and Its Applications, 6th edition
Extra Examples
Section 6.1—An Introduction to Discrete Probability (Part - 1)

p.394, icon at Example 1
#1. A computer password consists of five lower case letters, with repeated letters allowed. Find p(E) where E is the event that the password begins with c.

Solution:
The sample space S has 26^5 elements, corresponding to the number of ways to fill in the following five blanks with lower case letters: . The event E has 26^4 elements, corresponding to the number of ways to fill in the four blanks in c . Thereforep(E) = p(password begins with c) =|E|/|S| = (26^4)/(26^5) = 1 /  26  ≈  0.038.

Note: In place of writing p(E), we often replace E with the English description of E.

p.394, icon at Example 1

#2. A computer password consists of five lower case letters, with repeated letters allowed.

(a) Find p(F1), where F1 is the event that the password contains no vowels.

(b) Find p(F2), where F2 is the event that the password contains only vowels.

Solution:

(a) The set F1 has 21^5

elements because each of the five blanks must be filled in with one of 21 consonants.

Therefore

p(F1) = p(password contains no vowels) = |F1| / |S| = (21^5) / (26^5 ) ≈ 0.344.

(b) The set F2 has 5^5 elements because each of the five blanks must be filled in with one of five vowels. Therefore

p(F2) = p(password contains only vowels) = |F2| / |S| = (5^5) / (26^5) ≈ 0.00026

p.394, icon at Example 1

#3. A professor teaches two sections of a calculus course and gave a quiz to the students in each section.

In Section 1, 8 students out of 35 got a score of 90 or higher. In Section 2, 11 students out of 28 got a score of 90 of higher.

Find the probability that the student:

(a) is in Section 1, if the student is chosen at random from among all 63 students.

(b) is not in Section 1, if the student is chosen at random from among all 63 students.

(c) scored at least 90 on the quiz, if the student is chosen at random from those in Section 1.

(d) is in Section 1 and scored at least 90 on the quiz, if the student is chosen at random.

(e) is in Section 1, if the student is chosen at random from those who scored at least 90 on the quiz.

Solution:

The given information can be displayed in the following table:

                 |  Section 1 | Section 2 |

Score ≥ 90  |       8        |       11     |

score < 90   |      27       |      17      |

(a) Of the 63 students, 35 are in Section 1. Therefore, the probability that the student is in Section 1 is 35/63.

(b) The probability that a randomly chosen student is not in Section 1 is equal to the probability that the student is in Section 2, which is 28/63.

(c) There are 35 students in Section 1. The probability that the student scored at least 90 is 8/35.

(d) Eight students are in Section 1 and scored at least 90 on the quiz. Therefore, the probability that the student is in Section 1 and scored at least 90 on the quiz is 8/63.

(e) The number of students who scored at least 90 on the quiz is 19, and, of these, 8 come from Section 1.

Therefore, the probability that a randomly chosen student comes from Section 1 is 8/19.

p.394, icon at Example 1

#4. You flip a coin twice. Find the following:

(a) p(E) where E is the event of getting heads on the first flip and tails on the second flip.

(b) p(F) where F is the event of getting one head and one tail in the two flips.

Solution:

The sample space for this experiment is S = {H H, H T , T H, T T } where H stands for heads, T for tails, the first letter in each pair is the result of the first flip, and the second letter is the result of the second flip.

(a) The event E = {H T }. Thus p(E) = |E|/|S| = 1/4.

(b) The event F = {H T  ,  T  H}. Thus p(F) = |E|/|F| = 2/4 =  1/2.

p.394, icon at Example 1

#5. A tetrahedral die is a regular polyhedron consisting of 4 equilateral triangles, with the four faces

numbered 1, 2, 3, 4. You roll the pair of tetrahedral dice. Find the probability that the sum is: (a) 2, (b) 3,

(c) 4, (d) 5, (e) 6, (f) 7, (g) 8.

Solution:

The sample space consists of the 16 elements:

(1, 1),(1, 2),(1, 3),(1, 4),(2, 1),(2, 2),(2, 3),(2, 4),(3, 1),(3, 2),(3, 3),(3, 4),(4, 1),(4, 2),(4, 3),(4, 4).

Thus, the probabilities are: (a) 1/16, (b) 2/16, (c) 3/16, (d) 4/16, (e) 3/16, (f) 2/16, (g) 1/16.

Section5-6-Generating Permutations and Combinations

Rosen, Discrete Mathematics and Its Applications, 6th edition
Extra Examples
Section 5.6—Generating Permutations and Combinations


p.383, icon at Example 2
#1. Place the following permutations of 1, 2, 3, 4, 5, 6 in lexicographic order: 461325, 326145, 516243, 324165, 461235, 324615, 462135.

Solution:
Proceeding from smallest to largest we have:

324165, 324615, 326145, 461235, 461325, 462135, 516243.

p.383, icon at Example 2
#2. Find the permutation of 1, 2, 3, 4, 5, 6 immediately after 263541 in lexicographic order.

Solution:
The digits 5, 4, 1 are in descending order, so we need to increase the digit in the third position, 3. Replacing this digit 3 by 4 and then putting the remaining digits in increasing order, we have 264135.

p.383, icon at Example 2
#3. Find the permutation of 1, 2, 3, 4, 5, 6 immediately before 261345 in lexicographic order.

Solution:
The final four digits, 1345, are in increasing order. Therefore the permutation that comes immediately before this must have a 5 in the second position and the four digits to the right of the 5 in decreasing order. Thus, the predecessor of 261345 is 256431.


p.383, icon at Example 2
#4. If the permutations of 1, 2, 3, 4, 5, 6 are put in lexicographic order, with 123456 in position 1, 123465 in position 2, etc., find the permutation in position 362.

Solution:
There are 6! = 720 permutations of 1, 2, 3, 4, 5, 6. The first 120 (i.e., the permutations in positions 1 through 120) begin with 1, the second 120 (in positions 121 through 240) begin with 2, etc. Hence the first permutation beginning with 4, 412356, is in position 361. Therefore, the next permutation, 412365, will be in position 362.

p.383, icon at Example 2
#5. If the permutations of 1, 2, 3, 4, 5 are put in lexicographic order, in what position is the permutation 41253?

Solution:
There are 4! = 24 permutations of 1, 2, 3, 4, 5 that begin with 1; these permutations are in positions 1 through 24. Similarly, the permutations in positions 25 through 48 begin with 2 and the permutations in positions 49 through 72 begin with 3. Thus, the first permutation beginning with 4, 41235, is in position 73. Therefore 41253 is in position 74.

Section 5-5-Generalized Permutations and Combinations - Discrete Mathematics and Its Applications

Rosen, Discrete Mathematics and Its Applications, 6th edition
Extra Examples
Section 5.5—Generalized Permutations and Combinations

p.373, icon at Example 4

#1. A jar contains 30 pennies, 20 nickels, 20 dimes, and 15 quarters. (The coins of each denomination are considered to be identical.)

(a) Find the number of ways to put all 85 coins in a row.
(b) Find the number of possible handfuls of 12 coins.

Solution:

(a) The answer is not 85! because not all the coins are distinct. Think of the problem as one of taking 30 p’s, 20 n’s, 20 d’s, and 15 q’s, and putting these letters in a row. Taking into account the identical letters,

we have 85! / 30! · 20! · 20! · 15! .

(b) The number of handfuls of 12 coins is equal to the number of nonnegative integer solutions to the equation p + n + d + q = 12.

The number of solutions to this equation is C(15, 3) = 455.

p.373, icon at Example 4

#2. A bakery sells four kinds of cookies: chocolate, jelly, sugar, and peanut butter. You want to buy a bag of 30 cookies. Assuming that the bakery has at least 30 of each kind of cookie, how many bags of 30 cookies could you buy if you must choose:

(a) at least 3 chocolate cookies and at least 6 peanut butter cookies.
(b) exactly 3 chocolate cookies and exactly 6 peanut butter cookies.

Solution:

We will use c to represent the number of chocolate cookies purchased, j for the number of jelly cookies purchased, s for the number of sugar cookies purchased, and p for the number of peanut butter cookies purchased.

(a) We must have c ≥ 3 and p ≥ 6. Picture yourself in the bakery with an empty bag in which you will place 30 cookies. Put into the bag three chocolate cookies and six peanut butter cookies. The bag now has nine cookies in it, so you need to place 21 more cookies into the bag. You have met the two conditions, so you do not care about the numbers of each of the four types you choose for the remaining 21 cookies.
Therefore, you need to find the number of nonnegative integer solutions to the equation c + j + s + p = 21.

The number of nonnegative integer solutions to this equation is C(24, 3). Therefore there are C(24, 3) = 2,024 ways to buy 30 cookies with at least 3 chocolate cookies and at least 6 peanut butter cookies.

(b) We must have c = 3 and p = 6. Picture yourself in the bakery with an empty bag in which you will place 30 cookies. Put into the bag three chocolate cookies and six peanut butter cookies. The bag now has nine cookies in it, so you need to place 21 more cookies in to the bag, but you cannot select more chocolate or peanut butter cookies. Therefore you need to find the number of nonnegative integer solutions to the equation j + s = 21.

The number of nonnegative integer solutions to this equation is C(22, 1) = 22. Therefore there are 22 ways to buy 30 cookies with exactly 3 chocolate cookies and exactly 6 peanut butter cookies.


p.373, icon at Example 4

#3. A bakery sells four kinds of cookies: chocolate, jelly, sugar, and peanut butter. You want to buy a bag of 30 cookies. Assuming that the bakery has at least 30 of each kind of cookie, how many bags of 30 cookies could you buy if you must choose at most 5 sugar cookies.

Solution:

We will use c to represent the number of chocolate cookies purchased, j for the number of jelly cookies purchased, s for the number of sugar cookies purchased, and p for the number of peanut butter cookies purchased.

To solve the problem, we use “complement counting”. That is, we find the number of possible bags of 30 cookies with more than 5 sugar cookies, and then subtract that number from the total number of bags of 30 cookies. That is, we find the number of solutions to c + j + s + p = 30 with s ≥ 6. This is the number of solutions to the equation c + j + s + p = 24, which equals C(27, 3).

Thus, the answer to the question is the total number of nonnegative integer solutions to the equation c + j + s + p = 30, C(33, 3), with C(27, 3) subtracted: (total number of solutions) − (number of solutions with s ≥ 6) = C(33, 3) − C(27, 3) = 2,531.

p.373, icon at Example 4

#4. A bakery sells four kinds of cookies: chocolate, jelly, sugar, and peanut butter. You want to buy a bag of 30 cookies. Assuming that the bakery has at least 30 of each kind of cookie, how many bags of 30 cookies could you buy if you must choose at least one of each of the four types of cookies.

Solution:

We will use c to represent the number of chocolate cookies purchased, j for the number of jelly cookies purchased, s for the number of sugar cookies purchased, and p for the number of peanut butter cookies purchased.

To “see” the solution, take an empty bag and place in it one cookie of each of the four types. This leaves 26 more cookies to be selected and there are no additional restrictions on the cookies. This yields the equation c + j + s + p = 26. The number of nonnegative integer solutions to this new equation is C(29, 3) = 3,654.


p.375, icon at Example 7

#1. In how many ways can the letters in DECEIVED be arranged in a row?

Solution:

The word has two D’s, three E’s, one C, one I, and one V. Therefore, the number of permutations of DECEIVED is 8! / (2! · 3! · 1! · 1! · 1!) = 8! /( 2! · 3!) = 3,360.


p.375, icon at Example 7

#2. In how many ways can 7 of the 8 letters in CHEMISTS be put in a row?

Solution:

There are two patterns to consider:
(a) seven distinct letters are selected (that is, only one S is selected), and
(b) the two S’s are selected.
In the first pattern, there are 7! ways to put the 7 distinct letters in a row.
In the second pattern, we select the two S’s and use all but one of the six other letters. For example, we could use the letters S,S and C,H,E,M,T, or S,S and C,H,E,M,I. Each of these sets of seven letters can be put in a row in 7!/2 ways. There are 6 ways to choose five of the six letters that are not S’s; therefore, there are 6 · 7!/2 ways to have the second pattern.

Adding the totals obtained from the two cases, we have the total number of ways to put seven of the eight letters in a row is 7! + 6 · (7!/2!) = 20,160.

p.376, icon after start of ”Distributing Objects into Boxes” subsection

#1. Four players are playing bridge. In how many ways can they be dealt hands of cards? (In bridge, a hand of cards consists of 13 out of 52 cards.)

Solution:

This is a problem of placing 52 distinguishable objects (the cards) in four distinguishable piles of size 13 (one pile for each of the four players). This can be done is 52! / 13!·13!·13!·13! ways.

p.376, icon after start of ”Distributing Objects into Boxes” subsection

#2. In how many ways can ten books be put in four labeled boxes, if one or more of the boxes can be empty? Assume that the books are:
(a) distinct.
(b) identical.

Solution:

(a) Each book can be placed in any of the four boxes. By the product rule, this can be done in 410 ways.
(b) Let xi be the number of books in box i. We need to find the number of nonnegative integer solutions to the equation x1 + x2 + x3 + x4 = 10. There are C(13, 3) such solutions.

Section 5.3 Permutations and Combinations - Discrete Mathematics and Its Applications-Extra Examples

Rosen, Discrete Mathematics and Its Applications, 6th edition
Extra Examples
Section 5.3—Permutations and Combinations


p.355, icon at Example 1
#1. A class has 30 students enrolled. In how many ways can:
(a) four be put in a row for a picture?
(b) all 30 be put in a row for a picture?
(c) all 30 be put in two rows of 15 each (that is, a front row and a back row) for a picture?


Solution:
(a) We need to fill in the following row of four blanks: . This can be done in 30 · 29 · 28 · 27 ways.
This is the number of 4-permutations from a set of 30, which is P(30, 4).


(b) The answer can be visualized as the number of ways to fill in a row of 30 blanks with the 30 students,
which is 30!, or P(30, 30).


(c) The answer can be visualized as the number of ways to fill in two rows, each with 15 blanks, with the 30 students:
We can begin by filling in the bottom row, which can be done in 30 · 29 · 28 · . . . · 17 · 16 ways. Then we fill in the top row, which can be done in 15 · 14 · 13 · . . . · 2 · 1 ways. Therefore the answer is  (30 · 29 · 28 · · · 17 · 16) · (15 · 14 · 13 · · · 2 · 1) = 30 ! .




p.355, icon at Example 1
#2. A class has 20 women and 16 men. In how many ways can you
(a) put all the students in a row?
(b) put 7 of the students in a row?
(c) put all the students in a row if all the women are on the left and all the men are on the right?


Solution:
(a) There are 36 students. They can be put in a row in 36! ways.


(b) You need to have an ordered arrangement of 7 out of 36 students. The number of such arrangements is P(36, 7).


(c) You need to have an ordered arrangement of all 20 women AND and ordered arrangement of all 16 men.
By the product rule, this can be done in 20!·16! ways.




p.360, icon at Example 12
#1. A certain type of push-button door lock requires you to enter a code before the lock will open. The lock has five buttons, numbered 1, 2, 3, 4, 5. The lock is programmed to recognize six different 4-digit codes, with repeated digits allowed in each code. How many different sets of recognizable codes are there?


Solution:
There are 5^4 = 625 possible four-digit codes. Therefore, there are C(625, 6) different sets of six codes that the lock can be programmed to recognize.




p.360, icon at Example 12
#2. Several states play a lottery game called Mega Millions. On a Mega Millions lottery game ticket, you pick a set of five numbers from the numbers 1 through 56 on the top panel of the ticket, and one number (the Mega Ball number) from 1 through 46 on the bottom half of the ticket. (The Mega Ball number can be the same as one of the five numbers picked on the top half of the ticket.) A set of six winning numbers is selected: five numbers from 1 through 56 and one Mega Ball number from the numbers 1 through 46. You win a prize if your selections match some or all of the winning numbers, as follows: five and Mega Ball, five and no Mega Ball, four and Mega Ball, four and no Mega Ball, three and Mega Ball, three and no Mega Ball, two and Mega Ball, one and Mega Ball, only the Mega Ball.
Find the number of ways in which you can have one ticket with
(a) five winning numbers, but no Mega Ball.
(b) two winning numbers and the Mega Ball.


Solution:
(a) The number of ways in which all five numbers can be chosen correctly is C(5, 5) = 1 and the number of ways of choosing a number other than the Mega Ball is C(45, 1) = 45. Therefore, the number of ways to choose five numbers and miss the Mega Ball is C(5, 5)· C(45, 1) = 45.


(b) The number of ways in which exactly two of the five numbers can be chosen correctly is C(5, 2)· C(51, 3) — you choose two of the five winning numbers and three of the 51 losing numbers. The number of ways of choosing the Mega Ball is C(1, 1). Therefore, the number of ways to choose exactly two winning numbers and the Mega Ball is C(5, 2)· C(51, 3)· C(1, 1) = 208, 250.




p.360, icon at Example 12
#3. How many ways are there to choose a committee of size five consisting of three women and two men from a group of ten women and seven men?


Solution:
The number of ways to choose three women is C(10, 3) and the number of ways to choose two men is C(7, 2). Using the product rule to choose three women and two men, the answer is C(10, 3) · C(7, 2) = 2, 520.


Note: The answer is not C(17, 5) (which counts all committees of size five) because this ignores that fact that the committees must have exactly three women and exactly two men. Also, the answer is not C(10, 3) + C(7, 2), which is a commonly made mistake. This says that you are choosing either three women or two 2men; it does not count committees of size five.




p.360, icon at Example 12
#4. Let S = {1, 2, . . . , 19}. Find the number of subsets of S with equal numbers of odd integers and even integers.


Solution:
Note that there are 10 odd integers and 9 even integers in S. The subsets to be counted must consist of k odd integers and k even integers, where k = 1, 2, 3, . . . , 9. Therefore, by the product rule, the number of each type is C(10, k)· C(9, k). Therefore, by the sum rule the answer is
C(10, 0) · C(9, 0) subsets with 0 odd and 0 even + C(10, 1)· C(9, 1) subsets with 1 odd and 1 even + C(10, 2)· C(9, 2)m subsets with 2 odd and 2 even + · · · + C(10, 9)· C(9, 9) subsets with 9 odd and 9 even = 92,377.
or 
C(10, 0) · C(9, 0)  + C(10, 1)· C(9, 1) + C(10, 2)· C(9, 2) + · · · + C(10, 9)· C(9, 9) = 92,377.




p.360, icon at Example 12
#5. Find the number of words of length 10 of letters of the alphabet, with no repeated letters, such that each word has equal numbers of vowels and consonants.


Solution:
Visualize a row of ten blanks. Each word of length 10 must contain all five vowels and five of the 21 consonants. There are different ways to solve this problem.
Here is one way to solve the problem. Choose a set of five of the ten blanks for the vowels. Then place the five vowels in these positions. These two steps can be done in C(10, 5)· 5! ways. Next, choose 5 consonants from the 21 consonants, and place them in the remaining five blanks. These two steps can be done in C(21, 5)· 5! ways. Thus, the number of ways of forming the desired words by placing the vowels and consonants is C(10, 5)·5!·C(21, 5)·5! = (10!/5!5!)·5!·(21!/5!16!)·5! =10!21!5!16!= 10·9·8·7·6·21·20·19·18·17 = 73,842,451,200.


Here is a second way to approach the problem. Choose any set of five consonants, and form a set consisting of these five consonants and the five vowels. These ten letters can be arranged in 10! ways, each of which forms one of the words we are counting. But there are C(21, 5) ways to choose the five consonants. Therefore, there are C(21, 5) · 10! = 10·9·8·7·6 · 21·20·19·18·17 words.
Here is a third way to approach the problem. First, place the five vowels in five of the ten blanks (10 choices for A, 9 choices for E, etc.) — this can be done in 10·9·8·7·6 ways. Then place five of the 21 consonants in the five remaining blanks (21 choices for the first blank, 20 choices for the second blank, etc.) — this can be done in 21·20·19·18·17 ways. Therefore, by the product rule, the number of words with the five vowels and five consonants is 10·9·8·7·6 · 21·20·19·18·17.




p.360, icon at Example 12
#6. Find the number of ways to take an ordinary deck of 52 playing cards and break it into:
(a) four equal piles, labeled A, B, C, D.
(b) four equal piles that are not labeled.


Solution:
(a) Each pile must have 52/4 = 13 cards in it. In sequence, we form pile A, then pile B, then pile C, and finally pile D. There are C(52, 13) ways to obtain pile A, C(39, 13) ways to obtain pile B, C(26, 13) ways to obtain pile C, and C(13, 13) = 1 way to obtain pile D. Therefore, by the product rule the answer is 
C(52, 13)· C(39, 13)· C(26, 13)· C(13, 13) = (52!/13! · 39!)·(39!/13! · 26!)·(26!/13! · 13!)·(13!/13! · 0!) = 52!/(13!)^4.


(b) If the four piles are not labeled, there is no distinction to be made among piles A, B, C, D. We can permute these in 4! ways. Hence the answer is the answer to part (a) divided by 4!:
(C(52, 13)· C(39, 13)· C(26, 13)· C(13, 13))/4! = 52! / ((13!)^4)· 4!).




p.360, icon at Example 12
#7. Suppose S = {1, 2, . . . , 25}. Find the number of subsets T ⊆ S of size five such that T consists of two odd numbers and three even numbers.


Solution:
There are 13 odd numbers; we can choose two in C(13, 2) ways. There are 12 even numbers; we can choose three in C(12, 3) ways. Using the product rule to find the number of elements in T , we have C(13, 2) · C(12, 3) =17,160 subsets.




p.360, icon at Example 12
#8. Suppose S = {1, 2, . . . , 25}. Find the number of subsets T ⊆ S of size five such that T consists of exactly three prime numbers.


Solution:
(b) The prime numbers in S are 2, 3, 5, 7, 11, 13, 17, 19, and 23, and there are C(9, 3) ways to select three


of them. But we also need to select two of the 16 composite numbers to make T have size five; there are C(16, 2) ways to this. Therefore, the product rule gives C(9, 3) · C(16, 2) = 10,080 possible subsets T .




p.360, icon at Example 12
#9. Suppose S = {1, 2, . . . , 25}. Find the number of subsets T ⊆ S of size five such that T has the sum of its elements less than 18.


Solution:
There are very few subsets with this property. It is easiest in this case to count directly the set of five numbers whose sum is less than 18: 1, 2, 3, 4, 5, 1, 2, 3, 4, 6, 1, 2, 3, 4, 7, 1, 2, 3, 5, 6. Thus, there are four such subsets.




p.360, icon at Example 12
#10. Suppose S = {1, 2, . . . , 25}. Find the number of subsets T ⊆ S of size five such that T has at least one even number in it.


Solution:
It is easiest to count the total number of subsets of size five, and then subtract the number of subsets with no even numbers in them: C(25, 5) − C(13, 5) = 51,843.
Note: When you need to count objects that have a certain property, a good problem solving strategy to consider is “complement counting” — count the total number of objects in the universe and then subtract the number of objects that fail to have the desired property.

Section 5-2 The Pigeonhole Principle-Discrete Mathematics and Its Applications-Page-2

Rosen, Discrete Mathematics and Its Applications, 6th edition
Extra Examples
Section 5.2—The Pigeonhole Principle




p.349, icon at Example 6
#1. Each type of machine part made in a factory is stamped with a code of the form “letter-digit-digit”,
where the digits can be repeated. Prove that if 8000 parts are made, then at least four must have the same
code stamped on them.
Solution:
The maximum number of possible codes (pigeonholes) is 26 · 10 · 10 = 2600. But 8000 > 3 · 2600. Therefore
at least four parts must have the same code.




p.349, icon at Example 6
#2. Each student is classified as a member of one of the following classes: Freshman, Sophomore, Junior,
Senior. Find the minimum number of students who must be chosen in order to guarantee that at least eight
belong to the same class.

Solution:

The four classes are the pigeonholes. A group of 28 students could have 7 belonging to each class. But if

there are 29 students, at least 8 must be members of the same class. Therefore, the minimum number of

students who must be chosen is 29.

In other words, we are looking for the minimum number N such that [N/4] = 8. The minimum number is 29.

p.349, icon at Example 6

#3. What is the minimum number of cards that must be drawn from an ordinary deck of cards to guarantee

that you have been dealt

(a) at least three of at least one rank?

(b) at least three aces?

(c) the ace of diamonds?

Solution:

(a) There are thirteen ranks. If you are dealt 26 cards, it is possible that they consist of two cards of each

rank — two aces, two twos, two threes, . . . , two queens, two kings. The 27th card dealt must give you a

hand with three of some rank. (The pigeonholes are the thirteen ranks and the cards are the pigeons.)

(b) In the worst-case scenario, you are dealt 48 cards that include no aces. In order to get three aces, you

would need to be dealt 51 cards.

(c) It is possible that the ace of diamonds could be the last card dealt. Thus, you would need to have all 52

cards dealt to obtain the ace of diamonds.

p.349, icon at Example 6

#4. What is the minimum number of cards that must be drawn from an ordinary deck of cards to guarantee

that you have been dealt

(a) at least three of at least one suit?

(b) at least three clubs?

Solution:

(a) There are four suits. If you are dealt 8 cards, it is possible that they consist of two cards of each suit.

The ninth card dealt must give you three of at least one suit. (The pigeonholes are the four ranks and the

cards are the pigeons.)

(b) In the worst-case scenario, you are dealt 39 cards that include only diamonds, hearts, and spades. In

order to get three clubs, you would need to be dealt three additional cards, making 42 cards.

Section 5-2 The Pigeonhole Principle-Discrete Mathematics and Its Applications-Page-1

Rosen, Discrete Mathematics and Its Applications, 6th edition
Extra Examples
Section 5.2—The Pigeonhole Principle

p.348, icon at Example 4

#1. Prove that in any group of three positive integers, there are at least two whose sum is even.

Solution:

Consider two pigeonholes, labeled EVEN and ODD. If three positive integers are placed in these pigeonholes, one of the pigeonholes must have at least two integers (say a and b) in it. Thus, a and b are either both even or both odd. In either case, a + b is even.

p.348, icon at Example 4

#2. If positive integers are chosen at random, what is the minimum number you must have in order to guarantee that two of the chosen numbers are congruent modulo 6.

Solution:

In order for a and b to be congruent modulo 6, we must have a mod 6 = b mod 6. But there are six possible values for x mod 6: 0, 1, 2, 3, 4, or 5. Therefore seven positive integers must be chosen in order to guarantee that at least two are congruent modulo 6.

p.348, icon at Example 4

#3. Suppose you have a group of n people (n ≥ 2). Use the Pigeonhole Principle to prove that there are at least two in the group with the same number of friends in the group.

Solution:

Suppose you have a group of n people, and suppose that no two persons have the same number of friends in the group. There are n numbers of possible friends that a person can have: 0, 1, 2, . . ., n−1, where 0 means that the person has no friends in the group, 1 means that the person has exactly one friend in the group, . . . , n − 1 means that the person is friends with all other people in the group. 

It is impossible for the numbers 0 and n − 1 to both occur as “friendship numbers” in a group of n people. To see this, suppose person A has 0 friends and person B has n−1 friends. If the friendship number for B is n − 1, then B must be friends with everyone, including A. But this contradicts the fact that the friendship number for A is 0. Therefore, of the n possible friendship numbers, only n − 1 friendship numbers are available in any group of n people.

Because there are n people in the group and only n − 1 available friendship numbers, by the Pigeonhole Principle at least two people have the same friendship number. That is, at least two people in the group have the same number of friends in the group.

p.348, icon at Example 4

#4. Prove that in any set of 700 English words, there must be at least two that begin with the same pair of letters (in the same order), for example, STOP and STANDARD.

Solution:

The number of possible pairs of letters that can appear in the first two positions is 26 · 26 = 676. Thus, by the Pigeonhole Principle, any set of 677 or more words must have at least two words with the same pair of letters at the beginning of the word.

(Note: In reality, the number 700 can be replaced with a much smaller number, because many combinations of letters do not appear as the two beginning letters of a word. For example, there are no English words that begin with NQ, RR, or TZ.)

Section 5.1: The Basics of Counting: Discrete Mathematics and Its Applications: Page -3

Rosen, Discrete Mathematics and Its Applications, 6th edition

Extra Examples

Section 5.1—The Basics of Counting

p.340, icon  at Example 14

#5.   Find  the number  of strings of length  10 of letters  of the alphabet, with no repeated letters,  that have vowels in the first two positions.

Solution:

Keep in mind a row of ten blanks:                                                   .

We will first count the number  of ways to place vowels in the first two blanks.  We can choose any of the five vowels for the first blank and any of the remaining four vowels to put  in the second blank.  Because we must do both,  there are 5 · 4 = 20 ways to place the two vowels. Next  we will place eight  of the remaining  24 letters  in the remaining  eight  blanks.   This  can be done in 24 · 23 ··· 18 · 17 ways.

Therefore,  by the  product  rule, the number  of ways to place vowels in the first two blanks and eight letters in the remaining  eight blanks is

(5 · 4) · (24 · 23 ··· 18 · 17)  

p.340, icon  at Example 14

#6.   Ten men and ten women are to be put  in a row. Find  the number  of possible rows.

Solution:

Keep in mind a row of twenty blanks.  There is no restriction on how the  men and women can be placed 

in a row, so the answer is 20 · 19 · 18 ··· 3 · 2 · 1 = 20!.

p.340, icon  at Example 14

#7.    Ten  men and  ten women are to be put  in a row.  Find  the number  of possible rows if no two of the same sex stand adjacent.

Solution:

Keep in mind a row of twenty blanks.  If no two of the same sex stand in adjacent positions, then there are two possible patterns, using M for male and F for female:

MFMFMFMFMFMFMFMFMFMF  and   FMFMFMFMFMFMFMFMFMFM.

We will count the number  of ways of achieving  the first pattern and  double  this number  to find the  final answer.  The first man can be chosen in 10 ways, the first woman can be chosen in 10 ways, this second man can be chosen in 9 ways, etc.  

Thus,  by the extended  product rule, each pattern can be obtained  in 10 or (10 · 9 ··· 2 · 1)2   ways.  

The second pattern can be obtained  in the same number  of ways, so we double the answer to get 2(10 · 9 ··· 2 · 1)2   = 2 · 10!2 .

 p.340, icon  at Example 14

#8.   Ten men and ten women are to be put  in a row. Find the number  of possible rows if Beryl, Carol, and Darryl  want to stand next to each other in some order (such as Carol, Beryl, and Darryl,  or Darryl,  Beryl, and Carol).

Solution:

Keep in mind a row of twenty blanks.

We first consider  the  arrangements where Beryl, Carol,  and  Darryl stand  next  to each other in that order. We begin by putting the  17 other  people in a row, which can be done in 17! ways.  

No matter how the  17 are placed  in a row, Beryl, Carol,  and  Darryl  can either be inserted  (in that order)  between  two of the 17, or else placed at one of the two ends.  This is pictured  in the following diagram,  where the  17 x’s represent the 17 people placed in a row. 

There  are 18 places in which Beryl, Carol, and Darryl can be placed together

— 16 places between the x’s and two places on the two ends — marked by blanks.

x       x       x       x       x       x       x       x        x       x       x       x       x       x       x       x       x

Therefore,  the number  of ways to place the 18 people, with Beryl, Carol, and Darryl  next to each other (in that order) is But  Beryl, Carol, and Darryl can be permuted in 3! ways.  Therefore,  the final answer is 17! · 18 · 3!.

p.342, icon  at Example 17

#1.   Find  the number  of integers from 1 to 400 inclusive that are:

(a) divisible by 6.

(b) not divisible by 6.

Solution:

 (a)  Every  sixth  integer  from 1 to 400 is divisible  by 6, yielding    400    = 66.  (Note:  When  we divide  400 by 6 we obtain 66 2/3.  The fraction 2/3 indicates  that we are two thirds of the way toward the next integer

divisible by 6, which is 402. We round down because 402 is beyond the range of numbers  from 1 to 400.)

(b) From part  (a) we know that 66 integers from 1 to 400 are divisible by 6. Hence the number  that are not divisible by 6 is 400 − 66 = 334.

p.342, icon  at Example 17

#2.   Find  the number  of integers from 1 to 400 inclusive that are:

(a) divisible by 6 and 8.

(b) divisible by 6 or 8.

Solution:

(a) Divisibility by a and b is the  same as divisibility  by the least common multiple  of a and b.  Therefore, divisibility  by 6 and 8 is the same as divisibility  by 24. The answer is   400    = 16.

(b) We cannot take the number  of integers divisible by 6 and add to it the number of integers divisible by 8, because this would count integers such as 24 or 48 twice (because they are divisible by both 6 and  8).  We need to use the inclusion-exclusion  principle  to avoid the “double  counting”.

Let A1   = {x | 1 ≤ x ≤ 400,  x is divisible by 6}  and   A2   = {x | 1 ≤ x ≤ 400, x is divisible by 8}. We want

|A1  ∪ A2 |.  By the inclusion-exclusion  principle  we have

|A1  ∪ A2 |= |A1 | + |A2 |− |A1  ∩ A2 |

=   400   +   400   −   400  

= 66 + 50 − 16

= 100.

Note:   When  the word  “or”  appears  in  a  counting  problem,  it  is a  wise strategy  to  consider  using  the inclusion-exclusion  principle.

p.342, icon  at Example 17

#3.   Find  the number  of strings of length  10 of letters  of the alphabet, with repeated letters  allowed, (a) that begin with C and end with V.

(b) that begin with C or end with V.

Solution:

 (a) Keep in mind a row of ten blanks:                                                  .

If the string has the form

C                                        V ,

there are 26 ways to fill in each of the eight intermediate blanks.  Hence there are 268   strings of this form. (b) We need to count the number  of strings that have the form

C                                                 or                                                 V

The  number  of strings of each form is 269.   However,  we cannot  simply  add  the  two numbers  to get  our answer.  If we do this,  we are counting  the number  of strings  of the form  C                                                                                   V   twice because each such string fits both  patterns.

We need to use the inclusion-exclusion principle to avoid the double-counting.  Let A1   be the set of all strings of length  ten that begin with C and let A2    be the set of all strings of length  ten that end with V. We want

|A1  ∪ A2 |.  But  by the inclusion-exclusion  principle, 

|A1  ∪ A2 | = |A1 | + |A2 |− |A1  ∩ A2 |

= 269  + 269  − 268.

(The  term  268   was obtained  as the size of A1   ∩ A2 , which is the set of all strings of length ten that begin with C and end with V.)