% LaTex2e
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}
%\usepackage{anysize}
%\marginsize{left}{right}{top}{bottom}
%\marginsize{1.25cm}{1.25cm}{1.75cm}{2.5cm} % this cuts off page numbers
%%%%%% \marginsize{2cm}{2cm}{1cm}{3cm}

\pagestyle{myheadings}
\def\header{{\hfill Final Exam \hfill A. Miller \hfill Spring 2008
                                       \hfill Math 240\hfill}}
\markboth\header\header

\newcount\probno
\probno=0
\def\prob#1{\advance\probno by 1 \par\bigskip
    \noindent\the\probno .  }

\newenvironment{enum}
{\begin{list}{(\alph{enumi})}
{\usecounter{enumi}\setlength{\rightmargin}{\leftmargin}}}
{\end{list}}
\newenvironment{Enum}
{\begin{list}{(\Alph{enumi})}
{\usecounter{enumi}\setlength{\rightmargin}{\leftmargin}}}
{\end{list}}

\def\mod{\mbox{ mod }}

\begin{document}

\bigskip

Do not hand in this exam.

Put all your answers on the Yellow exam. 

\bigskip

No notes, no books, no calculators, no cell phones, no pagers, no
electronic devices of any kind.

\bigskip


\prob{12}
Let $\theta$ be the following sentence of the predicate logic:
$$\forall x\;\exists y\; (R(x,y)\wedge S(y))$$
which of the following is logically equivalent to the
negation of $\theta$, i.e., $$\neg\theta\equiv ?$$

\begin{enum}
\item $\forall x\;\exists y\; (\neg R(x,y)\wedge \neg S(y))$
\item $\exists x\;\forall y\; ( R(x,y)\to S(y))$

\item $\exists x\;\forall y\; (\neg R(x,y)\vee \neg S(y))$

\item $\forall x\;\forall y\; \neg (R(x,y)\vee S(y))$
\item None of above.
\end{enum}

\prob{12}
For integers $n$ and $m$ greater than one there exists a multiplicative
inverse of $m \mod n$, i.e., an integer $k$ such that
$$mk\equiv 1 \mod n$$ 
if and only if

\begin{enum}
\item $m$ and $n$ are relatively prime
\item $m$ does not divide $n$
\item $mn$ is not a prime number
\item $m$ and $n$ are divisible by the same prime numbers
\item None of above.
\end{enum}


\def\floor(#1){{\lfloor #1\rfloor}}
\def\ceiling(#1){{\lceil #1\rceil}}

\prob{12}  %  2.3    53 
Let $a$ and $b$ be real numbers with $0 < a < b$ use the floor and/or
ceiling functions to express the number of integers $n$ that
satisfy the inequality $a<n \leq b:$

\begin{enum}
\item  $\floor(b)-\floor(a)$
\item  $\ceiling(b)-\floor(a)+1$
\item  $\ceiling(b)-\floor(a)$
\item  $\floor(b-a)$
\item  None of above.
\end{enum}



\prob{12} % 3.4
Find all integers $a$ such that $$a \mod 3=a\mod 5.$$

\begin{enum}
\item $a$ is either a multiple of $3$ or a multiple of $5$.
\item $a$ is $8\mod 15$.
\item $a$ is not $3\mod 5$

\item $a$ is $0,1,$ or $2$  $\mod 15$.

\item None of the above.
\end{enum}


\prob{12} 
 Find the greatest common divisor of
 $2^3\, 3^6 \, 11^3$ and $2^2 \,3^7\, 5^4\, 11^5\, 13$.
\begin{enum}
\item $2^2\, 3^6\, 11^3$
\item $2^3\, 3^7\, 11^5$
\item $2^2\, 3^6\, 5^4\, 11^3\, 13$
\item $2^3\, 3^7\, 5^4\, 11^5\, 13$
\item None of above.
\end{enum}


\newpage

\prob{12}
Find the least common multiple of
 $2^3\, 3^6 \, 11^3$ and $2^2 \, 3^7\, 5^4\, 11^5\, 13$.
\begin{enum}
\item $2^2\, 3^6\, 11^3$
\item $2^3\, 3^7\, 11^5$
\item $2^2\, 3^6\, 5^4\, 11^3\, 13$
\item $2^3\, 3^7\, 5^4\, 11^5\, 13$
\item None of above.
\end{enum}

\prob{12} % supplementary problem chapter 3 - 40
Suppose 
$$A =
\left[
\begin{array}{cc}
                1 &  0 \\
                1 &  1
\end{array}
\right].
$$
Find $A^n$.

\begin{enum}

\item $$
\left[
\begin{array}{cc}
                n &  0 \\
                n &  n
\end{array}
\right].
$$
\item $$
\left[
\begin{array}{cc}
                1 & n-1 \\
                n &  1
\end{array}
\right].
$$
\item $$
\left[
\begin{array}{cc}
                1 &  0 \\
                n &  1
\end{array}
\right].
$$

\item $$
\left[
\begin{array}{cc}
                1 &  0 \\
                1 &  1
\end{array}
\right].
$$
\item None of above.
\end{enum}

\newpage

\prob{12} % 1  4.3 
 Given that $f(n)$ is defined recursively
by $f(0)=0$ and 

$f(n+1)=(f(n)+1)^2$ for $n=0,1,2,\ldots$.

Find $f(3)$:
\begin{enum}
\item 4
\item 5
\item 25
\item $26^2$
\item None of above
\end{enum}

\prob{12} % 53  5.1 
How many ways are there to arrange the letters: $g,r,e,a,t$ so that
$a$ is immediately followed by $t$?
\begin{enum}
\item $24$
\item $60$
\item $72$
\item $96$
\item $120$
\item None of above
\end{enum}

\prob{12}
How many ways are there to arrange the letters: $g,r,e,a,t$ so that
$a$ occurs somewhere to the left of where $t$ occurs?
\begin{enum}
\item $24$
\item $60$
\item $72$
\item $96$
\item $120$
\item None of above
\end{enum}

\newpage

\prob{12}
How many ways are there to arrange the letters: $g,r,e,a,t$ so that
$a$ and $t$ do not occur next to each other (in either order)?
\begin{enum}
\item $24$
\item $60$
\item $72$
\item $96$
\item $120$
\item None of above
\end{enum}

\prob{12} %  7  6.1 
What is the probability that when a fair coin is flipped five
times in a row it comes up Heads every time?
\begin{enum}
\item $2^5$
\item $({1\over 2})^5$
\item $({1\over 5})^2$
\item $ {5\over 2}$
\item None of above.
\end{enum}

\prob{12} 
Suppose a fair die is rolled 180 times.  Define the
random variable $X$ to be the number of times a 6 comes up.
What is the expected value $\mu=E(X)$?
\begin{enum}
\item $  5$
\item $ 25$
\item $ 30$
\item $ 60$
\item $ 90$
\item None of above.
\end{enum}

\prob{12}  (same $X$) Suppose a fair die is rolled 180 times.  Define the
random variable $X$ to be the number of times a 6 comes up.
What is the variance $\nu=Var(X)$?

\begin{enum}
\item $  5$
\item $ 25$
\item $ 30$
\item $ 60$
\item $ 90$
\item None of above.
\end{enum}

\prob{12} Suppose that $A$ is a set with $n$-elements.
How many binary relations are there on $A$?
\begin{enum}
\item $n^2$
\item $2^{n^2}$
\item $2^{n^2-n}$
\item $2^{n(n+1)/2}$
\item $3^{n(n-1)/2}\cdot 2^n$
\item None of above.
\end{enum}



\prob{12} Suppose that $A$ is a set with $n$-elements.
How many reflexive binary relations are there on $A$?
\begin{enum}
\item $n^2$
\item $2^{n^2}$
\item $2^{n^2-n}$
\item $2^{n(n+1)/2}$
\item None of above.
\end{enum}

\prob{12} (Choose all that apply.)
A binary relation $R$ on a set $A$ is an
equivalence relation
iff it is ??
\begin{enum}
\item reflexive
\item antisymmetric
\item symmetric
\item irreflexive
\item transitive
\end{enum}

\prob{12} (Choose all that apply.)
A binary relation $R$ on a set $A$ is a
partial order
iff it is ??

\begin{enum}
\item reflexive
\item antisymmetric
\item symmetric
\item irreflexive
\item transitive
\end{enum}


\prob{12} Let A be the set of all bit-strings
of length 16.  For $x,y\in A$ define 
$x\equiv y$ iff $x$ and $y$ have the same number of $1$'s.
How many equivalences classes are there?

\begin{enum}
\item 16
\item 17
\item $2^{16}$
\item $C(16,6)$
\item None of above.
\end{enum}


\prob{12} (Same $\equiv$ as above.) Let A be the set of all bit-strings
of length 16.  For $x,y\in A$ define 
$x\equiv y$ iff $x$ and $y$ have the same number of $1$'s.
How many elements
are there in the equivalence class which contains
$0001111000011000$?
\begin{enum}
\item $6$
\item $16$
\item $17$
\item $C(16,6)$
\item $6!$
\item $P(16,6)$
\item None of above.
\end{enum}


\bigskip\bigskip

Put your answers to the following two problems on the Yellow exam.

\bigskip\noindent
{\bf Problem A}.

Draw the Hasse diagram for the partially ordered set:

$A=\{1,2,3,4,5,6,7,8,9,10,11,12\}$ and $R\subseteq A\times A$ defined by

$xRy$ iff $x$ divides $y$.


\bigskip\noindent
{\bf Problem B}.

Find the closed form solution of the recurrence relation:
$$a_0=1 $$ $$ a_1=5$$
$$a_{n+1}=2a_n-a_{n-1}+2^n$$

\newpage
\begin{center} Answers 
\end{center}


1-20 

c a a d a d c

  

c a b c b c b


b c ace abe b d

\bigskip

\def\text#1{\makebox(0,0)[cc]{#1}}
\def\putnode(#1,#2,#3){\put(#1,#2){\circle{5}}\put(#1,#2){\text{#3}}}


A. 

\unitlength=1.36mm
\begin{picture}(100, 50)
\putnode(40,10,1)
\putnode(20,20,11)
\putnode(30,20,5)
\putnode(40,20,2)
\putnode(50,20,3)
\putnode(60,20,7)
\putnode(30,30,10)
\putnode(40,30,4)
\putnode(50,30,6)
\putnode(60,30,9)
\putnode(40,40,8)
\putnode(50,40,12)
\put(40,32){\line(0,1){6}}
\put(50,32){\line(0,1){6}}
\put(42,32){\line(1,1){6}}
\put(30,22){\line(0,1){6}}
\put(40,22){\line(0,1){6}}
\put(50,22){\line(0,1){6}}
\put(42,22){\line(1,1){6}}
\put(52,22){\line(1,1){6}}
\put(40,12){\line(0,1){6}}
\put(38,22){\line(-1,1){6}}
\put(38,12){\line(-1,1){6}}
\put(42,12){\line( 1,1){6}}
\put(42,11){\line(2,1){16}}
\put(38,11){\line(-2,1){16}}
\end{picture}

\bigskip

B. $a_n=2n-1+ 2^{n+1}$

\bigskip



\end{document}



