\documentclass[12pt]{article}
\title{Math 187 Final Exam}
\author{Dr. Holmes}
\date{May 9, 2007}
\begin{document}
\maketitle
This exam starts at 8 am and officially ends at 10 am. If no one
objects, the exam will continue until 10:15 am. You are allowed to
use your book and one standard sized sheet of notebook paper with
whatever you like written on it. You are allowed to use a standard
scientific calculator without graphing or symbolic computation
capabilities.
\newpage
\begin{enumerate}
\item Show that $P \rightarrow (Q \rightarrow R)$ is logically equivalent to
$(P \wedge Q) \rightarrow R$ by the method of truth tables. Be sure
to highlight significant rows or columns of your tables and state any
important relationships between them.
\newpage
\item
Give a formal proof that the product of two odd integers is odd. Your
proof should use nothing but the definition of ``odd'' (which you
should state) and basic algebra. It should be given in the formal
style with assumptions and goals which was taught in class.
\newpage
\item
A state has license plates consisting of four letters followed by
three digits. Set up your calculations on your paper then compute the
numerical answer.
\begin{enumerate}
\item How many plates are possible?
\vspace{.5 in}
\item
How many plates are possible if no letter can appear more than once on the plate and no digit can be immediately followed by the same digit?
\vspace{.5 in}
\item
How many plates contain no digit 8?
\vspace{.5 in}
\item
How many plates have no repeated letters or digits, all letters in
alphabetical order and all digits in numerical order? (It is still the
case that the letters all appear before the digits.)
\vspace{.5 in}
\end{enumerate}
\newpage
\item
In a group of 32 freshmen, all of whom must take at least one of English, Math, and French, 16 students take English, 19 take Math, 18 take French, while
9 take English and French, 10 take Math and French, and 10 take English and Math. How many take all three courses?
You need to set up and carry out your work using the Inclusion
Exclusion Principle; I should be able to tell from your paper that you
know what this principle is, at least in the case of three sets.
\newpage
\item
Prove by mathematical induction that for any nonnegative integer $n$,
the sum $\Sigma_{i=0}^{n} 3^i = 1+3+9+\ldots+3^{i-1}+3^i = \frac{3^{n+1}-1}2$.
\newpage
\item
Compute the gcd of 30 and 74 using the Euclidean algorithm (and clearly indicate that you know what the answer is: $\gcd(30,74)=\ldots$).
Find integers $x$ and $y$ such that $30x + 74y =\gcd(30,74)$.
\newpage
\item Chinese Remainder Theorem.
Solve the system of equations
$x \,{\tt mod}\, 23 = 11$
$x \,{\tt mod}\, 34 = 2$
Give the smallest non-negative solution.
\newpage
\item Degree sequences: for each of the following degree sequences either
present a graph with that degree sequence or give a reason why no such
graph is possible. Also, follow any additional instructions in each
part.
\begin{enumerate}
\item 1,2,2,3,3,3
\vspace{1 in}
\item 1,2,3,4,4,5
\vspace{1 in}
\item 2,2,2,2,2,2,2
(there are at least two fundamentally different graphs with this
sequence: draw two).
\end{enumerate}
\newpage
\item A graph has 8 vertices, each of degree 5.
I drew one: this is possible. You should not have to draw one to
answer the questions, however.
How many edges are there in this graph? Explain.
\vspace{1 in}
Show that the graph is not planar using an appropriate formula.
\newpage
\item A graph is pictured.
Identify all the cut edges in this graph (put an x in the middle of
each cut edge on the given graph picture).
Draw a spanning tree for this graph (a spanning subgraph which is a
tree: draw a separate picture of a subgraph of the given graph with
the same vertices which is a tree).
\newpage
\end{enumerate}
\end{document}