Math 55 Final Exam Thursday May 10 7 00pm 10 00pm This exam is closed book Do not use any books notes or electronic devices Please write in a blue note book with your name the name of your GSI and your section time on the front Each of the 10 problems is worth 10 points for a total of 100 points Answers without justi cation will receive no credit 1 Suppose n 1 is an integer a How many functions are there from the set 1 n to the set 1 2 3 b How many of the functions in part a are injective c How many of the functions in part a are surjective 2 Let G be a simple graph with at least two vertices Show that if G is not connected then the complementary graph G is connected 3 Suppose each of the three vertices of a triangle is colored at random either black or white with equal probability for each color What is the expected number of edges of the triangle that have both endpoints of the same color 4 Give an example of a relation R such that its transitive closure R satis es R R R2 R3 but R 6 R R2 5 Recall that the Fibonacci numbers are de ned by f0 0 f1 1 and fn fn 2 fn 1 for n 2 Prove that f0f1 f1f2 f2n 1f2n f 2 2n for any positive integer n 6 Find the set of all solutions x to the system of congruences x 2 mod 6 and x 3 mod 9 7 Suppose we randomly choose nonnegative integers x1 x2 x3 and x4 that solve the equation x1 x2 x3 x4 8 Here we assume that each solution has an equal probability of being chosen Given that at least one of x1 and x2 is equal to 1 what is the probability that x1 1 8 Solve the recurrence relation an 2an 1 an 2 2an 3 with initial conditions a0 1 a1 0 and a2 7 9 Give a recursive de nition of the set of bit strings that have the same number of zeros and ones 10 Use generating functions to determine the number of dif ferent ways 10 identical balloons can be given to four chil dren if each child receives at least two balloons Note The children are distinguishable
View Full Document
Unlocking...