MAT282 Introduction to Discrete Mathematics
Final Exam, Wed 24 Jan. 2001, 8-12 a.m.

1. Draw a Hasse diagram of the partially ordered set $(D_{60}, \vert)$, formed by the integer divisors of number 60, $D_{60} = \{d \in \mathbf{N}\;:\; d \vert 60\}$, ordered according to the integer divisibility relation: $m\vert n$ if $m$ is a factor of $n$.

2. A final exam contains 5 problems whose grading should be allocated among 3 graders (A, B, C) so that each grader is responsible for at least one problem. In how many ways can the partitioning of the problems be done, when:
   1. The numbering of the problems is not significant, so that the only thing to consider is how many problems are allocated to each of A, B, C.
   2. The numbering of the problems is important, but it does not matter who is responsible for which set of problems.
   3. Both the numbering of the problems and the graders' identities are taken into consideration.

3. A final exam contains 5 problems, each of which is worth 0-12 points. In how many ways can one reach an exact total of 30 points in the exam, under the condition that one must get at least 1 point from each problem? (The numbering of the problems is significant, so that e.g. the result 1-2-3-12-12 is considered to be different from 12-12-3-2-1.) -- If you don't have a calculator with you, providing the appropriate binomial coefficient formula suffices.

4. Prove that a connected graph $G = (V, E)$, $\vert V\vert \geq 2$, is bipartite (i.e. $\chi(G)=2$), if and only if $G$ doesn't contain odd cycles, i.e. if no subgraph of $G$ is of the form $C_{2k+1}$, $k \geq 1$.

5. A derangement on $n$ elements is a permutation $\sigma: \{1,\dots,n\} \rightarrow \{1,\dots,n\}$, such that $\sigma(i) \neq i$ for all $i = 1,\dots,n$. Prove, using the principle of inclusion and exclusion, that the number of $n$-element derangements equals
   
   $$d_n = n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\dots +(-1)^n\frac{1}{n!}\right).$$
   
   
   (Additional information, unrelated to solving the problem: The formula shows that the number of derangements quickly approaches $n!\,e^{-1}$ as $n$ grows. Thus, a randomly chosen permutation on $n$ elements is a derangement approximately with probability $1/e$.)

Grading: Each problem 12 points, total 60 points.