\documentclass[12pt]{article}
\usepackage{fullpage,graphicx,amssymb,amsmath}
\pagestyle{plain}
\begin{document}
\begin{center}
\textbf{College of the Holy Cross, Fall Semester 2017} \\
\textbf{MATH 243 -- Mathematical Structures, section 2} \\
\textbf{Final Exam -- December 13}

\end{center}



\vskip 1.5truein



\noindent\textbf{Your Name}: \underline{\phantom{Name Name Name Name Name}}

\vskip 0pt plus .3fil



\paragraph{Instructions:} You have until 2:00pm to work on this exam.
Please write your answers in the spaces
provided on the following pages, and show work on the test itself. 
{\it For possible partial credit, even if you cannot completely solve a problem, 
include definitions of terms involved, partial results you can do, etc.}  Use the 
back of the preceding page if you need more space for scratch work.



\vskip 1.0truein



\noindent\textbf{\noindent\textbf{Please do not write in the space below}}


\vskip 1.0truein

\begin{center}

\begin{tabular}{|l||r|}

\hline

Problem & Points/Poss    \strut \\

\hline\hline

I  & \hfil/\  25\hfil \strut \\

\hline

II  & \hfil/\  20\hfil \strut \\

\hline
III  & \hfil/\  20\hfil \strut \\

\hline

IV  & \hfil/\  35\hfil \strut \\

\hline

V  & \hfil/\  30\hfil \strut \\
\hline

VI  & \hfil/\  30\hfil \strut \\

\hline

VII  & \hfil/\  40\hfil \strut \\

\hline\hline

Total   & \hfil/200\hfil \strut \\

\hline

\end{tabular}
\vskip 10pt
\centerline{\it Have a peaceful and joyous holiday season!}
\end{center}
\vfill\eject
\noindent
I. 
\begin{enumerate}
\item[A)]  (15) Let $p,q$ represent any propositions. 
Construct the truth table for the proposition
$$(p\ {\rm implies}\ q)\ {\rm if\ and\ only\ if}\ ((p\ {\rm and\ not}\ q)\ {\rm implies\ not}\ p)$$
\vskip 4.0truein
\item{B)}  (5)  Give the contrapositive form of the statement
``If the product of two integers $x,y$ is even, then $x$ is even 
or $y$ is even.''
\vskip 1.0truein
\item{C)}  (5) Give the converse of the statement in part B.
\end{enumerate}
\vfill\eject
\noindent
II. All parts of this question refer to the mapping 
$f : \mathbb{Z} \to \mathbb{Z}$ defined by 
$$f(x) = \begin{cases} 6x & {\rm if}\ x\ {\rm is\ even}\\
                             2 - x & {\rm if}\ x\ {\rm is\ odd}
               \end{cases}
$$
\begin{enumerate}
\item[A)] (10)  Let $U = \{1,2,3,4,5\}$.  What is $f(U) \cap \{x \in \mathbb{Z} : x > 0\}$?
\vskip 3.0truein
\item[B)] (10)  Let $V = 4\mathbb{Z}$.  What is $f^{-1}(V)$ for this mapping?  
Describe using proper set notation.  
\end{enumerate}
\vfill\eject
\noindent
III. (20)   Give a precise statement of the Division Algorithm in $\mathbb{Z}$
and prove the Existence and Uniqueness parts.  
\vfill\eject
\noindent
IV.
\begin{enumerate}
\item[A)] (20)  Use the Euclidean Algorithm to find the integer 
$d = \gcd(753,156)$ and express 
$d$ in the form $d = 753m + 156n$ for some integers $m,n$.
\vskip 5.0truein
\item[B)] (15)  Let $a,b,c$ be integers.  Prove that $\gcd(ab,c) = 1$ if and only
if $\gcd(a,c) = 1$ and $\gcd(b,c) = 1$.  
\end{enumerate} 
\vfill\eject
\noindent
V.  Let $f:A \to B$ be a mapping and $U, V \subseteq A$. For each statement, give a proof 
if the statement is true, or give a counterexample if the statement is false. 
(A complete counterexample consists of specific sets $A, B, U$, and $V$, a mapping $f$, 
and justification of why these data contradict the statement.)
\begin{enumerate}
\item[A)] (15) If $f$ is injective and $f(U) \subseteq f(V)$, then $U \subseteq V$.
\vskip 3.5truein
\item[B)] (15) If $f$ is surjective and $f(U) \subseteq f(V)$, then $U \subseteq V$.
\end{enumerate}
\vfill\eject
\noindent
VI.  All parts of this question refer to  $R = \mathbb{Z}/30\mathbb{Z}$,
in which the operations are addition and multiplication mod 30.
\begin{enumerate}
\item[A)]  (20) Construct the addition and multiplication tables
for the subset $T=\{[0],[6],[12],[18],[24]\}$ in $R$.
\vskip 5.0truein
\item[B)] (10) Which elements of $R$ have {\it multiplicative}
inverses in $R$?  Explain how you know.  
\end{enumerate}
\vfill\eject
\noindent
VII.  
\begin{enumerate}
\item[A)]  (20) Prove by mathematical induction that 
$$\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \cdots + \frac{1}{n\cdot(n+1)} = \frac{n}{n+1}$$
for all natural numbers $n \ge 1$.
\end{enumerate}
\vfill\eject
\begin{enumerate}
\item[B)]  (10)  What is the least upper bound  
$$L = \sup\left(\left\{\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \cdots + \frac{1}{n\cdot(n+1)} \mid n \ge 1\right\}\right).$$
(This is the same set of numbers as in part A.)  Prove your assertion by showing that for every 
real $\epsilon > 0$, there exists some $n$ such that 
$$L - \varepsilon < \frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \cdots + \frac{1}{n\cdot(n+1)} \le L.$$
\vskip 4.0truein
\item[C)]  (10) What does your argument in part B say about the sequence 
$$a_n = \frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \cdots + \frac{1}{n\cdot(n+1)}?$$
\end{enumerate}  

\end{document}








