% LaTex2e
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}
\def\rr{{\mathbb R}}
\def\implies{\to}
\def\orx{\vee}   % \or special tex macro
\def\and{\wedge}
\def\iff{\leftrightarrow}


\oddsidemargin 5pt \evensidemargin 5pt \marginparwidth 68pt
\marginparsep 10pt \topmargin -40pt \headheight 10pt
\headsep 15pt \footskip 35pt
\textheight = 625pt  \textwidth 440pt \columnsep 10pt \columnseprule 5pt

\pagestyle{myheadings}
\def\la{\langle}  \def\ra{\rangle}
\def\header{{\hfill Final Exam \hfill A. Miller \hfill Spring 2002
                                       \hfill Math 240\hfill}}
\markboth\header\header
\newcount\probno
\newcount\total
\newwrite\examTBLFile


%\def\evenprob{\vfill}
\def\evenprob{\vfill\newpage}
\def\oddprob{\vfill\newpage}

\probno=0
\def\prob#1{\advance\probno by 1
   \ifodd\probno\oddprob\else\evenprob\fi
    \noindent\the\probno . (#1 pts)\advance\total by #1
    \immediate\write\examTBLFile{\the\probno
       \string& #1 \string&
       \string\qquad \string\\ \string\hline}}

\def\probx#1{\advance\probno by 1  \vfill  % \par
    \noindent\the\probno . (#1 pts)\advance\total by #1
    \immediate\write\examTBLFile{\the\probno
       \string& #1 \string&
       \string\qquad \string\\ \string\hline}}

\def\finishtbl{
    \immediate\write\examTBLFile{Total \string& \the\total
    \string& \qquad \string\\ \string\hline}
     }

%%% \outer\def\answer{ {\par\bigskip Circle your answer.} \par\medbreak

\newwrite\ans
\immediate\openout\ans=answers
\outer\def\answer{\par\medbreak
  \immediate\write\ans{}
  \immediate\write\ans{\string\bigskip \the\probno . }
  \copytoblankline}
\outer\def\answerx{ \par\medbreak
  \immediate\write\ans{}
  \immediate\write\ans{\string\bigskip \the\probno . }
  \copytoblankline}
\outer\def\putanswer{\par\medbreak
  \immediate\write\ans{}
  \copytoblankline}
\def\copytoblankline{\begingroup\setupcopy\copyans}
\def\setupcopy{\def\do##1{\catcode`##1=12}\dospecials
     \catcode`\|=12\obeylines}
{\obeylines \gdef\copyans#1
  {\def\next{#1}%
  \ifx\next\empty\let\next=\endgroup%
  \else\immediate\write\ans{\next}\let\next=\copyans\fi\next}}
\def\printanswers{\newpage\begin{center} Answers \end{center}
    \immediate\closeout\ans\input answers}

%\def\answer{\par\bigskip\bigskip\bigskip\noindent Answer: \par}


\begin{document}

\bigskip

Show all work.  Circle your answer.

No notes, no books, no calculator, no cell phones, no pagers, no
electronic devices at all.

Solutions will be posted shortly after the exam:
www.math.wisc.edu/$\sim$miller/m240

\par\vskip .25in
\begin{center}
Name\makebox[3in]{\hrulefill} \\
\end{center}


\begin{center} \Large
 \begin{tabular}{||c|c|c||} \hline\hline
  Problem & Points & Score \\  \hline\hline
   \input{exam.tbl}
  \hline \hline
 \end{tabular}
\end{center}

\immediate\openout\examTBLFile=exam.tbl

\setcounter{page}{0}

\prob{8} % exam 1
Prove that $3^n\geq 3n+1$ for every integer $n\geq 2$.

\answer \par\noindent Base Case: $n=2$.
$$3^2=9\geq 7=3\cdot 2 +1$$
Inductive Step: Assume $n\geq 2$ and $3^n\geq 3n+1$ then
$$3^{n+1}=3\cdot 3^n \geq 3(3n+1)= 3((n+1)+2n)=3(n+1)+6n\geq 3(n+1)+1$$
The last inequality is true since $6n\geq 1$ for $n\geq {1\over 6}$.
It follows by transitivity that
$$3^{n+1}\geq 3(n+1)+1$$
as we needed to show.

\prob{8} % quiz
Construct a truth table for $((P\vee Q)\wedge(P\to R))$
\answer $$\begin{array}{c|c|c|c|}
p & q & r & (p\vee q)\wedge (p\to r)\\
\hline
T & T & T & \hfill T \hfill T \hfill T\hfill \\
T & T & F & \hfill T \hfill F \hfill F\hfill \\
T & F & T & \hfill T \hfill T \hfill T\hfill \\
T & F & F & \hfill T \hfill F \hfill F\hfill \\
F & T & T & \hfill T \hfill T \hfill T\hfill \\
F & T & F & \hfill T \hfill T \hfill T\hfill \\
F & F & T & \hfill F \hfill F \hfill T\hfill \\
F & F & F & \hfill F \hfill F \hfill T\hfill \\
\end{array}$$



\prob{8} % exam 1
Find $d=$gcd$(45,39)$ and find integers $k$ and $l$ so
that $d=45k\;+\;39l$.
\answer gcd$(45,39)=3=(6)45+(-7)39$

\prob{8} % quiz
A prime triple is a prime $p$ such that $p$, $p+2$, $p+4$ are
all prime numbers.  Prove that $3,5,7$ is the only prime triple.
(Note: $1$ is not a prime number and $1,3,5$ is not a prime triple.)

\answer  Given any integer $p$, one of $p$, $p+2$, or $p+4$ is divisible by
3.  If $p$ is not divisible by 3, then $p$ must be either $1$ or $2$ mod
3. If it is $1$ mod 3 then $p+2$ is 3 mod 3 hence divisible by 3. If it is
$2$ mod 3 then $p+4$ is 6 mod 3 hence divisible by $3$.  If follows that the
only prime triple is 3, 5, 7.


\prob{8} % exam 2
How many words of length 8 are there such that
they are made up of the 26 letters $abc\ldots z$ and
they contain exactly two a's and three b's and no other letter is
repeated?
\answer $$\left(\begin{array}{c} 8\\ 2\end{array}\right)
\left(\begin{array}{c} 6\\ 3\end{array}\right)
\cdot 24\cdot 23 \cdot 22
$$


\prob{8} % quiz
What is the probability of a seven card flush?  This means 7 cards
are dealt randomly out of a standard deck of 52 and all 7 cards have
the same suit.
\answer $${ 4\cdot \left(\begin{array}{c} 13\\ 7\end{array}\right)
\over
\left(\begin{array}{c} 52\\ 7\end{array}\right)}$$

\prob{8} % exam 2
Find the general solution of the recurrence relation
$$a_n=5a_{n-1}-6a_{n-2}$$
\answer $a_n=A\; 2^n\;+\;B \;3^n$ where $A$ and $B$ are arbitrary constants.


\prob{8} % quiz
Let $R\subseteq A\times A$ be a binary relation on the set $A$.
Define
\def\skp{\par\vspace{1in}}
\skp
\par\bigskip (a) $R$ is reflexive
\skp
\par (b) $R$ is transitive
\skp
\par (c) $R$ is symmetric
\skp
\par (d) $R$ is antisymmetric
\answer (a) $\forall x\in A\;\; (x,x)\in R$
\par (b) $\forall x,y,z\in A\;\; (x,y),(y,z)\in R\implies (x,z)\in R$
\par (c) $\forall x,y\in A\;\; (x,y)\in R\implies (y,x)\in R$
\par (d) $\forall x,y\in A\;\; (x,y),(y,x)\in R\implies x=y$

\prob{10} In the two graphs below determine whether they have
an Euler path.  For each one either give such a path, or state
the reason it doesn't have one.

\bigskip\bigskip

\unitlength=1.50mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(55.00,67.00)
\put(20.00,21.00){\framebox(30.00,29.00)[cc]{}}
\put(35.00,65.00){\line(-1,-1){15.00}}
\put(35.00,65.00){\line(1,-1){15.00}}
\put(35.00,5.00){\line(1,1){15.00}}
\put(35.00,5.00){\line(-1,1){15.00}}
\put(20.00,35.00){\line(1,1){15.00}}
\put(35.00,50.00){\line(1,-1){15.00}}
\put(50.00,35.00){\line(-1,-1){15.00}}
\put(35.00,20.00){\line(-1,1){15.00}}
\put(35.00,64.00){\circle*{2.00}}
\put(50.00,50.00){\circle*{2.00}}
\put(50.00,35.00){\circle*{2.00}}
\put(50.00,21.00){\circle*{2.00}}
\put(35.00,21.00){\circle*{2.00}}
\put(20.00,21.00){\circle*{2.00}}
\put(35.00,5.00){\circle*{2.00}}
\put(20.00,35.00){\circle*{2.00}}
\put(35.00,50.00){\circle*{2.00}}
\put(20.00,50.00){\circle*{2.00}}
\put(35.00,67.00){\makebox(0,0)[cc]{a}}
\put(54.00,51.00){\makebox(0,0)[cc]{b}}
\put(55.00,35.00){\makebox(0,0)[cc]{c}}
\put(55.00,21.00){\makebox(0,0)[cc]{d}}
\put(40.00,5.00){\makebox(0,0)[cc]{e}}
\put(16.00,19.00){\makebox(0,0)[cc]{f}}
\put(15.00,35.00){\makebox(0,0)[cc]{g}}
\put(15.00,51.00){\makebox(0,0)[cc]{h}}
\put(34.00,53.00){\makebox(0,0)[cc]{i}}
\put(35.00,25.00){\makebox(0,0)[cc]{j}}
\end{picture}

\bigskip
\bigskip

\unitlength=1.50mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(53.00,53.00)
\put(10.00,10.00){\framebox(40.00,40.00)[cc]{}}
\put(10.00,10.00){\framebox(25.00,25.00)[cc]{}}
\put(10.00,10.00){\line(1,1){25.00}}
\put(10.00,35.00){\line(1,-1){25.00}}
\put(10.00,53.00){\makebox(0,0)[cc]{a}}
\put(53.00,52.00){\makebox(0,0)[cc]{b}}
\put(53.00,10.00){\makebox(0,0)[cc]{c}}
\put(7.00,9.00){\makebox(0,0)[cc]{d}}
\put(8.00,35.00){\makebox(0,0)[cc]{e}}
\put(38.00,37.00){\makebox(0,0)[cc]{f}}
\put(38.00,14.00){\makebox(0,0)[cc]{g}}
\put(23.00,26.00){\makebox(0,0)[cc]{h}}

\put(10.00,50.00){\circle*{2.00}}
\put(10.00,35.00){\circle*{2.00}}
\put(10.00,10.00){\circle*{2.00}}

\put(50.00,50.00){\circle*{2.00}}
\put(50.00,10.00){\circle*{2.00}}

\put(35.00,35.00){\circle*{2.00}}
\put(35.00,10.00){\circle*{2.00}}

\put(22.50,22.50){\circle*{2.00}}

\end{picture}

\answer The first graph has no Euler path because it has four vertices
of odd degree.  The second graph has an Euler path starting at $d$ and
ending at $f$ (or vice-versa) and visiting each of the 12 edges exactly once.
For example: deabcgdgfehgf

\prob{8} State Euler's formula relating the number of faces $|F|$,
vertices $|V|$ and edges $|E|$ for a connected planar graph.  Use
it to prove that the complete graph $K_5$ on five vertices is not
planar.
\par Hint: Use that each face must be bounded by three or more edges
to write an inequality relating $|F|$ and $|E|$.

\answer $|F|+|V|=|E|+2$. For $K_5$ we have $|V|=5$ and $|E|=
\left(\begin{array}{c} 5\\ 2\end{array}\right)=
10$ and so $|F|=7$
For each face $f\in F$ let edges($f$)
be set of edges which bound the face. Then
$$2|E|=\sum_{f\in F}|\mbox{edges}(f)|$$
this is because each edge is lies on two faces.  Since every face is
surrounded by at least three edges we have
$$\sum_{f\in F}|\mbox{edges}(f)|\geq \sum_{f\in F}3=3|F|$$
and so
$$20=2|E|\geq 3|F|=21$$
which is a contradiction.


\prob{8} The parse tree below is determined by
a formula of propositional logic.

\bigskip
\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(62.00,45.00)
\put(10.00,20.00){\line(1,1){10.00}}
\put(20.00,30.00){\line(1,-1){10.00}}
\put(20.00,30.00){\line(1,1){10.00}}
\put(30.00,40.00){\line(2,-1){20.00}}
\put(50.00,30.00){\line(-1,-2){5.00}}
\put(45.00,20.00){\line(0,-1){10.00}}
\put(50.00,30.00){\line(5,-6){8.33}}
\put(30.00,40.00){\circle*{2.00}}
\put(20.00,30.00){\circle*{2.00}}
\put(10.00,20.00){\circle*{2.00}}
\put(30.00,20.00){\circle*{0.00}}
\put(30.00,20.00){\circle*{2.00}}
\put(45.00,20.00){\circle*{2.00}}
\put(50.00,30.00){\circle*{2.00}}
\put(58.00,20.00){\circle*{2.00}}
\put(45.00,10.00){\circle*{2.00}}
\put(30.00,45.00){\makebox(0,0)[cc]{$\vee$}}
\put(17.00,33.00){\makebox(0,0)[cc]{$\to$}}
\put(10.00,15.00){\makebox(0,0)[cc]{P}}
\put(31.00,15.00){\makebox(0,0)[cc]{Q}}
\put(53.00,33.00){\makebox(0,0)[cc]{$\wedge$}}
\put(62.00,16.00){\makebox(0,0)[cc]{S}}
\put(41.00,22.00){\makebox(0,0)[cc]{$\neg$}}
\put(49.00,6.00){\makebox(0,0)[cc]{P}}
\end{picture}


\par (a) Use  inorder traversal to determine the infix formula.
\skp\skp
\par (b) Use  preorder traversal to determine the prefix formula (Polish
notation).
\skp\skp
\par  (c) Use postorder traversal to determine the postfix formula
(reverse Polish notation).
\answer (a) $(P\to Q)\vee(\neg P\wedge S)$
\par (b) $\vee\to PQ\wedge\neg PS$
\par (c) $PQ\to P\neg S\wedge\vee$

\prob{10}
For each graph, choose
$a$ as the root and use alphabetical order on the vertices and
produce a spanning tree by
\par\bigskip\skp
 (a) using depth-first search.  Draw in edges on right.

\bigskip\bigskip
\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(53.00,52.00)
\put(10.00,10.00){\framebox(40.00,40.00)[cc]{}}
\put(30.00,50.00){\line(0,-1){20.00}}
\put(30.00,30.00){\line(1,0){20.00}}
\put(10.00,30.00){\line(1,-1){20}}
\put(10.00,53.00){\makebox(0,0)[cc]{a}}
\put(29.00,53.00){\makebox(0,0)[cc]{b}}
\put(50.00,53.00){\makebox(0,0)[cc]{c}}
\put(13.00,33.00){\makebox(0,0)[cc]{d}}
\put(33.00,33.00){\makebox(0,0)[cc]{e}}
\put(53.00,33.00){\makebox(0,0)[cc]{f}}
\put(10.00,6.00){\makebox(0,0)[cc]{g}}
\put(30.00,6.00){\makebox(0,0)[cc]{h}}
\put(50.00,6.00){\makebox(0,0)[cc]{i}}
\put(10.00,50.00){\circle*{2.00}}
\put(10.00,30.00){\circle*{2.00}}
\put(10.00,10.00){\circle*{2.00}}
\put(30.00,50.00){\circle*{2.00}}
\put(30.00,30.00){\circle*{2.00}}
\put(30.00,10.00){\circle*{2.00}}
\put(50.00,50.00){\circle*{2.00}}
\put(50.00,30.00){\circle*{2.00}}
\put(50.00,10.00){\circle*{2.00}}
\end{picture}
\hspace{1in}
\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(53.00,52.00)
%\put(10.00,10.00){\framebox(40.00,40.00)[cc]{}}
%\put(30.00,50.00){\line(0,-1){40.00}}
%\put(10.00,30.00){\line(1,0){40.00}}
\put(10.00,53.00){\makebox(0,0)[cc]{a}}
\put(29.00,53.00){\makebox(0,0)[cc]{b}}
\put(50.00,53.00){\makebox(0,0)[cc]{c}}
\put(13.00,33.00){\makebox(0,0)[cc]{d}}
\put(33.00,33.00){\makebox(0,0)[cc]{e}}
\put(53.00,33.00){\makebox(0,0)[cc]{f}}
\put(10.00,6.00){\makebox(0,0)[cc]{g}}
\put(30.00,6.00){\makebox(0,0)[cc]{h}}
\put(50.00,6.00){\makebox(0,0)[cc]{i}}
\put(10.00,50.00){\circle*{2.00}}
\put(10.00,30.00){\circle*{2.00}}
\put(10.00,10.00){\circle*{2.00}}
\put(30.00,50.00){\circle*{2.00}}
\put(30.00,30.00){\circle*{2.00}}
\put(30.00,10.00){\circle*{2.00}}
\put(50.00,50.00){\circle*{2.00}}
\put(50.00,30.00){\circle*{2.00}}
\put(50.00,10.00){\circle*{2.00}}
\end{picture}

\bigskip\bigskip\skp
\par (b) using breath-first search. Draw in edges on right

\bigskip\bigskip
\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(53.00,52.00)
\put(10.00,10.00){\framebox(40.00,40.00)[cc]{}}
\put(30.00,50.00){\line(0,-1){40.00}}
\put(10.00,30.00){\line(1,0){40.00}}
\put(10.00,53.00){\makebox(0,0)[cc]{a}}
\put(29.00,53.00){\makebox(0,0)[cc]{b}}
\put(50.00,53.00){\makebox(0,0)[cc]{c}}
\put(13.00,33.00){\makebox(0,0)[cc]{d}}
\put(33.00,33.00){\makebox(0,0)[cc]{e}}
\put(53.00,33.00){\makebox(0,0)[cc]{f}}
\put(10.00,6.00){\makebox(0,0)[cc]{g}}
\put(30.00,6.00){\makebox(0,0)[cc]{h}}
\put(50.00,6.00){\makebox(0,0)[cc]{i}}
\put(10.00,50.00){\circle*{2.00}}
\put(10.00,30.00){\circle*{2.00}}
\put(10.00,10.00){\circle*{2.00}}
\put(30.00,50.00){\circle*{2.00}}
\put(30.00,30.00){\circle*{2.00}}
\put(30.00,10.00){\circle*{2.00}}
\put(50.00,50.00){\circle*{2.00}}
\put(50.00,30.00){\circle*{2.00}}
\put(50.00,10.00){\circle*{2.00}}
\end{picture}
\hspace{1in}
\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(53.00,52.00)
%\put(10.00,10.00){\framebox(40.00,40.00)[cc]{}}
%\put(30.00,50.00){\line(0,-1){40.00}}
%\put(10.00,30.00){\line(1,0){40.00}}
\put(10.00,53.00){\makebox(0,0)[cc]{a}}
\put(29.00,53.00){\makebox(0,0)[cc]{b}}
\put(50.00,53.00){\makebox(0,0)[cc]{c}}
\put(13.00,33.00){\makebox(0,0)[cc]{d}}
\put(33.00,33.00){\makebox(0,0)[cc]{e}}
\put(53.00,33.00){\makebox(0,0)[cc]{f}}
\put(10.00,6.00){\makebox(0,0)[cc]{g}}
\put(30.00,6.00){\makebox(0,0)[cc]{h}}
\put(50.00,6.00){\makebox(0,0)[cc]{i}}
\put(10.00,50.00){\circle*{2.00}}
\put(10.00,30.00){\circle*{2.00}}
\put(10.00,10.00){\circle*{2.00}}
\put(30.00,50.00){\circle*{2.00}}
\put(30.00,30.00){\circle*{2.00}}
\put(30.00,10.00){\circle*{2.00}}
\put(50.00,50.00){\circle*{2.00}}
\put(50.00,30.00){\circle*{2.00}}
\put(50.00,10.00){\circle*{2.00}}
\end{picture}

\answer \par (a)
\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(53.00,53.00)
\put(10.00,53.00){\makebox(0,0)[cc]{a}}
\put(29.00,53.00){\makebox(0,0)[cc]{b}}
\put(50.00,53.00){\makebox(0,0)[cc]{c}}
\put(13.00,33.00){\makebox(0,0)[cc]{d}}
\put(33.00,33.00){\makebox(0,0)[cc]{e}}
\put(53.00,33.00){\makebox(0,0)[cc]{f}}
\put(10.00,6.00){\makebox(0,0)[cc]{g}}
\put(30.00,6.00){\makebox(0,0)[cc]{h}}
\put(50.00,6.00){\makebox(0,0)[cc]{i}}
\put(10.00,50.00){\circle*{2.00}}
\put(10.00,30.00){\circle*{2.00}}
\put(10.00,10.00){\circle*{2.00}}
\put(30.00,50.00){\circle*{2.00}}
\put(30.00,30.00){\circle*{2.00}}
\put(30.00,10.00){\circle*{2.00}}
\put(50.00,50.00){\circle*{2.00}}
\put(50.00,30.00){\circle*{2.00}}
\put(50.00,10.00){\circle*{2.00}}
\put(10.00,50.00){\line(1,0){40.00}}
\put(50.00,50.00){\line(0,-1){40.00}}
\put(50.00,10.00){\line(-1,0){20.00}}
\put(30.00,10.00){\line(-1,1){20.00}}
\put(10.00,30.00){\line(0,-1){20.00}}
\put(50.00,30.00){\line(-1,0){20.00}}
\end{picture}
\hspace{1in} (b)
\unitlength=1.00mm
\special{em:linewidth 0.4pt}
\linethickness{0.4pt}
\begin{picture}(53.00,53.00)
\put(10.00,53.00){\makebox(0,0)[cc]{a}}
\put(29.00,53.00){\makebox(0,0)[cc]{b}}
\put(50.00,53.00){\makebox(0,0)[cc]{c}}
\put(13.00,33.00){\makebox(0,0)[cc]{d}}
\put(33.00,33.00){\makebox(0,0)[cc]{e}}
\put(53.00,33.00){\makebox(0,0)[cc]{f}}
\put(10.00,6.00){\makebox(0,0)[cc]{g}}
\put(30.00,6.00){\makebox(0,0)[cc]{h}}
\put(50.00,6.00){\makebox(0,0)[cc]{i}}
\put(10.00,50.00){\circle*{2.00}}
\put(10.00,30.00){\circle*{2.00}}
\put(10.00,10.00){\circle*{2.00}}
\put(30.00,50.00){\circle*{2.00}}
\put(30.00,30.00){\circle*{2.00}}
\put(30.00,10.00){\circle*{2.00}}
\put(50.00,50.00){\circle*{2.00}}
\put(50.00,30.00){\circle*{2.00}}
\put(50.00,10.00){\circle*{2.00}}
\put(10.00,50.00){\line(1,0){40.00}}
\put(50.00,50.00){\line(0,-1){40.00}}
\put(30.00,50.00){\line(0,-1){40.00}}
\put(10.00,50.00){\line(0,-1){40.00}}
\end{picture}



\finishtbl

\printanswers

\end{document}