\documentclass[12pt]{article}
\usepackage{amssymb}
\title{Math 187 Spring 2013 Final Exam}
\author{Dr. Holmes}
\begin{document}
\maketitle
The exam will begin at 12 pm precisely and end at 2 pm officially. The exam will continue until 2:15 pm unless a member of the class raises an objection.
You are allowed the use of your test paper, your writing instrument, your non-graphing scientific calculator, your book and one standard-sized sheet of notebook paper with whatever you like written on it. You may not use your cell phone in any way or have any access to it for any reason.
\newpage
\begin{enumerate}
\item Truth tables. Verification of a tautology and construction of an expression from a truth table.
\begin{enumerate}
\item Verify the deMorgan law asserting the equivalence of $\neg(P \vee Q)$ with $\neg P \wedge \neg Q$ using a truth table. You should highlight the features of your table which provide an answer to the question (circle some columns and say something about them).
\vspace{2 in}
\item Write an expression using $\wedge$, $\vee$, $\neg$ and letters which has the following truth table:
$$\begin{array}{|ccc|c|}
P & Q & R & ??? \\ \hline
T & T & T & F \\
T & T & F & T \\
T & F & T & F \\
T & F & F& F \\
F & T & T & T \\
F & T & F& F \\
F & F & T & T \\
F & F & F & F\\
\end{array}$$
\end{enumerate}
\newpage
\item Prove that the product of two odd numbers is odd. Your proof may use elementary algebra and the following definitions of odd and even number. The word ``divisible" should not appear in your proof, nor should any mention of division or remainders be made.
An integer $a$ is even iff there is an integer $x$ such that $2x=a$.
An integer $b$ is odd iff there is an integer $y$ such that $2y+1=b$.
You should start by converting the statement to be proved into an implication.
\newpage
\item Counting problems -- four problems are given. In some problems, the order of items in the outcome matters, and in some it doesn't.
In some problems, there may be more than one item of the same kind in an outcome (repetitions allowed) and in some there cannot be.
Solve each problem and classify it as order (does/doesn't) matter and repetitions (are/aren't) allowed.
\begin{enumerate}
\item A band with 30 members is asked to choose its three best members to participate in a national competition. How many ways are there to do this?
\vspace{.5 in}
\item A serial number consists of five octal digits (0-7). How many serial numbers are possible (they are allowed to start with zero).
\vspace{.5 in}
\item Delsa's has thirteen flavors of ice cream today and I am going to precariously heap three scoops on my waffle cone. How many different ways can I place my order (I'm just telling the girl how many scoops of each flavor)?
\vspace{.5 in}
\item In how many ways can I lay four cards from the standard 52-card deck out in a row in front of me?
\vspace{.5 in}
\end{enumerate}
\newpage
\item There are 24 students in the senior class at a small private school. Every one of them is taking either English Math or French or more than one of these. 14 are taking English. 9 are taking Math. 16 are taking French. 7 are taking English and French. 6 are taking English and Math.
4 brave souls are taking all three subjects. How many are taking Math and French, but not English?
\newpage
\item Let $x\,R\,y$ be defined as ``$x+y$ is even". Show that this is an equivalence relation. To do this you need to verify three properties:
you should clearly label these properties and write them out in terms of this specific relation (without using the abbreviation $R$ for the relation), then verify that each holds.
\vspace{4.5 in}
Show that the relation $x \,S\,y$ defined as ``$x+y$ is divisible by 3" is {\em not} an equivalence relation.
\newpage
\item A proof by mathematical induction. Prove that for every natural number $n$ the sum
$9\times10^0 + 9 \times 10^1 + 9 \times 10^2 \ldots + \ldots +9\times 10^{n} = 10^{n+1}-1$. For example,
$9+90+900+9000=10000-1$.
\newpage
\item Permutations.
Determine the compositions $\tau\circ \sigma$ and $\sigma\circ \tau$ where $\tau$ and $\sigma$ are the following permutations:
$$\sigma=\left[\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 5 & 3 & 2\end{array}\right]$$
$$\tau=\left[\begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 3 & 4 & 1\end{array}\right]$$
Write your answers in disjoint cycle notation and clearly label them so I can tell which is which.
\vspace{3 in}
What is the smallest positive number of times that the permutation $\rho =(012345)(789)$ of the decimal digits can be composed with itself to obtain the identity permutation? That is, if $\rho^k$ represents $\rho\circ \rho \circ\ldots\circ \rho$ ($k$ times) what is the smallest positive $k$ such that $\rho^k(d)=d$ for each digit $d$?
Explain.
\newpage
\item Greatest common denominator and Euclidean algorithm.
Compute the greatest common denominator of 100 and 77 and find integers $x$ and $y$ such that $100x+77y = \gcd(100,77)$. Part of your answer should be this equation with specific integers replacing $x$, $y$ and the gcd (a true equation of course).
\newpage
\item Number theory: Chinese remainder theorem
Solve the system of equations
$$x \equiv 2 \,{\tt mod}\, 37$$
$$x \equiv 10 \,{\tt mod}\, 24$$
Why do you know before you start that you will be able to find a solution?
Give the smallest positive solution, and give a general description of all solutions.
\newpage
\item An Eulerian walk through a graph is a walk which traverses each edge in the graph exactly once.
A graph is pictured. There is no Eulerian walk through this graph. Explain why not.
By adding a single edge to this graph, you can make an Eulerian walk possible. Draw in such an edge and describe such a walk through the modified graph. Your description should be a list of vertices visited in order.
\newpage
\item Graph theory: two graphs are pictured (a six pointed star in a circle and a five-pointed star in a circle, all vertices on the circle). One of these is planar and one is not. For the one which is planar, draw a planar picture.
For the one which is not, show a calculation with vertices and edges which verifies that it cannot be planar.
\end{enumerate}
\end{document}