MATH2800 Introduction to Discrete Structures

Final Exam, Monday, May 7, 2007.

You may use three sheets of handwritten notes, but no other sources. The exam lasts three hours. The exam consists of twelve questions; 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 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. 1. Use the Euclidean Algorithm to show that 25 and 77 are relatively prime.
   2. Find the inverse of 25 modulo 77.
   3. Find all solutions to the linear congruence
      
      $$25 x \equiv 2 \,\, (\mbox{mod } 77).$$
      
      

2. 1. Prove that there cannot be three consecutive odd integers $\geq 5$ that are all prime.
   2. Let $S$ be a set with $n$ elements. Prove that the number of subsets of $S$ with even cardinality is equal to the number of subsets of $S$ with odd cardinality.

3. The computer science department at Alhambra University rates its graduate program applicants numerically. Six different factors are taken into account, including GRE score, undergraduate GPA, letters of recommendation, and the applicant's experience and desire. These different factors are weighted differently, with the integral weights chosen to add up to 100. The weight for each individual factor is at least 10.

   1. In how many ways could the department choose the weights? (Express your answer in factorials and/or powers of integers.)
   2. Assume all the weighting schemes are equally likely. What is the probability that all the weights are at least 15? (Express your answer in factorials and/or powers of integers.)

4. Professor Jones has determined from historical data that 80% of students who get at least 90% on the first exam get an A in his course, 30% of students who get between 80% and 89% on the first exam get an A in the course, and 10% of students who get less than 80% on the first exam get an A in the course. Fred got an A in the course.

   1. What probability estimate does Professor Jones obtain from Bayes' Theorem that Fred got at least 90% on the first exam, under the assumption that each of the three ranges of scores were equally likely?
   2. What probability estimate does Professor Jones obtain from Bayes' Theorem that Fred got at least 90% on the first exam, under the assumption that a quarter of the students get at least 90% on the first exam, a quarter get between 80% and 89%, and half get less than 80%?

5. The complete graph $K_4$ has vertices $s$, $t$, $u$, and $v$. Two of the edges are selected randomly. Edges incident to $s$ are twice as likely to be picked as the other edges. What is the probability that the two selected edges share an endpoint? (Express your answer as a ratio of two integers whose greatest common divisor is 1.)

6. 1. How many simple paths are there of length 4 in the complete graph $K_{11}$? (Express your answer in factorials and/or powers of integers.)
   2. Choose a direction for each edge of $K_5$ so that the resulting directed graph is strongly connected.

7. Several researchers are interested in determining their Erdös numbers, that is, their distance from Paul Erdös in the collaboration graph. Denoting Erdös by E and the other researchers by A, B, C, F, G, K, L, M, T, and W, the relevant papers are (E, A, L), (E, G), (E, B), (A, F), (F, T), (T, K), (T, M), (G, W), (W, M), (M, K), (L, S), (B, C, S).

   1. Draw the collaboration graph.
   2. Use Dijkstra's algorithm to find the Erdös number of T.

8. Let $G=(V,E)$ be a graph with adjacency matrix $M$. Let $u$ and $v$ be two vertices in $V$ and let $p$ be a positive integer. Prove that there is a path of length exactly $p$ from $u$ to $v$ if and only if the $(u,v)$ entry of $M^p$ is nonzero. (Hint: use induction.)

9. Answer these questions for the poset ( $\{\{1\},\{2\},\{4\},\{1,2\},\{1,4\},\{2,4\},\{3,4\},\{1,3,4\},\{2,3,4\}\},\subseteq$).
   1. Find the maximal elements.
   2. Is there a least element?
   3. Find all upper bounds of $\{\{2\},\{4\}\}$.
   4. Find the greatest lower bound of $\{\{1,3,4\},\{2,3,4\}\}$.

10. Let $A=\{a,b,c,d\}$. Give an example of a relationship on $A$ that is reflexive, symmetric, antisymmetric, and transitive. What are the equivalence classes of your relationship? What is the Hasse diagram of your relationship?

11. The relationship $R$ on a set of five elements can be represented using the matrix
    

    $$M = \left[ \begin{array}{rrrrr} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 ... ...\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \end{array} \right]$$
    
    
    1. What is the reflexive closure $S$ of this relationship?
    2. What is the symmetric closure $T$ of the reflexive closure $S$?
    3. Verify that the relationship $T$ is an equivalence relation. What are the equivalence classes of this relationship?

12. Let $G=(V,E)$ be the following graph:

    
    
    
    1. Show that this graph is planar.
    2. Add one edge to the graph so that it is no longer planar. Justify your answer.