You may use three sheets of handwritten notes, but no other sources. The exam lasts three hours. The exam consists of twelve questions. Answer at least two of questions 10, 11, and 12; your score will be the total of your ten best questions. Each question is worth ten points. You can work all twelve problems. You need to work at least ten problems, including at least two of problems 10, 11, and 12, to score over 90% on the exam. Please show all work clearly and in reasonable detail. Answers without appropriate supporting work or requested explanations may not receive full credit. No calculators are allowed. Please ring your section below:

1. Let A := {a,b,c,d,e} and let the relation R on A be given by

   Find the transitive closure of the relation.

2. 1. Prove that 179 is prime.
   2. Solve the congruence 24x ≡ 3 (mod 71).
3. Let G = (V,E) be the following undirected simple graph:

   

   The edge lengths w_ij in this graph are given. For which three vertices v V \{a} do we know the length of the shortest path from a to v, after 3 iterations of Dijkstra’s algorithm?

4. In each part, either give an example of a simple graph meeting the given criteria, or explain why no such graph can exist.

   1. The degree list of G is (4, 2, 2, 1, 1) and G is bipartite.
   2. G has a chromatic number of 4 and is non-planar.

5. The recurrence relation

   

   satisfies a₀ = -1 and a₁ = 7. What is a₂? Find the solution to the recurrence relation.

6. Three children are competing for 10 prizes. Each child is equally likely to win each prize. What is the probability that at least one of the children does not win any of the prizes? (Express your answer in terms of factorials and/or powers of integers.)

7. Let p, q, and r be propositions. Are the statements (p → q) ∧ r and (p ∧ r) → q equivalent?
8. Twelve questions on an exam are distributed among four different topics, A, B, C, and D. (In each part, express your answer in terms of factorials and/or powers of integers.)
   1. In how many ways can the questions be distributed so that at least one question is given on each topic?
   2. Given that there is at least one question on each topic, what is the probability that no more than two questions are asked about topic D? (Assume that each topic is equally likely.)
9. How many nonzero entries does the matrix representing the relation R on A = {1, 2, 3,…, 100} consisting of the first 100 positive integers have if R is
   1. {(a,b) |a > b}?
   2. {(a,b) |a = b + 1}?
   3. {(a,b) |ab = 1}?
10. Show that if n ≥ 2 is a positive integer then

    where the sum is taken over all nonempty subsets of the set of the n smallest positive integers. (Hint: Use induction.)

11. Suppose that A and B are events in a sample space, with P(A) = 0.4, P(B) = 0.25, and P(A|B) = 0.3. What is P(A|B^c), where B^c is the complement of B? (You can express your answer as products and/or ratios of decimals.)
12. Four colleagues Kim, Frank, Joey, and David are going out to dinner. Only Kim has a car, which only has space for one passenger, so she will have to ferry her colleagues one-by-one to the restaurant. Kim has shared a secret with Frank, but she doesn’t want Joey or David to learn this secret. However, if Frank is left alone with either Joey or David then he will divulge the secret. So Kim needs to develop a plan to get the four of them to the restaurant, while making sure that Frank is not left alone with either Joey or David. Each state can be described by listing who is still at work and who is at the restaurant, so for example the initial state is represented by (KFJD,∅), and having Kim and Frank at work while Joey and David are at the restaurant is represented by (KF,JD).
    1. Construct a graph so that each vertex represents an allowable state and where edges represent possible transitions from one state to another.
    2. Find a path in this graph that solves Kim’s problem.