A

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.

1. Solve the congruence 11x ≡ 1 (mod 24).
2. A bag contains pink, yellow, and green balls. To be sure of withdrawing at least 2 pink balls you must take at least 12 balls. To be sure of withdrawing at least 2 yellow balls you must take at least 8 balls. To be sure of withdrawing at least 2 green balls you must take at least 14 balls. How many balls of each color are in the bag?

3. Can there be a simple graph with n vertices all of different degrees? Explain.

4. Dora has a coin that she suspects with probability might be biased. If the coin is biased it has a probability of of returning a head and only of returning a tail. Dora tosses the coin four times, obtaining three heads and one tail. How should Dora use this additional information to adjust her prior belief that the coin is biased with probability ?

5. Give an example of a graph that has an Euler circuit but not a Hamiltonian circuit, and give an example of a graph that has a Hamiltonian circuit but not an Euler circuit. Justify your answer.

6. Let R be a symmetric and transitive relation on a set A. Assume for every a A there exists b A with aRb. Prove that R is an equivalence relation.

7. Jim is a minor league pitcher. His starts can be divided into four categories:

   1. He gives up no runs.
   2. He gives up one or two runs.
   3. He gives up three or four runs.
   4. He gives up at least five runs.

   Jim makes ten starts during the season. In how many ways can the number of runs be distributed? (Assume the order of the starts is irrelevant. Express your answer in factorials and/or powers of integers.)

   Assuming each outcome for the season is equally likely, what is probability that Jim pitches at least three shutouts? (A shutout is when Jim gives up no runs. Express your answer in factorials and/or powers of integers.)

8. Answer these questions for the poset

   
   1. Find the maximal elements.
   2. Find the minimal elements.
   3. Is there a greatest element?
   4. Find the least upper bound of {{2},{4}}.
   5. Find the greatest lower bound of {{1, 3, 4},{2, 3, 4}}.
9. 1. Show that if A and B are sets then A - B = A ∩.
   2. Let A and B be independent events, with A having probability 0.6 and B having probability 0.3. What is the probability of A - B?
10. Let G be a graph with n vertices and let u and v be distinct vertices of G. Prove that if there is a walk from u to v then there is a walk from u to v that has length less than or equal to n - 1.
11. Use proof by contradiction to show that every integer greater than 11 is the sum of two composite numbers. (Hint: Let p ≥ 12 and let q = p - 6. If q is prime, look at numbers near q. Recall that a number n is composite if n > 1 and n is not prime.)
12. Prove that a_n = 2ⁿ(2 + n² + n³∕6) is a solution to the recurrence relation a _n = 4a_n-1 - 4a_n-2 + (n + 1)2ⁿ for n ≥ 2 when a₀ = 2 and a₁ = 6.