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


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

%\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}
How many strings of 8 ASCII characters contain the character \% at least
once? Note that there are 128 ASCII characters.
\answer (4.1 - 17)
There are $128^8$ strings all together. $127^8$ strings
have no occurence of \% in them.  Hence $128^8-127^8$ is the
number in which \% occurs at least once.


\prob{8}
Let $x$ be a positive real number and $n$ any positive integer.
Show that there is a positive integer $j$ such that the
distance from $jx$ and some integer is $\leq {1\over n}$.

\bigskip
Hint:
For each j there are integers $k$ and $m$ with
$0\leq m \leq n-1$ so that
$$k+{m\over n}\leq jx \leq k+{m+1\over n}$$

\answer ( 4.2 - 17)
The hint is true because for any real number $jx$ there is an
integer $k$ with $k\leq jx\leq k+1$.  We then divide the
interval $[k,k+1]$ into $n$ subintervals of length $1\over n$ to
see that we must have some $m$.
\par By the pidgeon hole principle we can find $j<j'$ that have the
same $m$ as in the hint, i.e.
 $$k+{m\over n}\leq jx \leq k+{m+1\over n}$$
 $$k'+{m\over n}\leq j'x \leq k'+{m+1\over n}$$
for some integers $k,k'$.  This is because there are infinitely many
$j$'s but only $n$ possible $m's$.  We claim that
$(j'-j)x$ is within $1\over n$ of the integer $k'-k$.
\par Since negation reverses inequalities
 $$-k-{m+1\over n}\leq -jx \leq -k-{m\over n}$$
So that adding the last two inequalities we get:
 $$k'-k -{1\over n}\leq (j'-j)x \leq k'- k+ {1\over n}$$
So $(j'-j)x$ is within ${1\over n}$ of the integer $k'-k$.

\prob{8}
One hundred tickets numbered $1,2,\ldots,100$ are to be sold to 100 different
people. Eleven prizes are awarded,
a grand prize (a scuba diving trip to the
Caribbean island of Bonaire), and 10 consolation prizes (a round-trip
bus ticket to Milwaukee not including taxes or gratuities).

How many ways are there to distribute the prizes?
Assume each person can win at most one prize.

\answer (4.3-17)
There are 100 choices for the grand prize.  To award the bus tickets
we must then choose 10 tickets out of the remaining 99. Hence the
answer is
 $$100\times \left(\begin{array}{cc} 99\\ 10 \end{array}\right) $$


\prob{8}
Ten sections from a book are to be tested on the second midterm.
Each section of the book ends with 20 exercises.
The instructor
randomly chooses one exercise from each section to put on the exam.

(a) What is the probability that every problem chosen is exercise 17?

(b) What is the probability that every problem chosen is exercise 17
except exactly one?


\answer (4.4- ??)
\par (a) There are $20^{10}$ possible exams.
Only one has problem 17 of each section on it. So
$${1\over 20^{10}}$$
\par (b) There are $10\times 19$ problems which are not 17. Hence
there are 190 exams as described. So
$${190} \over 20^{10}$$

\prob{8}
How many strings of decimal digits (0-9) are there of length twenty
which contain exactly one zero, two ones, and three twos?

\answer (4.6-17)\par
Choose one digit to be the zero,
 $\left(\begin{array}{c} 20\\ 1\end{array}\right)$
two of the remaining to be ones
 $\left(\begin{array}{c} 19\\ 2\end{array}\right)$
and three of the remaing to be twos
 $\left(\begin{array}{c} 17\\ 3\end{array}\right)$
the other 14 digits can be taken arbitrarily from the 7 digits
3-9. There are $7^{14}$ ways to do this.
$$\left(\begin{array}{c} 20\\ 1\end{array}\right)
\left(\begin{array}{c} 19\\ 2\end{array}\right)
\left(\begin{array}{c} 17\\ 3\end{array}\right)
7^{14}$$

\prob{8}
Find a recurrence relation for the number, $S_n$,
of decimal (0-9) strings of length $n$ which contain at least two
consecutive digits which are both 9's.

\answer (5.1-17)
The strings of length $n+1\geq 3$ which contain
at least two consecutive $9$'s can divided as follows.  Either the
 \par\noindent  first two digits are  $99$, there are $10^{n-1}$ such strings
 \par\noindent  or the first digit is not a $9$, there are $9S_n$ such strings
 \par\noindent  or the first digit is a $9$ and the second is not, there are
$9S_{n-1}$ of these.
 \par Hence $$S_{n+1}=10^{n-1}+9S_n + 9S_{n-1}$$

\prob{8}
Determine values of the constants $A$ and $B$ so that
$a_n=An+B$
is a particular solution of
$a_n=a_{n-1}-2a_{n-2}+n$.

\answer (5.2-25)
\par $An+B=A(n-1)+B-2(A(n-2)+B)+n$
\par $An+B=An-A+B-2An+4A-2B+n$
\par $An+B=(A-2A+1)n -A+B+4A-2B$
\par $An+B=(-A+1)n -A+B+4A-2B$
\par $\;\;\;\;\;\;\;\;\;\;0=(-2A+1)n +(3A-2B)$
\par\noindent For this to be true for every $n$ we must
have that $-2A+1=0$ and $3A-2B=0$.  So $A={1\over 2}$ and
so $B={3\over 4}$.  Hence $a_n={1\over 2}n+{3\over 4}$


\prob{8}
How many elements are in the union of four sets if the sets have
100,200,300,400 elements respectively, each pair of sets has
50 elements in common, each triple has 10 elements in common,
and there is exactly one element in all four sets?

\answer (5.5-17)
$$100+200+300+400-\left(\begin{array}{cc}4\\2 \end{array}\right)50
+\left(\begin{array}{cc}4\\3 \end{array}\right)10-1=739
$$


\prob{4}
Suppose that the function $f$ from $A$ to $B$ is a one-to-one
correspondence.  Let $R$ be the relation that equals the graph
of $f$. That is $R=\{(a,f(a))\;:\:a\in A\}$.
What is $R^{-1}$?

\answer (6.1-17)
\par It is the graph of the inverse function or
$$R^{-1}=\{(f(a),a)\;:\;a\in A\}$$

\prob{8}
Let
$$M_R=\left[\begin{array}{ccc}
1 & 1 & 0 \\
1 & 0 & 1 \\
0 & 1 & 1 \\
\end{array}\right]$$
represent the relation $R$.  Find a matrix which represents
$R^2=R\circ R$.
\answer (6.3-9)
\par
$$M_{R^2}=\left[\begin{array}{ccc}
1 & 1 & 1 \\
1 & 1 & 1 \\
1 & 1 & 1 \\
\end{array}\right]$$

\prob{8}
Let $R\subseteq\{1,2,3,4\}\times\{1,2,3,4\}$ be the following binary
relation:
 $$R=\{(1,3),(4,4),(4,2),(3,4),(2,1)\}$$
Draw a digraph picture for $R$.  Find a path of length 6 starting at 1 and
ending at 2.
\answer (6.4-16,17)
\par 1,3,4,4,4,4,2 is a path of length six.


\prob{8}
For any $n=2,3,4,\dots,15$ define $f(n)=p$ where $p$ is the least
prime which divides $n$.  Define the relation $x\equiv y$ on this
set by $x\equiv y$ iff $f(x)=f(y)$.

(a) Prove that $\equiv$ is
an equivalence relation on the set $\{2,3,4,\dots,15\}$.

(b) What are its equivalence classes?

\answer (6.5-6,17)
 \par\noindent (a) A relation is an equivalence relation iff it is reflexive,
symmetric and transitive.
 \par $x\equiv x$ iff $f(x)=f(x)$ so it is reflexive
 \par $x\equiv y$ implies $f(x)=f(y)$ implies $f(y)=f(x)$ implies $y\equiv x$
so it is symmetric
 \par $x\equiv y$ and $y\equiv z$ imply $f(x)=f(y)=f(z)$ so $x\equiv z$.
so this relation is transitive.
 \par\noindent (b)  $2$ is the smallest prime.  The equivalence classes are
\par $\{2,4,6,8,10,12,14\}$
\par $\{3,9,15\}$
\par $\{5\}$
\par $\{7\}$
\par $\{11\}$
\par $\{13\}$



\prob{8}
Draw the Hasse Diagram for the partial order $(P(\{a,b,c\},\subseteq))$.

\answer (6.6)
\par See text page 421.

\finishtbl

\printanswers

\end{document}

