Exam 2 A. Miller Spring 2005 Math 240 0Show all work.No notes, no books, no calculators, no cell phones, no pagers, no electronic devices of anykind.NameCircle your Discussion Section:DIS 303 12:05p T B235 VAN VLECKDIS 304 12:05p R B235 VAN VLECKDIS 307 2:25p T B139 VAN VLECKDIS 308 2:25p R B309 VAN VLECKProblem Points Score1 102 103 104 105 106 107 108 109 1010 10Total 100Solutions will be posted shortly after the exam: www.math.wisc.edu/∼miller/m240Exam 2 A. Miller Spring 2005 Math 240 11. (10 pts) Let p be a prime. Prove that for any integers a and b thata2≡pb2if and only if a ≡pb or a ≡p−b.a ≡pb stands for a = b mod p, or equivalently, a − b is divisible by p.Exam 2 A. Miller Spring 2005 Math 240 22. (10 pts) N = {1, 2, 3, . . .} is the set of positive integers. A nonempty set X is countable iffthere exists a function f : N → X which is onto. Equivalently, a nonempty set X is countableiff it can be enumerated:X = {x1, x2, x3, . . .}(a) Prove that the set E of even integers is countable. (Note: we include in E the negativeeven integers.)(b) Prove exactly one of the following. If you choose to prove (2) you may assume (1)without proof.1. The set of ordered pairs of natural numbers, N × N, is countable.2. The union of a countable family of countable sets is countable, i.e., if {Xn: n ∈ N} is afamily of sets where each Xnis countable, then X is countable:X =[{Xn: n ∈ N}Exam 2 A. Miller Spring 2005 Math 240 33. (10 pts) Consider a sequence defined by a0= 0, a1= 1 and an= 2an−1+ 3an−2+ n2forn ≥ 2. Write pseudocode for an iterative algorithm to compute f(n) = an. Iterative meansthat the algorithm may use loops (for-next, repeat-until, do-while, etc) but may not call itselfrecursively. Do not use an array to store the values of aifor i < n.Exam 2 A. Miller Spring 2005 Math 240 44. (10 pts) What is the minimum number of people each of whom comes from one of 25 citieswhich guarantees there are at least 9 from the same city?Exam 2 A. Miller Spring 2005 Math 240 55. (10 pts) How many possible ways are there for first, second, third, and last place finishes ina car race with 20 cars? Assume no ties.Exam 2 A. Miller Spring 2005 Math 240 66. (10 pts) What is the coefficient of x3in the expansion of (x − 1)8?Exam 2 A. Miller Spring 2005 Math 240 77. (10 pts) How many ways can 10 cans of soup be put onto 4 distinguishable shelves(a) If the cans are indistinguishable? For example, each can contains the same brand ofchicken noodle soup.(b) If each of the ten cans is a different kind of soup and the position of the cans on theshelves matter?Exam 2 A. Miller Spring 2005 Math 240 88. (10 pts) Suppose that there are 10 sections in a discrete math book and 10 assigned exercisesfrom each section. An instructor randomly chooses 10 of the 100 assigned exercises to base histest on.(a) What is the probability that all 10 chosen exercises come from the same section in thebo ok?(b) What is the probability that each chosen exercise is from a different section in the book?Exam 2 A. Miller Spring 2005 Math 240 99. (10 pts) Find the general solution toan+1− 5an+ 6an−1= 2n + 5(Hint: There should be two arbitrary constants in your solution.)Exam 2 A. Miller Spring 2005 Math 240 1010. (10 pts)(a) Suppose that f(n) = 7f(n/2)+n2whenever n is divisible by 2. Find the general solutionfor the recurrence relation satisfied by ak= f(2k).(b) Suppose that f of part (a) is an increasing function positive function. Estimate the sizeof f(n) using the big-O notation.Exam 2 A. Miller Spring 2005 Math 240 11The following program was used to pick the problems on the test. I combined a couple andchanged the probability problem completely.#! /usr/ucb/pythonimport stringimport sysimport randomf=open("hmwk2",’r’) # input filelines=f.readlines()random.seed("Moe, Larry, and Curly")linenumb=0problems=[]for line in lines:if linenumb > 30:s=string.split(line)if len(s)>0:section=s.pop(0)for prob in s:problems.append(section+"-"+prob.rjust(2))linenumb=linenumb+1random.shuffle(problems)problems=problems[0:12]problems.sort()for prob in problems:print probExam 2 A. Miller Spring 2005 Math 240 12Answers1. The main point is that for a prime p if p divides (a − b)(a + b), then either p divides a − bor p divides a + b.2.(a) {0, 2, −2, 4, −4, . . .}(b) (1) See figure 2 on page 235.(b) (2) Let g : N → N × N be an onto function. Suppose fn: N → Xnis onto for eachn ∈ N. Define the function h : N → X by h(n) = x where x = fi(j) and g(n) = (i, j). It is nothard to see that h is onto.3. The inner code of the loop might look like this:savey = yy = 2y + 3x + z2x = saveyz = z + 1Each iteration of the loop has the effect of ‘shifting’y = an, x = an−1, z = ntoy = an+1, x = an, z = n + 1.4. 2015. 20 · 19 · 18 · 17.6. −567. (a)133(b) 10!1338.(a)1010010(b)1010100109. an= C2n+ D3n+ n + 510.(a) ak= C(7k) + (−13)4kfor an arbitrary constant C.(b) f(n) is O(nc) where c = log2(7) ≈