Name:

MATH2800 Introduction to Discrete Structures

First Exam, Tuesday, September 25, 2007.

You may use one sheet of handwritten notes, but no other sources. The exam consists of five questions, and lasts fifty minutes. Please work all five problems. 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. (20 points) Show that $(p {\rightarrow}q) {\rightarrow}r$ and $p {\rightarrow}(q {\rightarrow}r)$ are not equivalent.

2. 1. (10 points) Define the two functions $f(x)$ and $g(x)$ on the positive integers as follows:
      
      $$f(x) = \left\{ \begin{array}{ll}x^3 & \mbox{if $x$\ is prim... ... $x$\ is odd} \\ x^2 & \mbox{otherwise.} \end{array} \right.$$
      
      
      Can we say that $f(x)$ is $O(g(x))$? Can we say that $g(x)$ is $O(f(x))$?
   2. (10 points) Use the definition of ``$f(x)$ is $O(g(x))$'' to show that $3+\log_{10}(x^2)$ is $O(\log_{10}x)$.

3. (20 points) Let $S_n$ be a set with $n$ elements, where $n \geq 2$. Use induction to show that the number of subsets of $S_n$ with exactly one element is equal to $n$ and the number of subsets with exactly two elements is equal to $\frac{n(n-1)}{2}$.

4. (20 points)
   1. (5 points) Use the Euclidean Algorithm to show that 16 and 67 are relatively prime.
   2. (8 points) Find the inverse of 16 modulo 67.
   3. (7 points) Find all solutions to the linear congruence
      
      $$16 x \equiv 3 \,\, (\mbox{mod } 67).$$
      
      

5. (20 points) Show that if the statement $P(n)$ is true for infinitely many positive integers $n$ and $P(n+1) {\rightarrow}P(n)$ is true for all positive integers, then $P(n)$ is true for all positive integers $n$.