Math 2320 Assignment 2 Solution

Math 2320 Assignment 2 Solution 1. How many people are needed to guarantee that at least two were born on the same day of the week and in the same month (perhaps in different years)? Solution: There are seven days in a week and 12 months in a year. We need at least (7 × 12 + 1) = 85 people to guarantee d 85 84 e = 2 were born on the same day of the week and in the same month. 2. (a) Show that if seven integers are selected from the first 10 positive integers, there must be at least two pairs of these integers with the sum 11. Solution: We group {1, 2, . . . , 10} into five groups {1, 10}, {2, 9}, {3, 8}, {4, 7} and {5, 6}. Note the pairs in each group sum to 11. By the pigeonhole principle (with the seven integers being the objects and the five groups being the boxes), there are at least two integers coming from the same group. These two integers sum to 11. Removing this pair of integers, there are five integers and four groups left. Using the pigeonhole principle, there are at least two integers (out of the remaining five integers) coming from one of the four groups. These two integers give the second pair with the sum 11. (b) Is the conclusion in part (a) true if six integers are selected rather than seven? Solution: No, among 1, 2, 3, 4, 5, 6, there is only one pair of integers summing to 11. 3. Seven women and nine men are on the faculty in the mathematics department at a school. (a) How many ways are there to select a committee of five members of the department if at least one woman must be on the committee? Solution: The
total number of committees of five with no restriction is 16 9
= 4368. There are = 126 ways to choose a committee 5 5 of 5 out of 9 men, hence with no woman. As a result, there are 4368 − 126 = 4242 committees with at least one woman. 1

(b) How many ways are there to select a committee of five members of the department if at least one woman and at least one man must be on the committee? Solution:
There are 75 = 21 ways to select a committee of 5 out of 7 women, hence no man. From the previous part, there are 4368 committees with no restriction and there are 126 committees with no woman. Therefore there are 4368−126−21 = 4221 committees with at least one woman and at least one man. 4. What is the probability that a five-card poker hand has the following? (a) Four Aces Solution:
There are 52 = 2598960 possible hands of five cards. In a 5 hand with four Aces, there are 52 − 4 choices for the fifth card. So, the probability of getting a five-card hand with four Aces is 48 1 2598960 = 54145 . (b) Four of a kind Solution: There are 13 choices for the four of a kind, and 52 − 4 choices for the fifth card. So, the probability of getting a five-card hand with four of a kind is 1 13 × 48 = . 2598960 4165 (c) A full house (three of a kind, and a pair) Solution:

There are 13 × 43 choices for the three of a kind, and 12 × 42 choices for the pair. So, the probability of getting a full house is

13 × 43 × 12 × 42 6 = . 2598960 4165 (d) Two pairs (not four of a kind nor a full house) Solution:
There are 13 for the two values of two pairs. For each 2 choices
value, we have 42 pairs, and 52 − 8 choices for the fifth card. So, the probability of getting a five-card hand with two pairs is 13
4
4
198 2 × 2 × 2 × 44 = . 2598960 4165 2

(e) A straight (a set of five consecutive values with the initial card value between Ace and 9) Solution: The straight could start with a Ace or 2 or . . . or 9. There are 9 choices of the starting number of the straight. Each of the cards could be one of the four suits. As a result, there are 9×4 5 possible straights. So, the probability of getting a straight is 9 × 45 192 = . 2598960 54145 5. A croissant shop has plain croissants, cherry croissants, chocolate croissants, almond croissants, apple croissants, and broccoli croissants. How many ways are there to choose (a) a dozen croissants? Solution: Let x1 , x2 , x3 , x4 , x5 and x6 be the number of plain croissants, cherry croissants, chocolate croissants, almond croissants, apple croissants, and broccoli croissants chosen, respectively. This problem is equivalent to finding the number of solutions of x1 + x2 + x3 + x4 + x5 + x6 = 12 where x1 , x2 , x3 , x4 , x5 and x6 are nonnegative integers.
= 6188. The number of solutions is 6+12−1 12 (b) two dozen croissants with at least two of each kind? Solution: This problem is equivalent to finding the number of solutions of x1 + x2 + x3 + x4 + x5 + x6 = 24

(1)

where x1 , x2 , x3 , x4 , x5 , x6 ≥ 2. We first let y1 = x1 − 2 ≥ 0, y2 = x2 − 2 ≥ 0, y3 = x3 − 2 ≥ 0, y4 = x4 − 2 ≥ 0, y5 = x5 − 2 ≥ 0 and y6 = x6 − 2 ≥ 0. Then we have y1 + y 2 + y 3 + y 4 + y 5 + y 6 = (x1 − 2) + (x2 − 2) + (x3 − 2) + (x4 − 2) + (x5 − 2) + (x6 − 2) = 24 − 12 = 12. 3

The number of solutions of (1) is equal to the number of solution of y1 + y2 + y3 + y4 + y5 + y6 = 12 where y1 , y2 , y3 , y4 , y5 , y6 ≥ 0.
= 6188. The number of solutions is 6+12−1 12 (c) two dozen croissants with no more than two broccoli croissants? Solution: This problem is equivalent to finding the number of solutions of x1 + x2 + x3 + x4 + x5 + x6 = 24

(2)

where x1 , x2 , x3 , x4 , x5 and x6 are nonnegative integers and x6 ≤ 2
We first see that there are 6+24−1 = 118755 solutions to 24 x1 + x2 + x3 + x4 + x5 + x6 = 24 where x1 , x2 , x3 , x4 , x5 and x6 are nonnegative integers. Now we count the number of solutions of x1 + x2 + x3 + x4 + x5 + x6 = 24 where x1 , x2 , x3 , x4 , x5 and x6 ≥ 3 are nonnegative integers. We let y6 = x6 − 3 and get x1 + x2 + x3 + x4 + x5 + y6 = 21 where x1 , x
2 , x3 , x4 , x5 and y6 are nonnegative integers. There are 21+6−1 = 65780 solutions to this equation. 21 Hence there are 118755 − 65780 = 52975 solutions for (2). (d) two dozen croissants with at least five chocolate croissants and at most three almond croissants? Solution: This problem is equivalent to finding the number of solutions of x1 + x2 + x3 + x4 + x5 + x6 = 24

(3)

where x1 , x2 , x3 , x4 , x5 and x6 are nonnegative integers, x3 ≥ 5 and x4 ≤ 3. We first count the number of solutions of x1 + x2 + x3 + x4 + x5 + x6 = 24 4

where x1 , x2 , x3 , x4 , x5 and x6 are nonnegative integers and x3 ≥ 5. Let y3 = x3 − 5 ≥ 0 and we get the following equivalent equation x1 + x2 + y3 + x4 + x5 + x6 = 24 − 5 where x1 , x2 , y3 , x4 , x5 and x6 are nonnegative
integers. The number of solutions of this equation is 6+19−1 = 42504. 19 Now we count the number of solutions of x1 + x2 + x3 + x4 + x5 + x6 = 24 where x1 , x2 , x3 , x4 , x5 and x6 are nonnegative integers and x3 ≥ 5 and x4 ≥ 4. Let y3 = x3 − 5 ≥ 0 and y4 = x4 − 4. We get the following equivalent equation x1 + x2 + y3 + y4 + x5 + x6 = 24 − 5 − 4 where x1 , x2 , y3 , y4 , x5 and x6 are nonnegative
integers. The num6+15−1 = 15504. ber of solutions of this equation is 15 Hence the number of solutions of (3) is 42504 − 15504 = 27000. 6. How many positive integers less than 1,000,000 have exactly one digit equal to 9 and have a sum of digits equal to 13? Solution: Let Si be the set of positive integers less than 1,000,000 with only the ith digit being 9 and have a sum of digits equal to 13, for i = 1, . . . , 6. Since our desired integers have exactly one digit equal to 9, the sets S1 , S2 , . . . , S6 are pairwise disjoint. If a positive integer in S6 has its last digit being 9, the sum of its first to fifth digits equals 13 − 9 = 4. Since the sum of these five digits is 4 < 9, none of these digits can be 9. For j = 1, . . . , 5, let x j be the j th digit. Then the number of positive integers in S 6 is equal to the number of solutions of x1 + x 2 + x 3 + x 4 + x 5 = 4 where x1 , . . . , x5 are nonnegative integers. There are solutions and hence |S1 | = 70.

5+4−1
4

= 70

Similarly, we have |S1 | = |S2 | = |S3 | = |S4 | = |S5 | = 70. By the sum rule, there are 70 + 70 + 70 + 70 + 70 + 70 = 420 positive integers less than 1,000,000 have exactly one digit equal to 9 and have a sum of digits equal to 13. 5

7. How many different strings can be made from the letters in AARDVARK (a) using all the letters, if all three A’s must be consecutive? Solution: We treat ”AAA” as one symbol, and count the number of permutations of ”AAA”, R, R, D, V, K. By Theorem 3 on page 375, 6! there are 1!2!1!1!1! = 360 desired strings. (b) using seven or more letters? Solution: If the seven letters are A, A, R, R, D, V, K, then the number of 7! = 1260. strings are 2!2!1!1!1! If the seven letters are A, A, A, R, D, V, K, then the number of 7! strings are 3!1!1!1!1! = 840. If the seven letters are A, A, A, R, R, V, K, then the number of 7! strings are 3!2!1!1! = 420. If the seven letters are A, A, A, R, R, D, K, then the number of 7! strings are 3!2!1!1! = 420. If the seven letters are A, A, A, R, R, D, V, then the number of 7! = 420. strings are 3!2!1!1! By the sum rule, there are 1260 + 840 + 420 + 420 + 420 = 3360 strings of seven letters in AARDVARK. 8! There are 3!2!1!1!1! = 3360 strings of eight letters in AARDVARK. By the sum rule, there are 3360+3360 = 6720 strings using seven or more letters.

6