% 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\conj{\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 Exam 1 \hfill A. Miller \hfill Spring 2002
                                       \hfill Math 240\hfill}}
\markboth\header\header
\newcount\probno
\newcount\total
\newwrite\examTBLFile


\def\evenprob{\vfill}
\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\newpage % \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}

\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{6} % 1.2  16
Show that $p\implies q$ and $(\neg q)\implies (\neg p)$ are
logically equivalent.

\answer $p\implies q$ is false iff $p$ is true and $q$ is false.
\par    $(\neg q)\implies (\neg p)$ is false iff $\neg q$ is true
 and $\neg p$ is false.
\par Hence they have the same truth table.

\prob{6} % 1.1 25
Construct a truth table for the following propositional sentence:
$$(p\orx q)\implies (p\and r)$$
\answer $$\begin{array}{c|c|c|c|}
p & q & r & (p\orx q)\implies (p\and 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 F \hfill F\hfill \\
F & T & F & \hfill T \hfill F \hfill F\hfill \\
F & F & T & \hfill F \hfill T \hfill F\hfill \\
F & F & F & \hfill F \hfill T \hfill F\hfill \\
\end{array}$$




\prob{6} % 1.3  25
Find a statement which is logically equivalent to
$$\neg [\;(\exists x \;P(x))\implies (\forall y \;Q(y))\;]$$
but in which the negation sign appears (if at all) only in front of
the predicate symbols.
\answer $(\exists x \;P(x))\conj(\exists y \;\neg Q(x))$

\prob{6} % 1.4 - 17
Let $A=\{1,2\}$ and $B=\{1,3,5\}$.  Find $A\times B$.
\answer $\{(1,1),(1,3),(1,5),(2,1),(2,3),(2,5)\}$


\prob{6} % 1.5 - 17
Let $A=\{1,3,4\}$, $B=\{2,4\}$, and $C=\{3,4,5,6\}$.  Find

\bigskip
\par (a) $|A|$

\vspace{.8in}

\par (b) $B\setminus C$

\vspace{.8in}

\par (c) $(A\cup B)\cap C$

\answer $|A|=3$, $B\setminus C=\{2\}$, $(A\cup B)\cap C=\{3,4\}$

\prob{6} % 1.6 - 29
Let $f:\rr\to\rr$ be defined by
$$f(x)=\lfloor {x}\rfloor$$ Let
 $S=\{2,5\}$.
Find  $f^{-1}(S)$.
\answer $\{x: 2\leq x<3 $ or $ 5\leq x<6\}=[2,3)\cup [5,6)$

\prob{6} % 1.7-17
Compute the following double sum:
$$\sum_{i=1}^2\sum_{j=1}^3\;(i+j)$$
\answer 21


\prob{5} % 2.2 - 9
How large a problem can be solved in 10 seconds or less using an algorithm
that when input $n$
requires $f(n)=n^2$ bit operations where each bit operation
is carried out in $10^{-9}$ seconds?
\answer   $n=10^5$

\prob{5} % 2.3 - 21
The value of the Euler $\phi$-function at the positive integer
$n$ is defined to be the number of positive integers less than
or equal to $n$ that are relatively prime to $n$.  Find
$\phi(12)$.
\answer 4

\prob{8} %1.8-49
What is smallest positive integer $k$ such that the function
$$f(n)=(n\log(n)+1)^2$$
is ${\mathcal O}(n^k)$?
\answer $k=3$ because $\log(n)$ is ${\mathcal O}(n^\epsilon)$
for any real $\epsilon>0$.

\prob{8} % 3.2 - 13
Show that $2^n > 2n+1$ for all integers  $n\geq 3$.
\answer This is proved by induction.
\par Basis: $n=3$ this true because $2^3=8>7=2*3+1=7$
\par Inductive step. Assume $2^n > 2n+1$ and $n\geq 3$.
Then
$$2^{n+1}=2*2^n=2^n+2^n> 2n+1+2^n>2n+1+8>2(n+1)+1$$
By inductive hypothesis and since $2^n\geq 2^3=8$.
Hence
$$2^{n+1}>2(n+1)+1$$
as we needed to show.

\prob{8} % 3.3 - 11
Let $f_n$ be the $n^{th}$ element of the Fibonacci sequence.
Prove that
$$f_1+f_3+f_5+\cdots+f_{2n-1}=f_{2n}$$
for every positive integer $n$.
\answer This is proved by induction.
\par Basis: $f_1=1=f_2$
\par Inductive Step: Assume true for $n$. Then
$$f_1+f_3+f_5+\cdots+f_{2n-1}+f_{2n+1}=f_{2n}+f_{2n+1}$$
by inductive hypothesis. But by the definition of Fibonacci sequence
$$f_{2n}+f_{2n+1}=f_{2n+2}=f_{2(n+1)}$$
and so noting that $2(n+1)-1=2n+1$
$$f_1+f_3+f_5+\cdots+f_{2(n+1)-1}=f_{2(n+1)}$$
as was to be shown.


\probx{8} % 2.6 - 5
Find a $2\times 2$ matrix $A$ so that
$$A
\left[
\begin{array}{rr}
1 & 2 \\
0 & -1
\end{array}
\right]
=\left[
\begin{array}{rr}
1 & 0 \\
3 & 2
\end{array}
\right]
$$
 Hint: Solve a system of linear equations.
\answer $$A=\left[
\begin{array}{rr}
1 & 2 \\
3 & 4
\end{array}
\right]
$$

\probx{8} % 2.4 - 21
Let $n=(\ldots a_ka_{k-1}\ldots a_2a_1a_0)_2$ be any positive
integer written in binary.
\par Let $E$ be the set of even $k$ such that $a_k=1$ and
\par let $O$ be the set of odd $k$ such that $a_k=1$.
\par\noindent Show that $n$ is divisible by
$3$ if and only if $|E|+2|O|$ is divisible by $3$.

\answer If $k$ is even, say $k=2l$ then
$$2^k=2^{2l}=4^l$$
But $4\equiv_3 1$ so it follows that
$$2^k\equiv_3 4^l\equiv_3 1^l\equiv_3 1$$
If $k$ is odd, then $k-1$ is even and hence
$$2^k=2*2^{k-1}\equiv_3 2$$
Now since $n=\sum_{k\in E}2^k+\sum_{k\in O}2^k$
it follows from above that
$$n\equiv_3  \sum_{k\in E}1+\sum_{k\in O}2$$
but
$$\sum_{k\in E}1+\sum_{k\in O}2=|E|+2|O|$$
so $3$ divides $n$ iff $n\equiv_3 0$ iff
$|E|+2|O|\equiv_3 0$ iff $3$ divides $|E|+2|O|$

\probx{8} % 2.5 - ?

\bigskip
(a) Find $d=$gcd$(54,17)$ using the Euclidean Algorithm.

\bigskip
(b) Find integers $a$ and $b$ such that $d = a \;54 \;+\; b \;17$

\answer  \par $54, 17\;\;\;\; 54=3(17)+3$
\par $3,17\;\;\;\; 17=5(3)+2$
\par $3,2$ and we see that gcd is 1.
\par $1=-1(3)+2(2)$ using $2=17-5(3)$ we get
\par $1=-1(3)+2(17-5(3))=-11(3)+2(17)$
\par $1=-11(3)+2(17)$ using 3=54-3(17) we get
\par $1=-11(54-3(17))+2(17)=-11(54)+35(17)$


\finishtbl

\printanswers

\end{document}

