COT3100.01, Fall 2002S. Lang (10/31/2002) Answer key to Test #2 Nov. 4, 2002Part I. (39 pts., 3 pts. each) True/False, or short-answer, questions. (No explanation needed and no partial credit given.)1. Let N denote the set of natural numbers {0, 1, 2, …}, and let A N and B N. Suppose set A contains a smallest value and set B contains a smallest value. Thus, the set A B contains a smallest value. (False, since the set A B may be empty)2. Suppose A and B are both finite sets. If A B and |A| = |B|, then A = B. (True, since A B, B = A (B – A) is true, which implies |B| = |A| + |B – A| because A (B – A) = ; thus, |B – A| = 0 because |A| = |B| by assumption. Therefore, the set B – A = , so A = B is true since A B.)3. Suppose n 1 is an integer. Then 2n > C(n, k) for any integer k with n k 1. (True, by the formula 2n = C(n, 0) + C(n, 1) + …+ C(n, n) > C(n, k) for any k, n k 1.)4. If C(n, 5) = C(n, 3), then the exact numerical value of n = 8, because C(8, 5) = C(8, 8 – 5) = C(8, 3).5. Suppose n 1 is an integer, and 1 + 2 + … + n = 20100. The exact numerical value of n = 200, because by the formula 1 + 2 + … + n = 2)1( nn = 20100, n(n + 1) = 20100 2 = 200 201.6. In how many ways can 10 movie tickets (to the same movie) be divided between 3 persons where each get at least one ticket? C(9, 2), by lining up the 10 tickets in a row which shows 9 gaps, and choosing 2 out of 9 divides the 10 tickets into 3 groups corresponding to ways of dividing the tickets to 3 persons. (This is the same as the example of dividing 10 apples among 3 persons, as in the course notes.)7. In how many ways can the 9 letters in the word “PAPERTAPE” (and only these letters) be re-arranged?!2!2!3!9, because there are 9 letters for the permutations, consisting of 3 Ps, 2 As, 2 Es, and 1 of each remaining letters R and T. 8. A pocket contains 5 coins: 2 quarters, 2 dimes, and 1 penny. When blindly picking two coins out of the pocket, is it more likely to get 1 quarter and 1 dime, or more likely to get 1 penny and 1 dime? Getting 1 quarter and 1 dime is more likely because there are 2 2 = 4 many ways to select 1 quarter and 1 dime, compared to 1 2 = 2 ways to select 1 penny and 1 dime.9. Is C(100, 95) < C(100, 96)? False, because C(100, 95) = C(100, 5) = 100 99 98 97 96 / 5!, which is larger than C(100, 96) = C(100, 4) = 100 99 98 97 / 4!.10. In how many ways may a student receive his grades when taking 4 classes and there are 5 possible grades(A, B, C, D, and F) for each class, and the same grades in different classes are considered different (e.g. “A” in English is different than “A” in Mathematics)? 5 5 5 5 = 54, because there are 5 possible grades for the first class, 5 grades for the second, etc., 5 grades for the 4th class.11. Is ?)2(80102 jkjk True, both sides equal 2 + 3 +…+ 10.12. Let a1, a2, …, an, …, denote an arbitrary sequence of integers (positive, zero, or negative). Then 11 1nknkkkaa. False, because ,111 1 knknkkkaaa but 1kamay be 0.13. Find the value of C(6, 1) + C(6, 2) + C(6, 3) + C(6, 4) + C(6, 5) + C(6, 6). By the formula,2),(0nnkknC for n 0, which implies C(6, 1) + C(6, 2) + …+ C(6, 6) = 26 – C(6, 0) = 26 – 1.Part II. (61 pts.) Computational Questions. (Explain your answer.)14. (20 pts.) Consider positive integers of 6 digits of the form ABCDEF where A is the leftmost digit, and F is the rightmost digit. Count the number of such integers under each of the following restrictions and briefly explain your answer, assuming A 0 for all parts.(a) A 5 and F 3, and duplicated digits are allowed.Answer: There are 5 choices for digit A (i.e., 5, 6, 7, 8, and 9), 10 choices (0 through 9) for each of the digits BCDE, and 4 choices for digit F (0, 1, 2, and 3). Thus, the total count of such numbers is 5 104 4.(b) Suppose the value of the integer is divisible by 10, and no digits are duplicated.Answer: The last digit (digit F) must be zero; there are 9 choices for digit A (i.e., 1 through 9), and there are P(8, 4) = 8 7 6 5 choices for digits BCDE (to avoid duplicates and different than digit A and digit 0). Thus, the total count is 9 8 7 6 5.(c) Suppose each of the 6 digits A through F are between 1 and 4 inclusively, and 1 A B C D E F 4 (thus, duplicated digits are allowed).Answer: There are C(6 + 4 –1, 6) = C(9, 6) = C(9, 3) combinations to choose 6 digits (allowing duplicates) from the 4 (types of) digits 1 through 4. Once these digits are selected, they can only be arranged in one unique way to satisfy an increasing order from left to right.(d) Suppose no digits may be duplicated, and digit 5 is used exactly once (i.e., exactly one of the places A, B, C, D, E, or F, is equal to 5, and all digits are distinct).Answer: (Case 1) Suppose digit A = 5. The number of permutations for the remaining digits is P(9, 5), by choosing 5 (distinct) digits from the digits 0 through 4, plus 6 through 9, then counting the permutations. (Case 2) Suppose A 5. Thus, there are 8 choices for digit A (1 through 4, plus 6 through 9); there are C(5, 1) = 5 possible places for digit 5, and there are P(8, 4) permutations for filling in the remaining 4 digits. The count equals 8 5 P(8, 4). Thus, the sum of the two cases equals P(9, 5) + 8 5 P(8, 4). (e) Suppose digits may be duplicated, while digits 2 and 3 are always used together, that is, each use of 2is (immediately) followed by a 3, and each use of 3 must be (immediately) behind a 2, examples include 623523, 766789, etc.Answer: The basic idea is to treat digits 2 and 3 together as a single entity since they are used together. We consider 4 …
View Full Document
Unlocking...