MATH2800 Introduction to Discrete Structures

Final Exam, Thursday, December 13, 2007.

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. What is the probability that a five card poker hand contains two pairs (that is, two of each of two different kinds and a fifth card of a third kind)?

2. A directed graph $G=(V,E)$ has 8 vertices and 12 directed edges.
   1. We are interested in the out-degrees of the vertices. How many different out-degree sequences are possible? (Assume the order of the vertices is important, so a sequence (2,1,3,1,0,0,3,2) is different from a sequence (3,0,1,0,2,2,1,3). Express your answer in terms of factorials and/or powers of integers.)
   2. Assume each arrangement is equally likely. What is the probability that every vertex has at least one outgoing edge? (Express your answer in terms of factorials and/or powers of integers.)

3. Assume 6 distinct integers are chosen from the first 10 positive integers. Show that there must be a pair of these integers with sum equal to 11.

4. A relation $R$ on a set with five elements has zero-one matrix
   
   $$M_R = \left[ \begin{array}{rrrrr} 0&1&0&0&1 \\ 0&0&1&0&0 \\ 0&0&0&1&0 \\ 0&1&0&0&0 \\ 1&0&0&1&0 \end{array}\right].$$
   
   

   What is the transitive closure of this relation?

5. Let $x$, $y$, and $z$ be variables with domains equal to $\{0,1\}$. Let $p$ be the statement $x=1$. Let $q$ be the statement $y=1$. Let $r$ be the statement $z=1$. Assume the statements $p \vee \neg q$ and $q \vee r$ are true. Show that we must have $x+z \geq 1$.

6. A matching on a graph $G=(V,E)$ is a subset of the edges that do not share any end vertices. Let $a_n$ equal the number of matchings on $K_n$. Show that $a_n=a_{n-1}+(n-1)a_{n-2}$. (For an example of a matching, see question 8.)

   Assume $a_1=1$ and $a_2=2$. Show that if $n \geq 3$ is odd then
   

   $$a_n \geq 2^{\frac{n-1}{2}} (\frac{n-1}{2})!$$
   
   

7. Let $Z\!\!\!\!Z$ denote the set of integers. Which of these relations on the set of all functions from $Z\!\!\!\!Z$ to $Z\!\!\!\!Z$ are equivalence relations? Determine the properties of an equivalence relation that the others lack.
   1. $\{(f,g) \; \vert \; f(1)=g(1)\}$.
   2. $\{(f,g) \; \vert \; f(0)=g(0) \mbox{ or } f(1)=g(1)\}$.
   3. $\{(f,g) \; \vert \; f(x)-g(x) = 1 \; \forall x \in Z\!\!\!\!Z\}$.
   4. $\{(f,g) \; \vert \; f(0)=g(0) \mbox{ and } f(1)=g(1)\}$.

8. A matching on a graph $G=(V,E)$ is a subset of the edges that do not share any end vertices. Consider the graph:
   
   
   

   For example, the set $\{a,e\}$ is a matching, but the set $\{b,c\}$ is not. Note that the empty set and the singleton sets consisting of just a single edge, for example $\{b\}$, are also matchings. Let $S_1$ and $S_2$ be two subsets of the edges that are matchings. The relation $\preceq$ is defined as set inclusion, so $S_1 \preceq S_2$ if and only if $S_1 \subseteq S_2$. This defines a partially ordered set.

   1. Draw the Hasse diagram for this poset.
   2. Give a maximal element of the poset with two edges and another maximal element with three edges.

9. A directed Euler circuit on a directed graph is an Euler circuit that traverses each edge in the correct direction. Let $G=(V,E)$ be the following directed graph.

   
   
   

   Show how the edges can be partitioned into a collection of directed circuits, so each edge appears in exactly one of the circuits. Hence find a directed Euler circuit on the graph.

10. Let $G=(V,E)$ be a connected directed graph. For each vertex $v \in V$, the in-degree is the number of edges entering vertex $v$ and the out-degree is the number of edges leaving vertex $v$. A directed Euler circuit on a directed graph is an Euler circuit that traverses each edge in the correct direction. Prove that $G$ contains a directed Euler circuit if and only if the in-degree of each vertex is equal to its out-degree.

11. Use strong induction to show that every number greater than or equal to 18 can be written as a sum of a nonnegative integer multiple of 4 and a nonnegative integer multiple of 7. (For example, $29=2 \times 4 + 3 \times 7$.)

12. Show that a positive integer is divisible by 3 if and only if the sum of its decimal digits is divisible by 3. (Hint: a number $n$ is divisible by 3 if and only if $n \equiv 0 \; (\mbox{mod } 3)$. You may assume $10^i \equiv 1 \; (\mbox{mod } 3)$ for any nonnegative integer $i$.)