CS206 – Discrete Structures II Midterm Exam – Section 01 & 02 – Fall 2015 Name: Student I.D.: 1 https://www.coursehero.com/file/13445843/mid-F15Solutions/ Th is s tud y r eso urc e w as sha red vi a C ou rse He ro. com Answer Key for Exam A 2 https://www.coursehero.com/file/13445843/mid-F15Solutions/ Th is s tud y r eso urc e w as sha red vi a C ou rse He ro. com Problems • This test is CLOSED book, CLOSED notes, NO calculators, NO cheat sheets. • You have 1:20 hours to answer the questions. • Answer all problems in as thorough detail as possible. Be sure to include all your work. Partial credit will be given even if the answer is not fully correct. • For combinatorial questions clearly specify the tasks, whether you used the sum or the product (or some other) rule, and justify how you came up with the answer. Do not just write down the final number. • You can use both sides of the test book to write your answers. • The number of points assigned to a question (roughly) indicates the question’s di culty. Use this as a guide in allocating your time. • The perfect score is 180. Any points you score over 180 will be considered extra credit. 3 https://www.coursehero.com/file/13445843/mid-F15Solutions/ Th is s tud y r eso urc e w as sha red vi a C ou rse He ro. com 1. [40 pts] Find the coe cient of xk in the expansion of (x 1)17(x+1)18 in the simplest possible form. Answer: One may approach the problem in the following two ways. (a) (Not recommended.) Expand the binomials individually, then form the product of two poly- nomials and collect coe cients of the same power: (x 1)17(x+ 1)18 = 17X i=0 C(17, i)xi !0@ 18X j=0 C(18, j)xj( 1)18 j 1A (1) = 17X i=0 18X j=0 C(17, i)C(18, j)( 1)jxi+j (2) = 35X k=0 0@L(k)X l=0 C(17, k l)C(18, l)( 1)l 1Axk, (3) where L(k) is the total number of entries corresponding to power k. We know that this can be computed as the number of integers solutions of i + j = k, which is C(k + 1, 1) = k + 1. However, it is not immediately obvious what that inner sum (representing the coe cient of xk) would reduce to. So this won’t results in a simple, compact form. (b) (Recommended.) Notice that in the product of the two binomials there are 17 pairs (x 1)(x+ 1) = (x2 1). So the product can be written as: (x 1)17(x+ 1)18 = (x2 1)17(x+ 1) = (x+ 1) 17X l=0 C(17, l)x2l( 1)17 l (4) = (x+ 1) 17X l=0 C(17, l)x2l( 1)l+1 (5) = 17X i=0 C(17, i)x2i+1( 1)i+1 + 17X j=0 C(17, j)x2j( 1)j+1. (6) Notice that the first term has only the odd powers of x, i.e., x1, x3, . . . , x35 and the second term has only the even powers of x, i.e., x0, x2, . . . , x34. So the expression can be written as a single polynomial 35X k=0 C(17, bk/2c)( 1)bk/2c+1xk. 4 https://www.coursehero.com/file/13445843/mid-F15Solutions/ Th is s tud y r eso urc e as sha red vi a C ou rse He ro. com 2. [25 pts] How many solutions are there to the inequality x1 + x2 + x3 15, where x1, x2, and x3 are nonnegative integers? Answer: Introducing an auxiliary integer variable x4 0, the problem becomes that of finding the number of possible solutions for equation x1+x2+x3+x4 = 15 instead of the inequality because x4 > 0 implies x1+x2+x3 15. Note that any xi can be zero, including x4. Recall now that this is equivalent to the problem of distributing 15 identical objects into 4 boxes (or equivalently, divide 15 objects into groups with 3 separators): C(4+151, 15) = C(15+4 1, 4 1) = C(18, 3) = C(18, 15). 5 https://www.coursehero.com/file/13445843/mid-F15Solutions/ Th is s tud y r eso urc e w as sha red vi a C ou rse He ro. com 3. [60 pts] How many di↵erent strings can be made from the letters of word ”rutgers”: (a) [20 pts] Using four characters (i.e, strings of length four)? (b) [10 pts] Using all seven characters, when the letter u always comes right after the letter r? (c) [30 pts] Using all seven characters, when the letter u comes after the last letter r? Answer: (a) There are three mutually exclusive cases to consider: (a) among the 4 characters there are no r ’s; (b) there is only one r among the four; and (c) there are two r ’s among the four. In the first case there are C(5, 4) ways of selecting the four characters and 4! ways of ordering them, resulting in C(5, 4)⇥ 4! = 5! strings. In the second case, once an r is selected there are C(5, 3) ways of selecting the remaining three characters, and then 4! ways of ordering the four di↵erent letters. Hence, C(5, 3) ⇥ 4! = 5!/(3!2!)4! di↵erent strings. In the third case, there are C(5, 2) ways of selecting the two non-r characters from the set of five, then 4!/2! ways of ordering them (because the two r ’s are identical). Hence, C(5, 2)⇥4!/2! di↵erent strings. The total number of di↵erent strings is (C(5, 4)+C(5, 3)+C(5, 2)/2)4! = (5+10+5)4! = 20⇥ 4!. (b) We can consider r and u as one block, ru. Then the number of ways to permute the 6 symbols {ru, t, g, e, r, s} is 6! = 30⇥ 4!. (c) This is a bit complicated by the fact that there are two r ’s here. One way to solve the problem is to consider the set of three key letters, {r, r, u}, in that (valid) order and then consider the assignment of positions to those letters. It is convenient to start with the placement of the middle r. This letter can be placed in one of 5 positions of the 7-character string, with the two remaining positions reserved for the first r and the trailing u. For each placement in position k = 2, 3, . . . , 6, the first r can be placed in positions 1, 2, . . . , k 1, i.e., the total of k 1 positions. The trailing u can be placed in positions k + 1, k + 2, . . . , 7. So we haveP6 k=2(k 1)⇥ (7 k) = 1⇥ 5 + 2⇥ 4 + 3⇥ 3 + 4⇥ 2 + 5⇥ 1 = 35 di↵erent valid placements of the three characters in a string of length 7. The other 7 3 = 4 characters can be placed in any order, creating the complete string. Therefore, we have a total of 35⇥ 4! strings. 6 https://www.coursehero.com/file/13445843/mid-F15Solutions/ Th is s tud y r eso urc e w s sha red vi a C ou rse He ro. com 4. [25 pts] In the computer science department of the University of South Pole, there are 2 professors and 5 teaching assistants (TAs). Each professor should teach exactly one distinct course every semester. Each TA should be assigned to exactly one course. Each course must have at least one TA assigned. How many ways can the TAs be assigned to professors for a semester (a) [10 pts] If no professor is allowed to have more than two TAs? (b) [15 pts] If no professor is allowed to have more than three TAs? Answer: (a) Given 2 professors, we have 4 slots for the TAs. Since we have 5 TAs, it is impossible to find a way to assign the TAs. (b) This corresponds to finding the number of ”onto” mappings from the set of 5 onto the set of 2 elements. Partitioning of 5 TAs into two classes (professors) can be done in S(5, 2) ways, where S(·, ·) is the Stirling number of the 2nd kind. Since the professors are distinct, there are S(5, 2)⇥ 2! = 15⇥ 2 = 30 ways of making these assignments. 7 https://www.coursehero.com/file/13445843/mid-F15Solutions/ Th is s tud y r eso urc e w as sha red vi a C ou rse He ro. com 5. [60 pts] You are playing the game of Bridge. (Bridge is played with an ordinary deck of 52 cards, 13 in each of 4 suites, and each of 4 players is dealt 13 cards.) The cards are dealt perfectly randomly from the deck (i.e., no cheating). (a) [5 pts] What is the total number of ways to be dealt a bridge hand? (b) [10 pts] In how many ways can one be dealt a hand (13 card) of one suite? (c) [5 pts] What are the odds of being dealt a hand of one suite? (The odds are defined as the ratio of the number of ways to be dealt a hand of one suite to the number of ways to be dealt a bridge hand.) (d) [5 pts] What is the total number of possible bridge hands? (Note that here we only care about the hand itself, not the way it was dealt.) (e) [10 pts] What is the total number of hands of one suite? (f) [5 pts] What is the ratio of the number of hands of one suite and the number of general bridge hands? (g) [10 pts] Compare your answers in (c) and (f). Justify intuitively the relationship bet
ween those two answers. (h) [10 pts] You are asked to numerically compute the odds of being dealt a hand of one suite. How would you compute this ratio with the highest possible precision? Clearly describe the steps in this process and justify why the resulting process would yield the highest precision. Answer: (a) The total number of dealing a bridge hand is (52)13 = P (52, 13) = 52⇥ 51⇥ . . .⇥ 40 = 52!/39!. (b) The total number of ways of dealing a hand of one suite is 52⇥12⇥11⇥. . .⇥2⇥1 = 52⇥12! = 52 ⇥ P (12) because you can first deal any card and then all subsequent cards should be of the same suite as the first card. The ordering matters, so these are permutations. (c) The odds of being dealt a hand of one suite is 52 ⇥ 12!/(52!/39!) = 12!39!/51!. These are permutations again. (d) We are now talking about combinations since only the final ”configuration” of the hand is what matters (not the way it was dealt). Hence, the total number of bridge hands is 52 13 = 52!/(13!39!). (e) Again, these are combinations, given the choice of the suite. The total number of hands of the same suite is 4 13 13 = 4. (f) The odds are 4/(52!/(13!39!)) = 12!39!/51!. (g) The two ways of sampling result in the same odds. This is not surprising because the odds only depend on the final configuration of the hand, not the way it was dealt. (h) You will need to compute 12!39!/51! = 12!/(52⇥ 51⇥ . . .⇥ 40). Clearly, certain terms could be cancelled out ahead of time. In general, however, you would be computing the log of the expression as log(12!39!/51!) = log(12!) + log(39!) log(51!). Each log factorial can be computed as log(n!) = Pn i=2 log(i) with high accuracy. The expression can then be evaluated in the log domain and, if necessary, transformed back into the ”linear” (original) domain. 8 https://www.coursehero.com/file/13445843/mid-F15Solutions/ Th is s tud y r es urc e w as sha red vi a C ou rse He ro. com Powered by TCPDF (www.tcpdf.org)
