COT3100 01 Fall 2002 S Lang 10 31 2002 Answer key to Test 2 Nov 4 2002 Part 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 n n 1 by the formula 1 2 n 20100 n n 1 20100 2 200 201 2 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 9 3 2 2 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 10 8 k 2 j 0 11 Is k j 2 True both sides equal 2 3 10 12 Let a1 a2 an denote an arbitrary sequence of integers positive zero or negative Then n 1 n n 1 n k 1 k 1 k 1 k 1 a k a k False because a k a k a k 1 but a k 1 may 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 n n C n k 2 for n 0 which implies C 6 1 C 6 2 C 6 6 26 C 6 0 26 1 k 0 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 2 is 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 cases depending on how many times the combination of digits 2 …
View Full Document
Unlocking...