COT3100C 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 blue added 10 28 1 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 what would 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 rightmost digit 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 or used 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 and penny Count the number of combinations of the coins if there are 4 coins in a pocket under each of the 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 order doesn 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 first 15 15 willbooks be onon theeach top of shelf 15 b Similar to Part a the of placing the the top next two shelves and 20 on the bottom but books on the second shelf and the rest on the bottom shelf 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 out of 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 remaining 45 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 …
View Full Document
Unlocking...