Exam (elaborations) TEST BANK FOR Discrete and Combinatorial Mathematics 5th Edition By Ralph P. Grimaldi (Instructor's Solution Manual) INSTRUCTOR'S
... [Show More] SOLUTIONS MANUAL DISCRETE AND COMBINAtORIAL MATHEMATICS FIFTH EDITION Ralph P. Gritnaldi Rose-Hulman Institute o/Technology Boston San Fra.'1cisco New York London Toronto Sydney Tokyo Madrid Mexico City Munich Paris Town Dedicated to the memory of Nellie and Glen /Fuzzy/ Shidler CONTENTS PART 1 FUNDAMENTALS OF DISCRETE Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 PART 2 Fundamental Principles Counting :Fundamentals of Logic Set Theory Properties of the Integel's: Mathematical Induction Relations and Functions Languages: Finite State Machines Relations: The Second Time Around FURTHER TOPICS IN ENUMERATION Chapter 8 Chapter 9 Chapter 10 The Principle of Inclusion and Exclusion Generating Functions Recurrence Relations GRAPH 1.'HEORY AND APPLICATIONS 1 3 26 59 95 134 167 179 207 209 229 243 281 4: Chapter 14 Riugs and Modular Arithmetic 369 Chapter 15 Boolean Algebra and Switching Functions 396 Chapter 16 Groups, Coding Theory, and Polya's Method. 413 Enumeration Chapter Fini te Fields and Comhinatorial Designs 440 THE APPENDICES 459 Appendix 1 Exponential and Logarithmic Functions 461 Appendix 2 Properties of Matrices 464 Appendix 3 Countable and Uncountable Sets 468 PART 1 FUNDAMENTALS OF DISCRETE MATHEMATICS CHAPTER 1 Sections and 1. ( a) By the rule of sum, there are 8 5 = 13 for the eventual winner. (b) Sim~e there are eight Republica,ns and Democrats, the rule of product we have 8 X 5 ::;:;; 40 possible pairs of opposing candidates. (c) The rule of sum in part (a); the rule of product in part (b). 2. By the rule of product there are 5 x 5 x 5 x 5 x 5 x 5 = 56 license plates where the first two symbols are vowels and the last four are even digits. 3. By the rule of product there are (a) 4 X 12 X 3 x 2 = 288 distinct Buicks that can be manufactured. Of these, (b) 4 x 1 x 3 x 2 = 24 are blue. 4. ( a) From the rule of product there are 10 X 9 X 8 X 7 = P( 10, 4) = 5040 possible slates. (b) (i) There are 3 x 9 x 8 x 7 = 1512 slates where a physician is nominated for president. (ii) The number of slates with exactly one physician appearing is 4 x [3 x 7 x 6 x 5] = 2520. (iii) There are 7 x 6 x 5 x 4 = 840 slates where no physician is nominated for any of the four offices. Consequently, 5040 - 840 = 4200 slates include at least one physician. 5. Based on the evidence supplied by Jennifer and Tiffany, from the rule of product we find that there are 2 x 2 x 1 x 10 x 10 x 2 = 800 different license plates. 6. (a) Here we are dealing with the permutations of 30 objects (the runners) taken 8 (the first eight finishing positions) at a trophies can be awarded in P(SO,S) = 30!/22! ways. (b) .n.!.Hl>en;(:!, and runners in 6 ways. each these 6 ways, there are P(28,6) ways for the other 6 finishers (in the top 8) to finish the race. the are 6· to with two runners a.U:lon,~ the top are (a.) 12! re31~nCl"lOl,LI); (b) (4!)( 8!) ways so that the four ..... ,." ..... "' ... and (c) (4!)(51)(3!) where the top .,..""",.,. ... tare PT(:JCe:8SE:<1 3 9. (a) (14)(12) = 168 (b) (14)(12)(6)(18) = 18,144 (c) (8)(18)(6)(3)(14)(12)(14)(12) = 73,156,608 10. Consider one such arrangement - say we have three books on one shelf and on the other. This can be accomplished 15! ways. fact for any subdivision (resulting in two nonempty shelves) of the 15 books we get 15! ways to arrange the books on the two shelves. Since there are 14 ways to subdivide the books so that each shelf has at least one book, the total number of ways in which Pamela can arrange her books in this manner is (14)(15!). 11. ( a) There are four roads from town A to town B and three roads from town B to town C, so by the rule of product there are 4 x 3 = 12 roads from A to C that pass through B. Since there are two roads from A to C directly, there are 12 + 2 = 14 ways in which Linda can make the trip from A to C. (b) Using the result from part (a), together with the rule of product, we find that there are 14 X 14 = 196 different round trips (from A to C and back to A). (c) Here there are 14 x 13 = 182 round trips. 12. (1) a,c,t (2) a,t,c (3) c,a,t (4) c,t,a (5) t,a,c (6) t,c,a 13. (a) 8! = P(8, 8) (b) 71 6! 14. (a) P(7,2) = 7!/(7 - 2)! = 7!/5! = (7)(6) = 42 (b) P(8,4) = 8!/(8 - 4)! = 8!/4! = (8)(7)(6)(5) = 1680 (c) P(lO, 7) = 10!/(1O - 7)! = 101/3! = (10)(9)(8)(7)(6)(5)(4) = 604,800 (d) P(12, 3) = 12!/(12 - 3)! == 12!/9! = (12)(11)(10) = 1320 15. Here we must place a,b,c,d in the positions denoted by x: e A e A e A e A e. By the rule of product there are 4! ways to do this. 16. (a) With repetitions allowed there are 4025 distinct messages. 20. (b) By the rule of product there are 40 x 30 x 30 x ... x 30 x 30 x 40 = (402)(3023) messages. Class (21 - 2)(224 - 2) = 2,1 928,964 Class B: 214(216 - 2) = 1,073,709,056 C: = 532, 608 system. (a) 7! == 5040 (3!)(5)( 4!) = (b) 4 x 3 x 3 x 2 x 2 x 1 x 1 = Since are three A's, there are 8l/3! = arrangements. 4 (b) Here we arrange the six symbols D,T,G,R,M, AAA in 6! = 720 21. (a) 121/(3!2!2!2!) (b) [11!/(3!2!212!)] (for AG) + [11!/(31212!2!)] (for GA) (c) Consider one where the are adjacent: S,C,L,G,C,L, OIOOIA. These seven symbols can be arranged in (7!)/(2!21) ways. Since O,O,O,I,I,A can be arranged in (6!)/(3!2!) ways, the number of arrangements with all vowels adjacent is [7!/(2!2!)}[61/(3!2!)]. 22. (Case 1: leading digit is 5) (6!)/(21) (Case 2: The leading digit is 6) (6!)/(2!)2 (Case 3: leading digit is 7) (61)/(21)2 In total there are (6!)/(2!)][1 + (1/2) + (1/2)J = 6! = 720 such positive integers n. 23. Here the solution is the number of ways we can arrange 12 objects - 4 the first type, 3 of the second, 2 of the third, and 3 of the fourth. There are 12!/( 4!3t2!31) = 277,200 ways. 24. Pen + 1,r) = {n + l)!/(n 1- 1')1 = [en + l)/Cn 1 - r)] . [nt/en - 1')IJ = fen + 1)/Cn 1- r)]P(n,r). 25. ( a) n = 10 (b) n = 5 (c) 2nl/(n - 2)1 + 50 = (2n)!/(2n - 2)! =} 2n(n -1) + 50 = (2n)(2n -1) =} n 2 = 25 =} n=5. 26. Any such path fro:m, (0,0) to (7,7) or from (2,7) to (9,14) is an arrangement of 7 R's and 7 U's. There are (141)/(7!7!) such arrangements. In general I for m, n nonnegative integers, and any real numbers a, b, the number of such paths from (a, b) to (a + m, b n) is (m n)!/{m!n!). 21. (a) path consists 2 1 V, and 7 A's. There are 10!/(2!1!7!) ways to arrange these 10 letters and this is the number of paths. numbers and m~ n, and p are nonnegative integers, bj to (a m,b+ c +n times, while those for j and k are py';·rut.PI'I 10-5+ 1 = 6 o ) we the instrudio:o.s in. k ............ '1-'''', resPei:trv'elY, 5 29. (3) & (b) By rrue product print statement is executed x 6 x 8 = 576 times. five '.<>1'.1':,0,..., X 1 x 1 x 1 = 263 x1x1= letters. are 26x26x (b) When letters may not appear more than two times, there are 26 x 25 x 24 = 15,600 palindromes for either five or six letters. 31. By rule product are (a) 9 X 9 X 8 x 7 x 6 x 5 = 136,080 six-digit integers with no leading zeros and no repeated digit. (b) When digits may he repeated there are 9 X 105 such six-digit integers. (i) (a) (9 x 8 x 7 x 6 x 5 x 1) (for the integers euding in 0) (8 x 8 x 7 x 6 x 5 x 4) (for the integers ending in 2,4,6, or 8) = 68,800. (b) When the digits may be repeated there are 9 x 10 x 10 x 10 x 10 x 5 = 450,000 six-digit even integers. (ii) (a) (9 X 8 x 7 x 6 x 5 x 1) (for the integers ending in 0) + (8 x 8 x 7 X 6 x 5 x 1) (for the integers ending in 5) = 28,560. (b) 9 x 10 x 10 x 10 x 10 x 2 = 180,000. (iii) We use the fact that an integer is divisible by 4 if only if the integer formed by the last. two digits is divisible by 4. (a) (8 x 7 x 6 x 5 x 6) (last two digits are 04, 08, 20, 40, 60, or 80) + (7 x 7 x 6 x 5 x 16) (last two digits are 12, 16, 24, 28, 32, 36, 48, 52, 56, 64, 68, 72, 76, 84, 92, or 96) = 33,600. (b) 9 x 10 x 10 x 10 x 25 = 225, O~~. 32. (a) For positive integers n, k, where n = 3k, n!/(3!)k is the number of ways to arrange the n objects Xl! Xt, Xb Xz, X2, X2,' .• ,Xk, Xk, XI;. This must be an integer. (b) If n,k are positive integers with n = mk, then n!/(m!)" is an integer. 33. (a) With 2 choices per question there are 210 = 1024 to answer the examination. (b) Now there are 3 choices per question and 310 ways. 34. (41/2!) (No 7'8) (4!) (One 7 and one 3) + (2)(4!/21) (One 7 all.d two 3's) (4!/2!) (Two 7'13 and no 3's) (2)(41/20 (Two 7'8 and one 3) + (41/(2121» (Two 7'8 and two 3'15). The total gives us 1.02 such four-digit Intc~l!elrS (a) 6! 36. Aon 6 38. The nine women can be situated around the table in 8! Each such arrangement 39. 1. 2. provides nine spaces (between women) where °a man can placed. VVe can of these places situate a man each of them (:)6! = {). 8 . 7· 6 . 5· 4 ways. Consequently, seating arrangements the 18 (:) 6! = 2,438, 553, 600. SumOfFad( i, sum: positive integers; j,k: nonnegative integers; factorial: array [0 .. 9] of positive integers) begin factorial [0] := 1 for i := 1 to 9 do factorial [~1 : = i * factorial [i - 1] for i := 1 to 9 do for j := 0 to 9 do end for k := 0 to 9 do begin sum := factorial [iJ + factorial [y] factorial [kl if (100 :+: i + 10 * j + k) = sum then print (100 * i + 10 * j + k) end The unique answer is 145 since (II) + (41) + (5!) = 1 24 120 = 145. Sedion 1.3 -- -- - -. a b b c c e a c b d c f a d b e d e a e b f d f a f c d e f Order is not relevant can selection in 5 - = (10)(9)(8)(7)/(4)(3)(2)(1) = 210 (b) = 12!/(7!5!) == (12)(11)( 7 ways. (c) C(14, = 14!j(1212!) = (14)(13)!{2)(1) c::; 91 (d) G!) = 151/(10!51) = (15)(14)(13)(12)(11)/(5)(4)(3)(2)(1) = 3003 4. (a) -1= + (:) (:) = 31 5. (a) are peS,3) = S!j(5 - = 51/2! = (5)(4)(3) = 60 permutations size 3 for the 6. five letters l, a, f, and t. (b) There are C(5, 3) = S!j[3!{5 - 3)IJ = 5!/(312!) = combinations of size 3 for the five letters m, l', a, f, and t. They are a,f,m a,r ,t a,f,r f,m,r a,f,t f,m,t a,m,r f,r,t a,m,t m,r,t (;) (n ~ 1) = (~)(n)(n _ 1) (~)(n - l)(n - 2) = (~)(n -l)[n + (n - 2)J = n)(n - 1)(2n - 2) = (n - 1)2. 7. (a) (~) (b)eaO) (~) 11. (c) C20) G~)(2 women) (~O) (~O) (4 women) ... + G~) e!O) (10 women) = Ef=l (;~) (121~2i) (d) e:) C50) (7 women) + (~O) (::) (8 women) + e:) (~) (9 women) + G~) (;0) (10 women) = C?) (l;~i)' (e) E!!s eiO) (li~i) (b) (!) (~8) (c) e1 3) (!) (~) (d) (:) (;) (f) (~3) (!) C12) (~) = 3744 (Division by 2 is needed since no distinction is made for the order are result 54, = 1 (!) (~) -3744 = + , r, 1 S (:) (four six) = (15)(4) ways. set G) ways. vOllSe~ i;;;;;l + 1 )' + 1, one + 9 -- 2--1 0+1 + (;~) - an even locations for (~~) ways for 0 < i < 5. Then for the positions selected there are tvvo choices; for the 10 - . 'C.u,~C:WJ,,,,.uJ'5 positions there are also two choices - 1,3. 20. (a) We can select 3 vertices from A, B, C, D, E, F, G, H in (:) ways, so there are (:) = 56 distinct inscribed triangles. (b) (:) = 70 quadrilaterals. (c) total number of polygons is (~) (:) (:) (:) (~) + (:) = 28 - [(~) (~) + (~) J = 256 - [1 8 + 28] = 219. 21. There are (;) triangles if sides of the n-gon may be used. Of (;) triangles, when n 4 there al'e n triangles that use two sides of the n-gon and n(n - 4) trian~les that use only one side. So if the sides of the n-gon cannot be used, then there are G) - n - n( n - 4), n 2 4, triangles. 22. (a) From the rule of product it follows that there are 4 x 4 x 6 = 96 terms in the complete expansion of (a + b + c + d)( e f 9 + h)( 'It + V w x y + z). (b) The terms bvx and egu do not occur as summands in this expansion. 23. (a) en (b) e~2)(23) (c) Let a = 2x and b = -3y. By the binomial theorem the coefficient of a9b3 in the expansion of (a + b)12 is (~). But e;n a9b3= (~2)(2x)9(_3y)3= (~)(29)(_3)3x9y3,so the cient of x9y3 is e:)(29 )( _3)3, (a) (1'~'2) = 12 ( 4. ) - 12 0,1,1,2 - (c) (1,i,2)(!~)( -1)( -1)2 = (d) (1,:,2)<-2)(3)2 = -216 (3,2~1,Z) (d) 4/' TO 1 1 n (n) 28. a) E =- = f E . =2n/nl i=O n! n·i=o ; 1 n . (n) 1 =- = f E(--lt : = - n. i=O ~ 29. ( m+n) _ (m+n)! _ (m+n)! _ n m - n m!n! - m!(n-l)! - ( 1) (m+n)! ( 1) (m+",)! ( m (m+1)(m!)(n-l)! = m (m+l)!(n-l)! = m (m+n) m+l The sum is the binomial expansion of + 2)n = 3"', 31. (a) 1=[(1 x)- =(1+x)n_-(7) 1 x)n-1 (;)x2(1 x)",-2_ ... ( [Show Less]