COT3100C-01, Fall 2002 Oct. 15, 2002, correction onCOT3100C-01, Fall 2002 Oct. 15, 2002, correction on S. Lang Solution Keys to Assignment #3 (40 pts.) 3(c) in red added 10/18, a simpler solution to 2(b) in blueadded 10/281. (12 pts.) Count the number of 7-digit integers under each of the following restrictions:(a) All digits are distinct. (Thus, integers such as 1234567 and 3456980 are counted, but integers such as 2345 and 2233445 are not counted.) Answer: 9 * P(9, 6) = 9*9*8*7*6*5*4, where the first factor 9 counts the choices of a non-zero digit (1 through 9) for the leftmost digit of the 7-digit integer; the factor P(9, 6) counts the number of permutations for the remaining 6 digits of the 7-digit integer.(b) The digits may be repeated (such as 2233456) but the integer must be divisible by 5. (Hint: whatwould be the last, rightmost digit for an integer to be divisible by 5?)Answer: 9 * 105 * 2, where the first factor 9 counts the 9 choices (1 through 9) for the leftmost digit; each of the middle 5 digits can be any of the 10 choices (0 through 9); finally, the rightmostdigit must be either 0 or 5, for two choices, for the integer to be divisible by 5.(c) The digits may be repeated but digit 3 must be used (as part of the integer) at least twice. (Hint: consider the cases: digit 3 used twice, three times, etc., until 7 times, then count each case or group separately. Alternatively, consider the complementary question, i.e, if digit 3 is not used orused exactly once, and count them separately.)Answer: We consider the complementary question. First, we count those 7-digit integers that don’t use digit 3. This count is 8 * 96 because the first digit can have 8 choices (1, 2, 4 through 9), each of the remaining 6 digits has 9 choices (0 though 9 excluding 3). We then count those 7-digit integers that contain digit 3 exactly once. There are two cases: (1) When the leftmost digit is 3. In this case, there are 1 * 96 choices because the first digit is 3 (one choice); each of the 6 remaining digits has 9 choices (0 though 9 excluding 3). (2) When the leftmost digit is not 3. There are 6 choices for the position of digit 3; the leftmost digit has 8 choices (1, 2, 4 through 9), and each of the 5 remaining digits has 9 choices (0 through 2, 4 through 9). Thus, the total count is 6 * 8 * 95.Finally, the count of 7-digit integers that contain digit 3 at least twice = (the total number of 7-digit integers) – (those 7-digit integers where digit 3 is used zero or one times) = 9 * 106 – (8 * 96 + 1 * 96 + 6 * 8 * 95).(d) All digits are distinct, and the digits are in an increasing order when viewed from the leftmost position to the rightmost position. (Thus, integers such as 1234567 and 1245689 are counted, but integers such as 3245678 and 2234579 are not counted.)Answer: Since the leftmost digit is at least 1 (cannot be digit 0), so digit 0 will not be used at all in these integers (where the digits are in increasing order from left to right). The count of these integers is the same as selecting 7 digits out of 9 digits (1 through 9) using the combination formula C(9, 7) = C(9, 2) = 36. Once 7 digits are selected, they can only be arranged in one value in which the digits are in increasing order from left to right.2. (9 pts.) Suppose there are 5 types of coins under consideration: half-dollar, quarter, dime, nickel, andpenny. Count the number of combinations of the coins if there are 4 coins in a pocket, under each ofthe following restrictions:(a) All coins are of distinct types (i.e., no two quarters, etc.)Answer: C(5, 4) = C(5, 1) = 5, which corresponds to choosing 4 out of 5 objects where the orderdoesn’t matter.(b) The coins may be of the same types and there are at least two quarters.Answer: We consider the following cases (groups) for the solutions:(1) The quarters are included exactly twice. There are 4 other types of coins, from which we select 2 coins allowing repetitions. The count is C(2+4–1, 2) = C(5, 2) = 10.(2) The quarters are included exactly 3 times. There are 4 choices for the last coin in the pocket.(3) The quarters are included 4 times. There is only one such possibility.Thus, the total count using the sum rule is 10 + 4 + 1 = 15.(A simpler solution) We could first put two quarters in the pocket, then choose the remaining coins be selecting from 5 types of coins (half-dollar, quarter, dime, nickel, and penny) the remaining two coins. In this way we are guaranteed to have at least two quarters in the pocket. The number of choices of selecting two coins out of 5 types, is C(2+5–1, 2) = C(6, 2) = 15. (c) The coins may be of the same types but there are no half-dollar coins.Answer: This corresponds to choosing 4 out of 4 types allowing repetitions, so the count is C(4+4 –1, 4) = C(7, 4) = C(7, 3) = 35.3. (9 pts.) Suppose there are 50 (distinct) books to be placed on the three shelves of a bookcase (see picture). Count the number of ways the books can be arranged under each of the following restrictions:(a) Place 15 books on each of the top two shelves, then the remaining 20 books on the bottom shelf. The books are arranged in an arbitrary order on each shelf, and different arrangements are counted separately.Answer: 50!, which corresponds to the permutations of 50 objects (in which the first 15 will be on the top shelf, the next 15on the second shelf, and the rest on the bottom shelf).(b) Similar to Part (a) of placing 15 books on each of the top two shelves and 20 on the bottom, but books within the same shelf are arranged in alphabetical order of the titles (assuming all book titles are distinct).Answer: C(50, 15) * C(35, 15) * C(20, 20) = 50! / (15! 15! 20!), which corresponds to choosing 15 outof 50 to be placed on the top shelf; then choosing 15 out of the remaining 35 to be placed on the next shelf, then placing the rest 20 on the bottom shelf. Once the books have been selected for a shelf, there is only one arrangement of them, i.e., in an alphabetical order.(c) Suppose 5 out of the 50 books are over-sized which must be placed on the bottom shelf. The remaining45 books are divided evenly between the three shelves (15 books on each); books are arranged in an arbitrary order on the shelves.Answer: P(45, 15) * P(30, 15) * 20! = (45! / 30!) * (30! / 15!) * 20! = (45! 20!) / 15!, where the first factor P(45, 15) corresponds to choosing 15 books out of the 45 non-oversized books where the order matters (for different arrangements on
View Full Document
Unlocking...