Exam 2 A. Miller Spring 2002 Math 240 0Show all work. Circle your answer.No notes, no books, no calculator, no cell phones, no pagers, no electronic devicesat all.Solutions will be posted shortly after the exam: www.math.wisc.edu/∼miller/m240NameProblem Points Score1 82 83 84 85 86 87 88 89 410 811 812 813 8Total 100Exam 2 A. Miller Spring 2002 Math 240 11. (8 pts) How many strings of 8 ASCII characters contain the character % at leastonce? Note that there are 128 ASCII characters.Exam 2 A. Miller Spring 2002 Math 240 22. (8 pts) Let x be a positive real number and n any positive integer. Show that thereis a positive integer j such that the distance from jx and some integer is ≤1n.Hint: For each j there are integers k and m with 0 ≤ m ≤ n − 1 so thatk +mn≤ jx ≤ k +m + 1nExam 2 A. Miller Spring 2002 Math 240 33. (8 pts) One hundred tickets numbered 1, 2, . . . , 100 are to be sold to 100 differentpeople. Eleven prizes are awarded, a grand prize (a scuba diving trip to the Caribbeanisland of Bonaire), and 10 consolation prizes (a round-trip bus ticket to Milwaukee notincluding taxes or gratuities).How many ways are there to distribute the prizes? Assume each person can win atmost one prize.Exam 2 A. Miller Spring 2002 Math 240 44. (8 pts) Ten sections from a book are to be tested on the second midterm. Eachsection of the book ends with 20 exercises. The instructor randomly chooses oneexercise from each section to put on the exam.(a) What is the probability that every problem chosen is exercise 17?(b) What is the probability that every problem chosen is exercise 17 except exactlyone?Exam 2 A. Miller Spring 2002 Math 240 55. (8 pts) How many strings of decimal digits (0-9) are there of length twenty whichcontain exactly one zero, two ones, and three twos?Exam 2 A. Miller Spring 2002 Math 240 66. (8 pts) Find a recurrence relation for the number, Sn, of decimal (0-9) strings oflength n which contain at least two consecutive digits which are both 9’s.Exam 2 A. Miller Spring 2002 Math 240 77. (8 pts) Determine values of the constants A and B so that an= An + B is aparticular solution of an= an−1− 2an−2+ n.Exam 2 A. Miller Spring 2002 Math 240 88. (8 pts) How many elements are in the union of four sets if the sets have 100,200,300,400elements respectively, each pair of sets has 50 elements in common, each triple has 10elements in common, and there is exactly one element in all four sets?Exam 2 A. Miller Spring 2002 Math 240 99. (4 pts) Suppose that the function f from A to B is a one-to-one correspondence.Let R be the relation that equals the graph of f . That is R = {(a, f(a)) : a ∈ A}.What is R−1?Exam 2 A. Miller Spring 2002 Math 240 1010. (8 pts) LetMR=1 1 01 0 10 1 1represent the relation R. Find a matrix which represents R2= R ◦ R.Exam 2 A. Miller Spring 2002 Math 240 1111. (8 pts) Let R ⊆ {1, 2, 3, 4} × {1, 2, 3, 4} be the following binary relation:R = {(1, 3), (4, 4), (4, 2), (3, 4), (2, 1)}Draw a digraph picture for R. Find a path of length 6 starting at 1 and ending at 2.Exam 2 A. Miller Spring 2002 Math 240 1212. (8 pts) For any n = 2, 3, 4, . . . , 15 define f(n) = p where p is the least prime whichdivides n. Define the relation x ≡ y on this set by x ≡ y iff f(x) = f(y).(a) Prove that ≡ is an equivalence relation on the set {2, 3, 4, . . . , 15}.(b) What are its equivalence classes?Exam 2 A. Miller Spring 2002 Math 240 1313. (8 pts) Draw the Hasse Diagram for the partial order (P ({a, b, c}, ⊆)).Exam 2 A. Miller Spring 2002 Math 240 14Answers1. (4.1 - 17) There are 1288strings all together. 1278strings have no occurence of% in them. Hence 1288− 1278is the number in which % occurs at least once.2. ( 4.2 - 17) The hint is true because for any real number jx there is an integerk with k ≤ jx ≤ k + 1. We then divide the interval [k, k + 1] into n subintervals oflength1nto see that we must have some m.By the pidgeon hole principle we can find j < j0that have the same m as in thehint, i.e.k +mn≤ jx ≤ k +m + 1nk0+mn≤ j0x ≤ k0+m + 1nfor some integers k, k0. This is because there are infinitely many j’s but only n possiblem0s. We claim that (j0− j)x is within1nof the integer k0− k.Since negation reverses inequalities−k −m + 1n≤ −jx ≤ −k −mnSo that adding the last two inequalities we get:k0− k −1n≤ (j0− j)x ≤ k0− k +1nSo (j0− j)x is within1nof the integer k0− k.3. (4.3-17) There are 100 choices for the grand prize. To award the bus tickets wemust then choose 10 tickets out of the remaining 99. Hence the answer is100 ×99104. (4.4- ??)(a) There are 2010possible exams. Only one has problem 17 of each section on it.So12010(b) There are 10 × 19 problems which are not 17. Hence there are 190 exams asdescribed. So19020105. (4.6-17)Exam 2 A. Miller Spring 2002 Math 240 15Choose one digit to be the zero,201two of the remaining to be ones192and three of the remaing to be twos173the other 14 digits can be taken arbitrarilyfrom the 7 digits 3-9. There are 714ways to do this.2011921737146. (5.1-17) The strings of length n + 1 ≥ 3 which contain at least two consecutive9’s can divided as follows. Either thefirst two digits are 99, there are 10n−1such stringsor the first digit is not a 9, there are 9Snsuch stringsor the first digit is a 9 and the second is not, there are 9Sn−1of these.HenceSn+1= 10n−1+ 9Sn+ 9Sn−17. (5.2-25)An + B = A(n − 1) + B − 2(A(n − 2) + B) + nAn + B = An − A + B − 2An + 4A − 2B + nAn + B = (A − 2A + 1)n − A + B + 4A − 2BAn + B = (−A + 1)n − A + B + 4A − 2B0 = (−2A + 1)n + (3A − 2B)For this to be true for every n we must have that −2A + 1 = 0 and 3A − 2B = 0. SoA =12and so B =34. Hence an=12n +348. (5.5-17)100 + 200 + 300 + 400 −4250 +4310 − 1 = 7399. (6.1-17)It is the graph of the inverse function orR−1= {(f(a), a) : a ∈ A}10. (6.3-9)MR2=1 1 11 1 11 1 111. (6.4-16,17)Exam 2 A. Miller Spring 2002 Math 240 161,3,4,4,4,4,2 is a path of length six.12. (6.5-6,17)(a) A relation is an equivalence relation iff it is reflexive, symmetric and transitive.x ≡ x iff f (x) = f (x) so it is reflexivex ≡ y implies f(x) = f(y) implies f (y) = f (x) implies y ≡ x so it …