\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}{\newpage}

\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}
{\large \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}} & / \;\;30\\
\hbox{Problem 4:}& \underline{\hspace{1in}} & / \;\;50\\
\hbox{Problem 5:}& \underline{\hspace{1in}} & / \;\;45\\
\hbox{Problem 6:}& \underline{\hspace{1in}} & / \;\;22\\
\hbox{Problem 7:}& \underline{\hspace{1in}} & / \;\;18\\
\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:}

$$(y+1)^2 - x^2.$$

Grading standard:
\begin{tabbing}
3 points for knowing to break up the sum (as in $\sum_0^y -
\sum_0^{x-1}$)\\
2 points for getting the limits right when breaking up\\
2 points for applying the arithmetic sum correctly\\
2 points for getting the algebra right\\
1 point for giving a simplified answer.
\end{tabbing}

Students should get at least 9 points if their answer is right.  An
example of an answer that would be right but worth only 9 points
would be

$$y(y+1) + y + 1 - x(x-1) - x$$

}



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

\solution{ \bigskip
{\bf Solution:}

$\frac{1}{4}n^2 + \frac{5}{4}n$ or $\frac{n(n+5)}{4}$ or $\frac{n^2 +
5n}{4}$

Grading standard:
\begin{tabbing}
3 point for reordering the summations\\
5 points for correctly applying the formula for an infinite geometric
series\\
2 points for correctly applying the arithmetic series formula\\
3 points for getting all the algebra right\\
2 points for simplifying
\end{tabbing}

Once again, correct answers should get at least 13 points, and then only
13 if the answer is BADLY unsimplified.  An answer like 

$$n + \frac{n(n+1)}{4}$$ 

should get 14 points.  Any of the given answers should get all 15 points.

}

\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}}} &=& 1 + \sum_{i=2}^n{\frac{3}{i^{10}}} \\
      &\leq& 1+ \int_1^n{\frac{3}{x^{10}}}dx\\
      &=& 1+ 3\int_1^n{\frac{1}{x^{10}}}dx\\
      &=& 1 + 3\left [{\frac{-1}{9x^{9}}}\right ]_1^n\\
      &=& 1 + \left [{\frac{-1}{3x^{9}}}\right ]_1^n\\
      &=& 1 - \frac{1}{3n^{9}} + \frac{1}{3}\\
      &=& \frac{4}{3} - \frac{1}{3n^{9}}
    \end{eqnarray*}
    Hence, $\sum_{i=1}^n \frac{3}{x^{10}} \leq \frac{4}{3} - \frac{1}{3n^{9}}$.

\medskip
\textbf{Grading Standard:}\\
Similar to problem 5 on pset 6.\\
-10 for not using the Integral method with wrong answer\\ 
-7 for both limits incorrect on the integral\\
-4 for one limit incorrect on the integral\\
-2 for making algebraic mistakes\\
-6 for using the Integral method but not being tight (for example, first
saying $3/i^{10} < 3/i^2$ and using the integral method from there)
}

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

Determine which of the eight choices below best describes each
function's asymptotic behavior.  No proofs are necessary.  {\bf (6
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}

\solution{
Grading Standard:
Give no partial credit, except on part (d) if they answer $2^{\theta(n)}$
instead of $\theta(2^n)$.  Give 3 points partial credit for this answer
(the function given IS 2^{\theta(n)}$ but this is not the best answer.)
}

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

\solution{\bigskip
{\bf Solution:}  \theta(n)$.
}

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

\solution{\bigskip
{\bf Solution:}  \theta(1)$.
}

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

\solution{\bigskip
{\bf Solution:}  2^{\theta(n)}$.
}

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

\solution{\bigskip
{\bf Solution:}  \theta(2^n)$.  
}

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

\solution{\bigskip
{\bf Solution:}  None of these
}

\nextproblem

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

\problempart {\bf (15 points)} How many ways are there to 3-color a
$2$ by $n$ grid graph?  Give your answer in closed form.  (Hint: come
up with a recurrence relation for $C_n$, the number of ways to color a
$2$ by $n$ grid graph, in terms of $C_{n-1}$, and figure out $C_1$
directly.)

\solution{\bigskip
{\bf Solution:}

$2\cdot 3^n$.

Grading standard:
\begin{tabbing}
XXX\=\kill
15 points for the right answer by any method.\\
5 points for understanding that given a coloring of a 2 by $n-1$ graph,
there\\
\>are 3 ways to color the remaining 2 points\\
3 points for understanding that this yields a multiplicative result.\\
3 points for coming up with something in the form $\alpha 3^n$.\\
2 points for setting up their structure correctly so their answer is the\\
\> number of colorings on a 2 by $n$ graph (as opposed to 2 by $n-1$ or
something)\\
2 points for getting the base case correct (6 ways to color a 2 by 1).
\end{tabbing}

}
\problempart {\bf (8 points)} 

\solution{\bigskip
{\bf Solution:}
1.  5

2.  2

3.  4

4.  2

Grading:
2 points for each correct answer, no partial credit.
}

\smallspace 

\problempart {\bf (7 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$.  

\solution{\bigskip
{\bf Solution:}

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

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

Grading:
\begin{tabbing}
XXX\=\kill
5 points for having the correct recurrence relations\\
3 points for having the wrong recurrence relation if it matches their
answers\\
\> for part (b).\\
2 points for having $A$ and $B$ not reversed.  \\
Give other partial credit, at your discretion, if you feel they deserve
it.
}

\problempart {\bf (4 points)} Find the values $A_1$ and $B_1$.

\solution{\bigskip
{\bf Solution:}
$A_1 = B_1 = 6$.  

Grading:  2 points each, no partial credit.

}
\smallspace

\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 of the solution to this system of recurrence relations.

\solution{\bigskip
{\bf Solution:}

$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 is the correct answer if they got parts (b) and (c) correct, however
NO PENALTY should be given if they solved the wrong recurrence (as long as
they solved the recurrence they formulated in part (c)).

Grading:
\begin{tabbing}
3 points for using $A_n = c^n, B_n = dc^n$ to find answers for $c$ and
$d$\\
1 point for using $B_n = c^n, A_n = dc^n$, et cetera.\\
4 points for algebraically working out solutions to the equations.\\
2 points for correctly indicating $c_1, c_2, d_1, d_2$.\\
\end{tabbing}
}

\nextproblem
 
\problempart {\bf (6 points)} Find a closed-form, simplified
expression for the number of ways to 3-color a $3$ by $n$ grid graph.


\solution{\bigskip {\bf Solution:} The number of ways of 3-coloring 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$$

$x = \frac{6}{\sqrt{17}}, y = \frac{-6}{\sqrt{17}}$ are the values we
solve for.  The above expression is $A_n + B_n$.  

Do NOT penalize students for starting with the wrong $c_1, c_2, d_1, d_2$,
as long as they use the ones they got in part (e).  Also, do not penalize
for using incorrect starting conditions as long as they use the ones they
found in part (d).  

Grading:
\begin{tabbing}
1 point for setting up to solve for $x$ and $y$ by using $A_1$ and
$B_1$.\\
2 points for finding each value $x$ and $y$ correctly.  
1 point for giving $A_n + B_n$ as their final answer
\end{tabbing}
}



\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 5
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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:}  $\frac{26!}{16!}$

Grading:
\begin{tabbing}
-5 points for thinking order doesn't matter $\binom{26}{10}$\\
-5 points for allowing repetitions of letters $(26^10)$\\
-10 points for both of these mistakes $\binom{35}{10}$\\
-5 points for incorrectly applying the permutation formula\\
-15 points for a mysterious answer.\\
\end{tabbing}

}
\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:}  $26! - 23! - 22! + 19!$.

Grading:
\begin{tabbing}
3 points for attempting to use inclusion/exclusion.\\
2 points for setting up inclusion/exclusion correctly.\\
2 points for getting the 26! term correct*.\\
2 points for noticing that ``TEST'' can never appear.\\
2 points for getting the 23! term correct.\\
2 points for getting the 22! term correct.\\
2 points for getting the 19! term correct.
\end{tabbing}

* If they didn't subtract from 26! they should lose the points for both
getting the 26! term and for setting up inclusion/exclusion correctly.

If they didn't set up each of the terms in terms of permutations, but
otherwise got them right (and did the same wrong thing with each term),
take off 5 points.  
 
}

\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:}
$$ \binom{55}{30} - 2\binom{51}{26} - \binom{50}{25} + 2\binom{48}{23}
+ \binom{46}{21} - \binom{45}{20}.$$

Grading:
\begin{tabbing}
3 points for realizing we need to use inclusion/exclusion and setting it
up.\\
5 points for using combinations with repetitions to come up with the
terms.\\
3 points for using the formula correct.y.\\
3 points for getting the size correct on each of the three two-set
intersections.\\
2 points for getting the size correct on the 3-set intersection.\\
\end{tabbing}

What I mean by getting the size correct is that they understand the
intersection issues (ie, that the `E' in EXAM and TEST need not be in the
collection twice).  

}
\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 6
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \pts{22} \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
Grading:
\begin{tabbing}
3 points for appearing to understand the $fp$ function.\\
3 points for understanding what it means for $fp(nh)$ to be $< 0.01$.\\
5 points for correct ``pigeons" ($fp(nh)$ for each $n \in \mathbb{Z}$.\\
5 points for correct ``pigeonholes" (ranges of size $.01$).\\
2 points for subtracting two pigeons to get an element in $S$.\\
1 points for correctly dealing with which of the elements to subtract from
which.\\
4 points for proving their element is such that $fp(nh) < 0.01$.\\
2 points for proving their element is such that $n \neq 0$.
\end{tabbing}

Note: the first 6 points are designed to be partial credit we can give to
people who never manage to come up with the pigeonhole principle
stuff.  I would say anyone who sets up the pigeonholes correctly gets the
first 3 points automatically, and anyone who deals with which of the
pigeons to subtract from which OR who proves their element is such that
$fp(nh) < 0.01$ correctly gets the second 3 points automatically.

}

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 7
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{18} \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)} $S = \mathcal{P}(\mathbb{N}) \cap
\mathcal{P}(\{ 2^{-i} \ | \ i \in \mathbb{N}\})$

\solution{\bigskip
{\bf Solution:}

Finite; 2

Grading:
\begin{tabbing}
4 points for saying "Finite"\\
2 points for giving 2 as the size.\\
1 point for giving 1 as the size.\\
\end{tabbing}
}



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

\solution{\bigskip
{\bf Solution:}

Countable.  The map $S \mapsto \prod_{p \in S} p$ is an injective map.

Grading:
\begin{tabbing}:
XXX\=\kill
2 points for saying "Countable."\\
4 points for an injective map.\\
2 points for a badly specified map but which at least gives the
impression\\
\> the student understands why $T$ is countable.
\end{tabbing}
}

\mediumspace
\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.

Grading:
\begin{tabbing}
2 points for saying "Uncountable."\\
1 point for saying there is an equivalence class for each real number as
their argument.\\
2 points for setting up some incorrect diagonalization argument\\
4 points for any correct argument.\\
\end{tabbing}

}


\end{problems}
\end{document}



