\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{psfig}
\usepackage{graphics}
\usepackage[pdflatex]{graphicx}
\input{macros-course}
 
\newif\ifspaceout
\spaceouttrue
%%\spaceoutfalse
\newcommand{\smallspace}{\ifspaceout\vspace{1in}\fi}
\newcommand{\mediumspace}{\ifspaceout\vspace{2in}\fi}
\newcommand{\largespace}{\ifspaceout\vspace{4in}\fi}
\newcommand{\nextproblem}{\ifspaceout\newpage\fi}

\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}

\newcommand{\bij}{\mathbin{\mbox{\rm bij}}}
\newcommand{\inj}{\mathbin{\mbox{\rm inj}}}
\newcommand{\sur}{\mathbin{\mbox{\rm sur}}}
\newcommand{\ran}[1]{\text{range}(#1)}
\newcommand{\Union}{\bigcup}

\newcommand{\eqdef}{\mathbin{\mbox{::=}}}

\newcommand{\ROT}{\mbox{ROT}}
\newcommand{\FBT}{\mbox{FBT}}
\newcommand{\brep}{\mbox{rot-to-fbt}}
\newcommand{\unrep}{\mbox{fbt-to-rot}}
\newcommand{\nil}{\mbox{\texttt{()}}}
\newcommand{\sz}{\mbox{size}}
\newcommand{\cons}{\mbox{cons}}
\newcommand{\sbtr}{\mbox{subtrees}}
\newcommand{\kcomp}[1]{\bar{#1}}

\newcommand{\fins}{\mathcal{F}}

\newcommand{\kpfend}{}

\newcommand{\kskip}[1]{}

\newcommand{\pts}[1]{\relax[#1 points]\enskip\ignorespaces}
\newcommand{\onept}{\relax[1 point]\enskip\ignorespaces}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
   \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother

\askaboutsolutions

\begin{document}


\ifshowsolutions
{
\begin{center}
{\large \bf
Exam 2 Solutions}

November 22, 2000
\end{center}
\spaceoutfalse
\else
\begin{center}
{\huge \bf
6.042 Exam 2}

November 15, 2000
\end{center}

\fi

\ifshowsolutions
\else
\smallspace


\begin{tabbing} 
\hspace{1.5in}\=Name:\hspace{1in}\=\underline{\hspace{2.5in}}\\
\\
\>Tutorial Leader:\>\underline{\hspace{2.5in}}\\
\\
\>DO NOT WRITE IN THIS SPACE
\end{tabbing}
\smallspace
\begin{eqnarray*}
\hbox{Problem 1:}& \underline{\hspace{1in}} & / \;\;25\\
\hbox{Problem 2:}& \underline{\hspace{1in}} & / \;\;10\\
\hbox{Problem 3:}& \underline{\hspace{1in}} & / \;\;25\\
\hbox{Problem 4:}& \underline{\hspace{1in}} & / \;\;35\\
\hbox{Problem 5:}& \underline{\hspace{1in}} & / \;\;15\\
\hbox{Problem 6:}& \underline{\hspace{1in}} & / \;\;21\\
\hbox{Problem 7:}& \underline{\hspace{1in}} & / \;\;45\\
\hbox{Problem 8:}& \underline{\hspace{1in}} & / \;\;24\\
\hbox{Total:}& \underline{\hspace{1in}} & / \;200
\end{eqnarray*}
\nextproblem
\fi


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{25} \textbf {Summations}

Find the closed form for each of the expressions listed below.  Give
your answer in simplified form.

\problempart {\bf (10 points)}: $ \sum_{i=x}^{y} 2i+1 $

\solution{ \bigskip
{\bf Solution:}

There are two ways of doing this problem.  In the first, we re-form the 
sum so the lower limit is 0 instead of $x$ and apply the arithmetic sum 
formula.  

$$\sum_{i=x}^y 2i+1 = \sum_{i=0}^{y-x} 2(i+x)+1$$
$$= \sum_{i=0}^{y-x} 2i + 2x+1$$
$$= (y-x+1)(2x+1) + 2 \sum_{i=0}^{y-x} i $$
$$= (y-x+1)(2x+1) + 2 \frac{(y-x)(y-x+1)}{2} $$
$$= (y-x+1)(2x+1 + y-x) = (y-x+1)(y+x+1) = ((y+1)-x)((y+1)+x) $$
$$= (y+1)^2 - x^2.$$


In the second, we express this sum as the difference of two summations,
one involving only $y$ and one involving only $x$.  

$$\sum_{i=x}^{y} 2i+1 = \sum_{i=0}^{y} 2i + 1 - (\sum_{0=1}^{x-1} 2i +
1).$$

Now, since 

$$\sum_{i=0}^n 2i+1 = n+1 + 2\frac{n(n+1)}{2} = n+1 + n(n+1) = n^2 +
2n+1 = (n+1)^2,$$

we can evaluate this to

$$(y+1)^2 - x^2.$$
}
\mediumspace
\problempart {\bf (15 points)}:
$ \sum_{i=0}^{\infty} \sum_{j=1}^n \left(\frac{j}{j+2}\right)^i $

\solution{ \bigskip
{\bf Solution:}

First, we reorder the summations to get

$$\sum_{j=1}^n \sum_{i=0}^{\infty} \left(\frac{j}{j+2}\right)^i.$$

We can do this reordering because the value of $j$ never depends on the
value of $i$, we just use every possible pair of values for a nonnegative 
$i$ and a $j$ between 1 and $n$.

Evaluating the inner summation, which is just an infinite geometric
series, we get

$$\sum_{j=1}^n \frac{1}{1 - \frac{j}{j+2}}$$
$$= \sum_{j=1}^n \frac{j+2}{2}$$
$$= n + \frac{1}{2}\sum_{j=1}^n j$$
$$= n + \frac{n(n+1)}{4}$$

which simplifies to $\frac{1}{4}n^2 + \frac{5}{4}n$.

}

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{10} \textbf {Bounding Infinite Sums}
% not multiple choice (but could be)

Using the Integral Method, give an upper bound for 
\[\sum_{i=1}^n \frac{3}{i^{10}} \] 
 
\solution{

\textbf{Solution:}\\
\medskip
Since $f(k)=\frac{3}{i^{10}}$ is monotonically decreasing for $x>1$, we have:
    \begin{eqnarray*}
      \sum_{i=1}^n{\frac{3}{i^{10}}} &=& 3 + \sum_{i=2}^n{\frac{3}{i^{10}}} \\
      &\leq& 3+ \int_1^n{\frac{3}{x^{10}}}dx\\
      &=& 3+ 3\int_1^n{\frac{1}{x^{10}}}dx\\
      &=& 3 + 3\left [{\frac{-1}{9x^{9}}}\right ]_1^n\\
      &=& 3 + \left [{\frac{-1}{3x^{9}}}\right ]_1^n\\
      &=& 3 - \frac{1}{3n^{9}} + \frac{1}{3}\\
      &=& \frac{10}{3} - \frac{1}{3n^{9}}
    \end{eqnarray*}
    Hence, $\sum_{i=1}^n \frac{3}{x^{10}} \leq \frac{10}{3} - \frac{1}{3n^{9}}$.

}

\nextproblem
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{25} \textbf {Asymptotic Notation}

Determine which of the eight choices below best describes each
function's asymptotic behavior.  No proofs are necessary.  {\bf (5
points each)}

\begin{tabbing}
XXX\=XXXXXXXXXXXX\=\kill
\>$\theta (n)$\>$\theta (n!)$\\
\>$\theta (n\log n)$\>$\theta (n^2)$\\
\>$\theta (1)$\>$\theta (2^n)$\\
\>$2^{\theta(n)}$\>None of the above
\end{tabbing}

\problempart  $g(n) = n + \ln n + (\ln n)^2$.

\solution{\bigskip
{\bf Solution:}

$\theta(n)$

We know that for sufficiently large $n$, $n > (\ln n)^2 > \ln n$.  
(For instance, if $n > e^2$ then $(\ln n)^2 = 4 < e^2$.)  Thus,
for sufficiently large $n$, 

$$n + \ln n + (\ln n)^2 < n + n + n = 3n.$$

Furthermore, as long as $\ln n$ is positive, 

$$n + \ln n + (\ln n)^2 > n.$$

Thus, for all sufficiently large $n$,  $n < g(n) < 3n$, so $g(n) = 
\theta(n)$.  
}

\smallspace
\problempart $h(n) = \frac{n^2 + 2n - 3}{n^2 - 1}$

\solution{\bigskip
{\bf Solution:}

$\theta(1)$

Dividing the top and bottom by $n-1$ yields

$h(n) = \frac{n+3}{n+1}$.  

Now, since the top is greater than the bottom, $h(n) > 1$ for all $n > -1$.
Furthermore, solving the equation $\frac{n+3}{n+1} < 2$ yields the solution
$n > 1$.  So for all $n > 1$, $h(n) < 2$.  

Thus, for all $n > 1$, we have $1 < h(n) < 2$ so $h(n) = \theta(1)$.
}

\smallspace
\problempart $j(n) = \sum_{i = 0}^n 2^{2i+1}$

\solution{\bigskip
{\bf Solution:}

$2^{\theta(n)}$

Putting the summation in closed form yields $j(n) = 2(4^n)/3$.

Now certainly, $\log_2 j(n) = \log_2(2/3) + n\log_2(4) = \theta(n)$.  Thus, 
$j(n) = 2^{\theta(n)}$.  However, as we showed in tutorial, $\neg (4^n = 
O(2^n))$ so $\neg (j(n) = \theta(2^n))$.  So $2^{\theta(n)}$ best 
describes
the asymptotic behavior of $j(n)$. 
}

\smallspace
\problempart $k(n) = (2 + \sin (n))2^{n + \sin(n)}$.

\solution{\bigskip
{\bf Solution:}

$\theta(2^n)$

We know that $\sin n \geq -1$ so $k(n) \geq (2-1)2^{n-1} = \frac122^n$.

We also know that $\sin n \leq 1$ so $k(n) \leq (2+1)2^{n+1} = 6\cdot2^n$.

Thus, $\frac12 2^n \leq k(n) \leq 6\cdot2^n$, so $k(n) = \theta(2^n)$.
}

\smallspace
\problempart $f(n) = \ln ((n^2)!)$.

\solution{\bigskip
{\bf Solution:}

None of the above.

By Stirling's approximation, we know that $l(n) = \theta(n^2 \ln n^2) =
\theta (n^2 \ln n)$.  Now, this grows faster than $\theta(1), \theta(n),
\theta(n^2)$ and $\theta(n \log n)$, and slower than $\theta(n!),
\theta(2^n)$ and $2^{\theta(n)}$, so ``none of these'' is the correct
answer. 

}

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 4
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \pts{35} \textbf {3-coloring Grid Graphs}

In Exam 1, we proved that an $m$ by $n$ grid graph is always
2-colorable.  Thus, it must be 3-colorable.  However, with 3 colors,
we suddenly get a lot of choices for how to color the graph.  In this
problem we will solve the question ``How many ways are there
to 3-color a $3$ by $n$ grid graph?''

(Recall that a 3-coloring of a graph is an assignment of one of three
colors to each vertex in the graph such that if two vertices are
connected by an edge, they must have different colors.  We consider
two 3-colorings different if any vertex is colored differently between
the two.)

\problempart {\bf (8 points)} Suppose we want to color the
graph by first coloring the first $n-1$ columns, then choosing a
coloring for the last column.  However, the number of ways we can
color the last column is dependent on which coloring we choose.  There are
two cases to consider.

\begin{figure}[htbp]
\centerline{\psfig{figure=3color.eps,height=1.5in}}
\end{figure}

In the first case, the vertices $(n-1,1)$ and $(n-1,3)$ are the same color.

In the second case, the vertices $(n-1,1), (n-1,2)$, and $(n-1,3)$
are all different colors.  

\begin{itemize}
\item[1.] How many ways can we color the last column in the first
case?  \underline{\hspace{1in}} \solution{5}

\item[2.] Of the ways to color the last column in the first case, how
many use three different colors? \underline{\hspace{1in}} \solution{2}

\item[3.] How many ways can we color the last column in the second case?
\underline{\hspace{1in}} \solution{4}

\item[4.] Of the ways to color the last column in the second case,
how many use three different colors? \underline{\hspace{1in}}
\solution{2}

\end{itemize}

\nextproblem

\problempart {\bf (10 points)} Let $A_n$ be the number of ways to
3-color a $3$ by $n$ grid graph such that the last column is colored
with only 2 colors.  Let $B_n$ be the number of ways to 3-color a $3$
by $n$ grid graph such that the last column is colored with three
different colors.

Formulate a system of recurrence relations for $A_n$ and $B_n$, and give
the initial values $A_1$ and $B_1$.

\solution{\bigskip
{\bf Solution:}

$A_n = 3A_{n-1} + 2B_{n-1}$.

$B_n = 2A_{n-1} + 2B_{n-1}$.

$A_1 = B_1 = 6.$
}

\mediumspace

\problempart {\bf (7 points)} Suppose that 

$$A_n = xc_1^n + yc_2^n$$
$$B_n = xd_1c_1^n + yd_2c_2^n$$

is the solution to the recurrence relation you found in part (b).
Find the number of ways to 3-color a 3 by $n$ grid graph 
in terms of $c_1, c_2, d_1, d_2$, and $n$ and no other variables.

\solution{\bigskip
{\bf Solution:}

Plugging in $A_1 = 6$ and $B_1 = 6$ we get that 
$xc_1 = 6 - yc_2$ so $6 = d_1(6-yc_2)+yd_2c_2$.  Solving for $y$ we get

$$y = \frac{6 - 6d_1}{(d_2 - d_1)c_2},$$

so 

$$x = \frac{-6 + 6d_2}{(d_2 - d_1)c_1}.$$

Finally, the number of ways to 3-color a 3 by $n$ grid graph is $A_n + B_n$
which is just

$$A_n+B_n = \left(\frac{-6+6d_2}{(d_2-d_1)c_1}\right)(1+d_1)c_1^n +
\left(\frac{6 - 6d_1}{(d_2-d_1)c_2}\right)(1+d_2)c_2^n$$

this can be simplified a bit, to 

$$A_n+B_n = 6(d_1+1)\left(\frac{d_2-1}{d_2-d_1}\right)c_1^{n-1} -
6(d_2+1)\left(\frac{d_1-1}{d_2-d_1}\right)c_2^{n-1}.$$

}


\nextproblem

\problempart {\bf (10 points)}  Find $c_1, c_2, d_1,$ and $d_2$ such that

$$A_n = xc_1^n + yc_2^n$$
$$B_n = xd_1c_1^n + yd_2c_2^n$$

is the general form for the system of recurrence relations you found in 
part (b).  

\solution{\bigskip
{\bf Solution:}

Let's guess that for some $c \neq 0$ and some $d$, that $A_n = c^n$
and $B_n = dc^n$.  Then, substituting into the recurrence relation
yields

$$c^n = 3c^{n-1} + 2dc^{n-1}$$

and 

$$dc^n = 3c^{n-1} + 2dc^{n-1}$$

Dividing the top equation by $c^{n-1}$ yields $c = 3+2d$.  Subsituting
this into the bottom equation and gathering terms yields $2d^2 + d - 2 = 0$,
so 

$$d = \frac{-1 \pm \sqrt{17}}{4}.$$

This gives two solutions, $c_1 = \frac{5+\sqrt{17}}{2}, d_1 =
\frac{-1+\sqrt{17}}{4}$ and $c_2 = \frac{5-\sqrt{17}}{2}, d_2 =
\frac{-1-\sqrt{17}}{4}$.  

This was not required by the question, but for a sense of
completeness, using these values and simplifying, the number of ways
to 3-color a 3 by $n$ grid graph is

$$\left(\frac{9+3\sqrt{17}}{2\sqrt{17}}\right) \left( \frac{5+
\sqrt{17}}{2} \right)^n +
\left(\frac{-9+3\sqrt{17}}{2\sqrt{17}}\right) \left( \frac{5-
\sqrt{17}}{2} \right)^n.$$



}
\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 5
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{15} \textbf {Nonhomogenous Recurrence}

Give a closed-form solution to the following nonhomogenous recurrence
relation,

$$G_n = 2G_{n-2} + 2^{n-1}$$

such that $G_0 = 1$ and $G_1 = 2$.

\solution{\bigskip {\bf Solution:}
First we solve the homogenous part.  The characteristic equation
is 

$$r^2 - 2 = 0$$

so $r = \pm \sqrt{2}$ are the solutions.  Thus, our general solution is of 
the form $\alpha_1 \sqrt{2}^n + \alpha_2 (-\sqrt{2})^n$.  

For our particular solution, we guess that $c2^n$ will work, where $c$
is a constant.  Plugging in, this gives us

\begin{eqnarray*}
c2^n &=& 2c2^{n-2} + 2^{n-1}\\
     &=& c2^{n-1} + 2^{n-1}\\
2c2^{n-1} &=& c2^{n-1} + 2^{n-1}\\
c2^{n-1} &=& 2^{n-1}\\
c &=& 1
\end{eqnarray*}

So we must now solve for $\alpha_1$ and $\alpha_2$ such that

$\alpha_1 + \alpha_2 + 2^0 = \alpha_1+\alpha_2 +1 = 1$

Therefore, $\alpha_2 = -\alpha_1$.  Furthermore, 

$$\sqrt{2}\alpha_1 + (-\sqrt{2})(-\alpha_1) + 2^1 = 2\sqrt{2}\alpha_1 + 2 = 2$$

so $\alpha_1 = \alpha_2 = 0$ are our solutions.  So the
closed form solution for the recurrence relation is just

$$G_n = 2^n.$$

}
\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 6
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \pts{21} \textbf {A Strange Set}
% difficulty: medium-hard

Define the function $fp(x) = x - \floor{x}$.  ($fp$ stands for
``fractional part.'')  Recall that $\floor{x}$ is the greatest integer
less than or equal to $x$.  So, $\floor{8.2} = 8$ and $\floor{-2.3} =
-3$.   Let $h = \sqrt{37}$

Let $S = \{ n \in \mathbb{Z} \ | \ n \neq 0 \wedge  fp(nh) < 0.01 \}$. 


Use the pigeonhole principle to prove that $S$ is nonempty.  Other methods
will not get credit.


\solution{\bigskip
{\bf Solution:}

We let $fp(nh)$ be our pigeon (for each $n$ there is one pigeon), and let
the pigeonholes be ranges of size $.01$.  So the first pigeonhole would be
those $n$ for which the first two digits of $fp(nh)$ after the decimal
point are 0 and 0, the secound would have digits 0 and 1, and so on.  
Since there are infinitely many pigeons and only 100 pigeonholes, by the
pigeonhole principle, there must be a pigeonhole with more than one pigeon
in it.

Let $m$ and $n$ be two different numbers such that $fp(nh)$
and $fp(mh)$ end up in the same hole.  Suppose, without loss
of generality, that $fp(nh) \geq fp(mh)$.  Then,
$fp(nh) - fp(mh) < .01$.

Suppose $l$ and $m$ are the digits associated with the pigeonhole both
$n$ and $m$ fall into.  Then, we can write $k = 10l + m$ and write

$nh = \frac{k}{100} + \alpha + \floor{nh}$ and

$mh = \frac{k}{100} + \beta + \floor{mh}$ where $0 \leq \beta \leq \alpha 
< .01$

Now, we can subtract these two equations and get

$$nh-mh = \alpha - \beta + \floor{nh}-\floor{mh}.$$

Since $\alpha \geq \beta$ we know $\alpha - \beta \geq 0$.  Since $\alpha 
< .01$ we know $\alpha < 1$, so $\alpha - \beta < 1$.  Thus, 

$$nh-mh = \alpha - \beta + \floor{nh-mh}.$$

by the definition of the floor function.  Thus, $\alpha - \beta = 
fp(nh-mh) = fp ((n-m)h)$.  Since $n-m$ is an integer and is not equal to 0 
(since $m$ and $n$ were different numbers), and since $0 \leq fp((n-m)h) 
< .01$ we know $n-m$ must be an element of $S$.  Thus, $S$ is nonempty.
}
\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 7
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \pts{45} \textbf {Rearranging the Alphabet}

For this problem you do not need to evaluate an expression fully: you
may leave it in terms of binomial coefficients, powers of numbers,
factorials, and so on.  For this problem we consider the alphabet to
consist only of capital letters.

\problempart {\bf (15 points)} How many different strings are there
of 10 letters such that no letter is used more than once?

\solution{\bigskip
{\bf Solution:}

This is just asking for a permutation of 10 out of 26 objects.  Thus,
the answer is $P(26,10) = \frac{26!}{(26-10)!} = \frac{26!}{16!}$.  
}
\mediumspace

\problempart {\bf (15 points)} How many ways can you rearrange the
alphabet (using each letter only once) so that none of the words ``TEST,''
``EXAM,'' and ``STUDY'' appear as consecutive letters in your arrangement?


\solution{\bigskip
{\bf Solution:}

We proceed by using the inclusion/exclusion principle.  It makes our
job slightly easier that the word ``TEST'' can never appear in a
rearrangement of the alphabet, since ``TEST'' contains the letter T
twice.  The number of valid arrangements is equal to $A-E-S+B$ where
$A$ is the number of ways we can rearrange the alphabet, $E$ is the
number of ways we can rearrange the alphabet so that ``EXAM'' appears,
$S$ is the number of ways we can rearrange the alphabet so that
``STUDY'' appears, and $B$ is the number of ways we can rearrange the
alphabet so that both ``EXAM'' and ``STUDY'' appear.

$A = 26!$, since there are $26!$ ways of putting 26 distinct elements in order.

$E = 23!$. since there are $23!$ ways of ordering 23 objects: the string 
``EXAM'' and the 22 other letters in the alphabet.

$S = 22\cdot 21! = 22!$ by the same reasoning.

$B = 19!$ by the same reasoning; this time there are two strings, ``EXAM'' 
and ``STUDY'' and 17 letters.

So the final answer is $26! - 23! - 22! + 19!$.
}

\nextproblem

\problempart {\bf (15 points)} How many ways are there to choose a
collection of 30 letters such that none of the words ``EXAM,'' ``STUDY,''
and ``TEST'' can be formed using the letters in the collection?

\solution{\bigskip
{\bf Solution:}

Again, we prooced by inclusion/exclusion.  A collection is not an ordered
object, and we are obviously allowed to use letters more than once, so we 
use the formula for combinations with repetitions.  Thus,
the number of ways to choose a collection of 30 letters is
$\binom{30+26-1}{30} = \binom{55}{30}$.

The number of ways to make a collection of 30 letters with $k$ specified
letters is the number of ways to make a collection of $30-k$ letters (to
which we add the specified letters).  Thus, it is $\binom{30+26-1-k}{30-k}
= \binom{55-k}{30-k}$.  

Let $A$ be the set of all collections which contain the letters `E', `X',
`A', and `M'.  Let $B$ be the set of all collections which contain the
letters `S', `T', `U', `D', and `Y'.  Let $C$ be the set of all
collections which contain the letters `S', `E', and which contains the
letter `T' at least twice.  What we want is

$$| A \cup B \cup C | = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B
\cap
C| + |A \cap B \cap C|$$

Now we note that $A \cap B$ has 9 fixed letters, $A \cap C$ and $B \cap C$
have 7, and $A \cap B \cap C$ has 10 fixed letters.  (For instance,
``EXAM'' and ``TEST'' overlap so we only have to have the `E' once to form
both words).  Thus, 

$$|A \cup B \cup C| = \binom{51}{26} + \binom{50}{25} + \binom{51}{26} -
\binom{46}{21} -
\binom{48}{23} - \binom{48}{23} + \binom{45}{20}$$

So our answer is

$$ \binom{55}{30} - 2\binom{51}{26} - \binom{50}{25} + 2\binom{48}{23}
+ \binom{46}{21} - \binom{45}{20}.$$


which, if you're curious, evaluates to about 2.5 quadrillion.

}
\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 8
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{24} \textbf{Finite and Infinite Sets}

For each of the following sets, state whether it is finite, countably
infinite, or uncountably infinite.  If it is finite, give its size.
If it is countably infinite, give an injective function from the given
set to $\mathbb{N}$.  If it is uncountable, give a brief argument.

\problempart {\bf (6 points)} $R = \mathcal{P}(\{2^{-i} \ | \ i \in
\mathbb{N}\})$

\solution{\bigskip
{\bf Solution:}

Uncountable.  Proof by contradiction by the diagonalization method:
suppose $S_0, S_1, \ldots$ is a complete list of all elements of $R$.  
Consider the set $S = \{ 2^{-i} \ | \ 2^{-i} \notin S_i\}$.  Since $S$
is a member of $R$ it must appear in the list somewhere, so assume its
number is $n$.  This is a contradiction since $2^{-n} \in S 
\Leftrightarrow 2^{-n} \notin S$.  Thus, there must not be any such 
complete list.
}

\smallspace

\problempart {\bf (6 points)} $S = \mathcal{P}(\mathbb{N}) \cap
\mathcal{P}(\{ 2^{-i} \ | \ i \in \mathbb{N}\})$

\solution{\bigskip
{\bf Solution:}

Finite.  The only two subsets in common between $\mathbb{N}$ and $\{
2^{-i}
\ | \ i \in \mathbb{N}\}$ are the subset containing $1$ and the
empty set.  Thus, its 
size is 2.
}



\smallspace
\problempart {\bf (6 points)} $T$, the set of all finite sets of
prime numbers.

\solution{\bigskip
{\bf Solution:}

Countable.  Each finite set of prime numbers defines a different
integer, namely the product of all the numbers in the set.  This
mapping is injective since the prime factorization of a number is
unique.  Thus, $N$ can be mapped into the natural numbers, so $N$ is
countable.  (We can count $T$ by listing the sets that map to integers
in ascending order of the integers.  So the first element would be
$\emptyset$, the second would be $\{2\}$, and the fifth would be $\{2,
3\}$, et cetera).

}

\smallspace
\problempart {\bf (6 points)} $U$, the set of all equivalence classes
of the equivalence relation $\{ (x, y) \ | \ x, y \in \mathbb{R}$ and
$x-y \in \mathbb{Q}\}$

\solution{\bigskip
{\bf Solution:}

Uncountable.  Each equivalence class is a countable set: if $C$ were
countable we could express $R$ as the cartesian product of two
countable sets (namely, the set of equivalence classes and
$\mathbb{Q}$).  But this would make $R$ countable and it is not.
}


\end{problems}

\end{document}



