\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
Final Exam Solutions}

\end{center}
\spaceoutfalse
\else
\begin{center}
{\huge \bf
6.042 Final Exam}

Fall 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}} & / \;\;33\\
\hbox{Problem 2:}& \underline{\hspace{1in}} & / \;\;16\\
\hbox{Problem 3:}& \underline{\hspace{1in}} & / \;\;\;9\\
\hbox{Problem 4:}& \underline{\hspace{1in}} & / \;\;10\\
\hbox{Problem 5:}& \underline{\hspace{1in}} & / \;\;\;6\\
\hbox{Problem 6:}& \underline{\hspace{1in}} & / \;\;10\\
\hbox{Problem 7:}& \underline{\hspace{1in}} & / \;\;16\\
\hbox{Problem 8:}& \underline{\hspace{1in}} & / \;\;20\\
\hbox{Problem 9:}& \underline{\hspace{1in}} & / \;\;\;6\\
\hbox{Problem 10:}& \underline{\hspace{1in}} & / \;\;\;6\\
\hbox{Problem 11:}& \underline{\hspace{1in}} & / \;\;\;10\\
\hbox{Problem 12:}& \underline{\hspace{1in}} & / \;\;\;8\\
\hbox{Total:}& \underline{\hspace{1in}} & / \;150
\end{eqnarray*}
\nextproblem
\fi


\begin{problems}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{33} \textbf {Miscellaneous}

\problempart {\bf (6 points)} Circle the numbers of ALL of the
following which are logical tautologies:

1.  $(P \wedge \neg P) \vee (Q \vee \neg Q)$\\
2.  $(P \Leftrightarrow Q) \vee (\neg P \vee Q)$\\
3.  $\forall x \forall y (P(x) \wedge \neg P(x)) \Rightarrow Q(y)$

\solution{\bigskip{\bf Solution:}
1 and 3 are tautologies and 2 is not.  

In 1, $(Q \vee \neg Q)$ is always true.  Since it is one part of an or
expression, the law of domination tells us the expression is always
true.

In 2, the expression is false if $P$ is true and $Q$ is false.

In 3, the expression $P(x) \wedge \neg P(x)$ is always false.  Since
an implication is always true if its antecedent is false, the expression
$(P(x) \wedge \neg P(x)) \Rightarrow Q(y)$ is true for all $x$ and $y$.
}

\problempart {\bf (3 points)} Define the relation $R$ such that $nRm$
whenever $n$ and $m$ are natural numbers such that $|n-m|$ is the
square of a nonnegative integer.
Circle the numbers of ALL of the following which apply to $R$:

1.  A reflexive relation\\
2.  A symmetric relation\\
3.  An equivalence relation

\solution{\bigskip{\bf Solution:} 
1 and 2 apply to $R$ but 3 does not.

Since $0$ is a nonnegative integer, 0 is the square of a nonnegative
integer.  Thus, if $n = m$, then $|n-m| = 0$ so $nRm$.  Thus, 1
applies.

If $|n-m| = a$ where $a$ is the square of a nonnegative integer, then
$|m-n| = |(-1)(n-m)| = a$, so $mRn$.  Thus, 2 applies.

However, $0R1$ and $1R5$ but $\neg 0R5$, so $R$ is not transitive.
Thus, 3 does not apply.
}

\problempart {\bf (10 points)} Circle the numbers of ALL of the
following statements that are true for all $m, n > 0 \in N$.  Let $G$
be an $m$ by $n$ grid graph.

1.  There is an Euler circuit in $G$.\\
2.  There is a Hamiltonian path in $G$.\\
3.  If $m$ and $n$ are even, there is a Hamiltonian circuit in $G$.\\
4.  If $m$ and $n$ are odd, there is a Hamiltonian circuit in $G$.\\
5.  If there is a Hamiltonian circuit in $G$ then $m$ and $n$ are even.

\solution{\bigskip{\bf Solution:} 
2 and 3 are true; the others are false.

1 is not true if either $m$ or $n$ is not equal to 2.  Thus is it not
true for ALL $m$ and $n$, though it is true for some.

2 is true.  The Hamiltonian path simply goes row by row and snakes back 
and forth.

3 is true.  We proved a less general version of this on the first exam;
the proof is analagous.

4 is false.  Grid graphs are 2-colorable; however, a Hamiltonian
circuit contains every node once.  Thus, since $mn$ is odd, the
Hamiltonian circuit is a circuit of odd length that is 2-colorable.
This is not possible, so there could be no Hamiltonian circuit.

5 is false.  Actually, the accurate statement is that if there is
a Hamiltonian circuit in $G$ then either $m$ or $n$ is even.  The 
2 by 3 grid graph gives a counterexample to 5.
}

\problempart {\bf (8 points)} Circle the numbers of ALL of the
following functions which are $\theta(n)$:

1.  $f(n) = 8000 \sqrt{n} + .00034 n$\\
2.  $g(n) = \frac{n^2 + 3n - 4}{-4n^2 + 9n + 9}$\\
3.  $h(n) = \log (n!/n)$\\
4.  $l(n) = n^{1 + \frac{1}{n}}$

\solution{\bigskip{\bf Solution:} 
1 and 4 are $\theta(n)$.

1: $f(n)$ is clearly $\theta(n)$ since the growth of $n$ outstrips
that of $\sqrt{n}$.

2: $g(n)$ is $O(n)$ but not $\Omega(n)$ since $\lim_{n \to \infty}
g(n) = -\frac14$.

3: $h(n)$ is $\Omega(n)$ but not $O(n)$.  By Stirling's approximation,
$\log(n!) = \theta(n \log n)$.  Thus, $h(n) = \theta (n \log n - n)$ which
is still $\theta(n \log n)$.

4: $l(n)$ is clearly greater than $n$, so it is $\Omega(n)$.  However, the
other direction is harder.  The question becomes whether there is a constant
$c$ such that for sufficiently large $n$,

$$n^{1 + \frac1n} < cn$$
$$n^{\frac1n} < c$$
$$\frac1n \log n < \log c$$

which is true for (say) $c = e$ since $\lim_{n \to \infty} \frac1n \log n = 0$.
Thus, $l(n) = O(n)$, so $l(n) = \theta(n)$.
}

\problempart {\bf (6 points)} Circle the numbers of ALL of the
following which are uncountably infinite sets:

1.  The set of all even natural numbers\\
2.  The set of all subsets of the even natural numbers\\
3.  The set of all real numbers with only even digits in their 
decimal representations

\solution{\bigskip{\bf Solution:} 
2 and 3 are uncountably infinite, but 1 is not.

1 is clearly countable.  $0, 2, 4, \ldots$ is the way to count it.

2 is uncountable by the standard diagonalization argument.  It is just
like $\mathcal{P}(\mathbb{N})$.

3 is uncountable.  The diagonalization argument for the uncountability
of the real numbers works even better here, since we don't run into the
$.9999\ldots = 1$ issue.
}

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{16} \textbf {Counting Connected Components of a Graph}

Consider the following algorithm, which counts the number of connected
components in a graph by ``contracting'' edges until there are no edges
left in the graph.

\begin{tabbing}
XXXX\=XXXX\=\kill
{\bf CompCount} (Undirected Graph $G$)\\
1.  $H := G$\\
2.  While $H$ contains at least one edge do:\\
\>1.  Pick an edge $(v, w)$ in $H$.\\
\>2.  Add a new vertex $z$ to $H$.\\
\>3.  For each vertex $p$ in the graph, add the edge $(p,z)$ to $H$\\
\>\>if and only if $(p,v)$ or $(p,w)$ is an edge in $H$.\\
\>4.  Remove vertices $v, w$ and all their incident edges from $H$.\\
3.  $n := $ the number of vertices in $H$.\\
4.  CompCount $(G) := n$
\end{tabbing}

\problempart {\bf (3 points)} If $H$ is the graph given below, and the
edge $(v,w)$ is the one selected in step 2.1, draw the graph $H$ after
step 2.4 in the algorithm.  Label the $z$ vertex in your graph.

\includegraphics[height=3in]{problem2a.eps}

\solution{\bigskip {\bf Solution:}
\includegraphics[height=3in]{problem2asol.eps}
}

\problempart {\bf (3 points)} Model this algorithm as a state machine.

\solution{\bigskip {\bf Solution:}

The states of the machine will be pairs $(G, H)$ where $G$ and $H$ are
graphs.  

The start state $q_0$ of the machine will be pairs $(G, G)$ where $G$
is some graph.

The transitions are of the form $(G, H) \mapsto (G, H'_{(v,w)})$.
They exist as long as $H$ has any edges, and for each edge $(v,w)$ in
$H$ there is a transition.

The graph $H'$ has all the same vertices as $H$, except that $v$ and
$w$ are replaced by a single vertex $z$.  The edges between vertices
not involving $v$ and $w$ are in $H'$, and for any other vertex $x$,
there is an edge between $x$ and $z$ in $H'$ if and only if there is
an edge between $x$ and $v$ or between $x$ and $w$ in $H$.
}

\nextproblem

\problempart {\bf (7 points)} Prove, using an invariant, that if the
algorithm terminates, the output is the number of connected components
of $G$.  You may assume that in a graph with no edges, the number of
connected components is equal to the number of vertices.

\solution{\bigskip {\bf Solution:}

Let our invariant $P(q)$ be, ``In state $q$, $H$ has the same number
of connected components as $G$.''

The invariant is clearly true in the start state, since $H$ and $G$ are
the same graph.

Suppose that $(G, H'_{(v,w)})$ is a state reachable from $(G, H)$.  
Since there is an edge from $v$ to $w$ they must be in a connected component.
Clearly, all other connected components still exist in $H'$ so there is no
problem.  We must prove that those vertices corresponding to the connected 
component including $v$ and $w$ form a connected component in $H'$.

Suppose $x$ is in the same connected component as $v$ and $w$ but $x$
is different from both $v$ and $w$.  Then there is a path from $x$ to
$v$ in $H$, so there is a path from $x$ to $z$ in $H'$.  (To make it,
simply reuse any edge not involving $v$ or $w$, or use the edge from
$y$ to $z$ instead of the edge from $y$ to $v$ or $y$ to $w$, and drop
the edge $(v,w)$ if it appears.)  

So, if $x$ is a vertex in the connected component with $v$ and $w$ in
$H$, then any vertex coming from $x$ (either $x$ itself if $x \neq v$
and $x \neq w$ or $z$ otherwise) is in the same connected component as $z$.

Furthermore, if $x$ is a vertex in another connected component from
$v$ and $w$ in $H$, then there is no path from $x$ to $z$.  If there
were, there must have been a path from $x$ to either $v$ or $w$ but
there was not.

Thus, the invariant is proven.  If the algorithm reaches a point where
there are no edges, the number of connected components is the number
of points.  Thus, if the algorithm terminates, it outputs the number
of connected components of $G$.
}

\largespace

\problempart {\bf (3 points)} Prove that this algorithm always terminates.

\solution{\bigskip {\bf Solution:}

Let $F(G, H)$ be the number of edges in $H$.  $F$ is clearly always a
nonnegative integer since graphs cannot have non-integer or negative
numbers of edges.  Furthermore, $F$ is strictly decreasing.  

When we make the transition from $H$ to $H'$ we remove the edge $(v,
w)$, and we may remove other edges too (if there are edges from some
node $x$ to both $v$ and $w$, these will be replaced with only one
edge from $x$ to $z$ in $H'$.)  

By the termination theorem, this algorithm terminates.
}

\nextproblem


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{9} \textbf {Lines That Cross and Lines That Don't}

Suppose we have a set $L$ of 26 different lines with equations in the
form $y = mx + b$ for real $m$ and $b$.  Prove that there is either

\begin{itemize}
\item[1.]  A set $S$ of 6 lines that never intersect one another when $x>0$, or
\item[2.]  A set $T$ of 6 lines such that any two of them intersect
one another at some point where $x>0$.
\end{itemize}

Hint:  Use Dilworth's Theorem.

\solution{\bigskip {\bf Solution:}

Let $\preceq$ be the relation on the set of 26 different lines such
that $mx + b \preceq m'x + b'$ if and only if at all points where $x >
0$, the height $mx + b$ is less than or equal to the height $m'x +
b'$.  (This relation is equivalent to the relation that $mx + b
\preceq m'x + b'$ if and only if $m \leq m'$ and $b \leq b'$, but we
won't prove this here.)

This is a partial order.  It is reflexive, since $mx + b \leq mx + b$
for every value of $x$.  If $mx + b \leq m'x + b'$ and $m'x + b' \leq
mx + b$ for all $x > 0$ then $mx + b = m'x + b$ so the two lines must
be the same (thus, the relation is antisymmetric).  Finally, the
relation is transitive since $\leq$ is transitive.

By Dilworth's theorem, there is either a chain in this poset of size
$>5$ or there is an antichain of size $\geq (26/5)$.

If there is a chain of size $6$ or greater, then the first six
elements of it form the set $S$.  If two lines are comparable they don't 
intersect when $x>0$.  If they did, at say $x = a$, then one of them is
higher at $x = 2a$ but the other is higher at $x = a/2$.  Thus, the 
chain forms the set $S$.

If there is an antichain of size $6$ or greater, then the first six
elements of it form the set $T$.  If two lines are not comparable,
there must be some point $x = a > 0$ such that $ma + b < m'a + b$ but
there must then be some point $x = a' > 0$ such that $ma' + b > m'a' +
b'$.  Thus, the function $(m'-m)x + (b'-b)$ has a value $(a)$ that
makes it greater than zero, and a value $(a')$ that makes it less than
zero.  Since this is a line, it must pass through zero at some point
$a''$ between $a$ and $a'$.  Since $a$ and $a'$ are both greater than
zero, $a''$ must also be greater than zero, so the two lines
intersect.
}

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 4
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{10} \textbf {Recurrence Relations}

\problempart {\bf (5 points)}
Find a closed form solution to the following homogenous recurrence
relation,

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

such that $A_0 = 1, A_1 = 0,$ and $A_2 = 3$.

\solution{\bigskip{\bf Solution:}

The characteristic equation for this recurrence is 

$$r^3 + r^2 - r - 1 = 0$$

which factors to

$$(r+1)(r^2 - 1) = (r+1)^2(r-1) = 0.$$

So we get a closed form solution of the form

$$A_n = c_1 + c_2(-1)^n + c_3 n(-1)^n.$$

Using the initial conditions, we find that

$c_1 + c_2 = 1,$ so $c_2 = 1 - c_1$.

$c_1 - (1-c_1) - c_3 = 0$, so $c_3 = 2c_1 - 1$, and

$$c_1 + (1-c_1) + 2(2c_1 - 1) = 3$$

$$4c_1 + 1 - 2 = 3$$

$$4c_1 = 4$$

so $c_1 = 1$, $c_2 = 0$, and $c_3 = 1$.  Thus, the final answer is

$$A_n = 1 + n(-1)^n.$$
}

\mediumspace

\problempart {\bf (5 points)} Find a closed form solution to the
following inhomogenous recurrence relation:

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

where $A_0 = 1, A_1 = 0$, and $A_2 = 3$.

\solution{\bigskip{\bf Solution:}
We can use the general form for the homogenous part from part (a):

$$ A_n = c_1 + c_2(-1)^n + nc_3(-1)^n. $$

Now, let us guess a particular solution in the form $an+b$.

$$ an+b = a(n-3) + b + a(n-2) + b - a(n-1) - b + 4 $$
$$ an+b = an - 4a + b + 4 $$
$$ 0 = -4a + 4$$
$$ 4a = 4$$

So $a = 1$ and $b$ can be anything, so we will choose 0.  Now,
substituting the initial conditions, we get that

$c_1 + c_2 = 1$ so $c_2 = 1 - c_1$.

$c_1 - c_2 - c_3 + 1 = 0$, so $c_3 = 2c_1$, and

$c_1 + c_2 + 2c_3 + 2 = 3$, so

$c_1 + (1-c_1) + 4c_1 + 2 = 3$

$4c_1 + 3 = 3$, so $c_1 = 0$.  Thus, the solution is

$$A_n = (-1)^n + n$$.  }

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 5
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{6} \textbf {Summations}

\problempart {\bf (2 points)}  Find a simplified closed form for

$$\sum_{i=0}^{\infty} \sum_{j=1}^n \frac{1}{2^i}$$

\solution{\bigskip {\bf Solution:}

The inner sum, 

$$ \sum_{j=1}^n \frac{1}{2^i} $$

is very simple since $j$ is not involved in the inner term.  The
closed form for this is simply

$$ \frac{n}{2^i} $$.

Since $n$ is a constant, we can take it out, and evaluate a simple
infinite geometric sum to get $\sum_{i=0}^{\infty} \sum_{j = 1}^n
\frac{1}{2^i} = 2n$
}

\mediumspace

\problempart {\bf (4 points)}  Find a simplified closed form for

$$\sum_{i=0}^n (i+1)x^i.$$

\solution{\bigskip {\bf Solution:}

Consider that 

$$\frac{d}{dx}\left( \sum_{i=0}^{n+1} x^i \right) = \sum_{i=0}^n (i+1)x^i.$$

However, the sum $\sum_{i=0}^{n+1} x^i$ can be written in closed form as

$$\frac{x^{n+2} - 1}{x - 1}.$$

Taking the derivative of this yields

$$\frac{(n+2)x^{n+1}}{x-1} - \frac{x^{n+2} - 1}{(x-1)^2} = $$

$$\frac{(n+1)x^{n+2} - (n+2)x^{n+1} + 1}{(x-1)^2}.$$
}

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 6
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{10} \textbf {Combinatorics}
Let $S$ be the set $\{a, b, c, d, e\}$ and let $T$ be the set $\{1,
2, 3, 4\}$. {\bf (2 points each)}

\problempart What is the number of binary relations from $S$ to $T$?

\solution{\bigskip{\bf Solution:} 
The set of all binary relations is
$\mathcal{P}(S \times T)$.  Since $|S \times T| = 20$, the number of
binary relations between $S$ and $T$ is $2^{20}$.
}

\smallspace

\problempart What is the number of functions from $T$ to $S$?

\solution{\bigskip{\bf Solution:} To make a function from $T$ to $S$,
we must assign an element of $S$ to each element of $T$.  Thus, for
each of the 4 elements in $T$ we must make one of 5 choices.  Therefore
the number of functions from $T$ to $S$ is $5^4$.}

\smallspace

\problempart What is the number of injective functions from $T$ to $S$?

\solution{\bigskip{\bf Solution:} We must choose a permutation of 4
out of 5 elements.  Thus, $5!$ is the number of injective functions.
(We must make a choice of which of the 5 elements of $S$ is mapped to
from the first element of $T$, then a choice of which of the remaining
4 elements of $S$ is mapped to from the second element of $T$, et
cetera.}

\smallspace

\problempart What is the number of surjective functions from $T$ to $S$?

\solution{\bigskip{\bf Solution:} 
0.  $T$ is smaller than $S$ so there cannot be a surjection from $T$ to $S$.
}

\smallspace

\problempart What is the number of surjective functions from $S$ to $T$?

\solution{\bigskip{\bf Solution:} To form a surjective function, we
first take an injective function from $T$ to $S$ (this takes care of
the surjective requirement), and then choose which element of $T$ is
the image of the remaining element of $S$ which hasn't been paired up
yet.  There are $5! \cdot 4$ ways of doing this.

However, we have double-counted everything.  For example, if the
function is $(1, 2, 3, 4, 1)$, we have counted this by choosing the
injection $(a, b, c, d)$ and then the element 1, AND by choosing the
injection $(e, b, c, d)$ and then the element 1.  So, we must divide 
by 2 to take care of this; this leaves $2 \cdot 5!$ as the final answer.}

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 7
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{16} \textbf {Coloring Grid Graphs, Yet Again}

Let $G$ be a 4 by 4 grid graph: 

\begin{center}\includegraphics[height=2.75in]{problem7.eps}\end{center}


Suppose we pick a random 4 color graph coloring of $G$, where the
colors being used are red, green, blue, and yellow.  That is, we pick
uniformly at random from the set of all valid colorings.  Let $A$ be
the event that vertex (1,1) is colored red, $B$ be the event that
vertex (1,2) is colored red, and $C$ be the event that (1,1) and (2,2)
are the same color.  Let $X$ be the number of ``points'' the graph
coloring gives, where each red node is worth 1 point, each yellow node
is worth 2 points, each blue node is worth 3 points, and each green
node is worth 6 points.

\problempart {\bf (2 points)} What is Pr$(A)$?

\solution{\bigskip {\bf Solution:}

By symmetry, vertex (1,1) should be no more likely to be any one
particular color than any other.  Thus, the probability is $1/4$.
}

\problempart {\bf (2 points)} What is Pr$(B|\overline{A})$?

\solution{\bigskip {\bf Solution:}

By symmetry, vertex (1,2) should be no more likely to be any one
particular valid color (given that vertex (1,1) is colored red) than
any other.  Thus, the probability is $1/3$.
}
\problempart {\bf (2 points)} What is Pr$(A|C)$?

\solution{\bigskip {\bf Solution:}

By symmetry, if vertices (1,1) and (2,2) are the same color, they
should not be more likely to be any one color than any other.  Thus,
the probability is $1/4$.
}

\problempart {\bf (2 points)} What is Pr$(B|\overline{A} \cap C)$?

\solution{\bigskip {\bf Solution:}

By symmetry, if vertices (1,1) and (2,2) are both not red (which is what
having $\overline{A}$ and $C$ both be true means), then vertex (1,2) should be 
no more likely to be any one valid color than any other.  No matter which
color vertices (1,1) and (2,2) are, red is one of three valid colors for
vertex (1,2), so the probability is $1/3$.
}

\problempart {\bf (4 points)}  Which pairs of the events $A, B,$ and $C$ are 
independent?  

\solution{\bigskip {\bf Solution:} 

Obviously, since $A$ and $B$ cannot both be true at the same time,
they are not independent.

However, $Pr(A|C) = Pr(A)$ so $A$ and $C$ are independent.

$Pr(B|C) = 1/4$ since if vertices (1,1) and (2,2) are the same color,
they should be equally likely to be any particular color.  With
probability 3/4, they are not red, and then with probability 1/3,
vertex (1,2) is red.  With probability 1/4, (1,1) and (2,2) are red,
and then with probability 0, vertex (1,2) is red.  Thus, $Pr(B|C) =
(3/4)(1/3) + (1/4)0 = 1/4 = Pr(B)$.  Thus, $B$ and $C$ are independent.
}

\problempart {\bf (4 points)} What is Ex$(X)$?

\solution{ \bigskip {\bf Solution:}
Let $X_v$ be a random variable for vertex $v$, which determines the
number of points that vertex contributes.  Since $X = \sum_{v \in G} X_v$,
by linearity of expectation, we have that

Ex$(X) = \sum_{v \in G} $Ex$(X_v)$.  

Since Ex$(X_v) = (1)(1/4) + (2)(1/4) + (3)(1/4) + (6)(1/4) = 12(1/4) = 3$,
and there are sixteen vertices in $G$, this gives that 

Ex$(X) = 48$.
}

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 8
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{20} \textbf {The Florida Election}

Suppose that in one Florida county populated exclusively with
probability theory enthusiasts, there are 10,000 people.  Every one of
them votes independently of one another, and they vote for Bush with
probability $2/5$ and for Gore with probability $3/5$.

\problempart {\bf (2 points)} Let $X$ be a random variable that
represents the number of votes Gore gets in this county.  What is the
expected value of $X$?

\solution{\bigskip {\bf Solution:}

6000.}

\problempart {\bf (3 points)} What is the variance of $X$?

\solution{\bigskip {\bf Solution:}

$V(X) = 10000(2/5)(3/5) = 2400$.
}

\smallspace

\problempart {\bf (5 points)} Using the Markov inequality, give an
upper bound for the probability that Gore gets at least 2600 more votes than
Bush.

\solution{\bigskip {\bf Solution:}

If Gore gets at least 2600 more votes than Bush in the county, then
$X$ must be at least 6300 (since $6300 - 3700 = 2600)$.  By Markov's
inequality,

$$Pr(X \geq 6300) \leq \frac{6000}{6300} = \frac{20}{21}$$
}

\smallspace

\problempart {\bf (5 points)} Using the Chebyshev inequality, give an
upper bound for the probability that Gore gets at least 2600
more votes than Bush.  

\solution{\bigskip {\bf Solution:}

Using the one-sided Chebyshev formula, 

$$Pr(X - Ex(X) \geq t) \leq \frac{V(X)}{V(X) + t^2}$$

with $t = 300$ gives an upper bound of $\frac{2400}{92400} = \frac{2}{77}.$

However, the two-sided Chebyshev inequality is almost as good.

$$Pr(X - Ex(X) \geq t) \leq Pr(|X - Ex(X)| \geq t) \leq \frac{V(X)}{t^2},$$

with $t = 300$ gives an upper bound of $\frac{2400}{90000} = \frac{2}{75}.$
}

\smallspace

\problempart {\bf (5 points)} Using the Chernoff inequality, give a
simplified upper bound for the probability that Gore gets at least 2600 more
votes than Bush, or explain why the Chernoff bound does not apply.  

\solution{\bigskip {\bf Solution:}

Since the 6300 votes Gore would need for this to happen is equal to
$21/20$ times 6000, the expected number of votes Gore gets, the
Chernoff inequality yields

$$Pr(X \geq (21/20)Ex(X)) \leq e^{-\alpha c Ex(X)}.$$

Plugging in $\alpha = \ln c + 1/c - 1$ and evaluating gives that

$e^{-\alpha c Ex(X)} \approx e^{-7.37} \approx 0.000625$.
}

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 9
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{6} \textbf {MIT Football}

MIT's football coach goes to K-mart to buy 32 football jerseys.  While
he is away, instead of practicing, the team proves theorems about the
numbers on the jerseys.

For each of the theorems, fill in whichever blanks are asked for.  You
do not have to complete the proof.  For example, 

{\bf Theorem 1}\\
If the numbers on the jerseys are integers in the set $\{1, \ldots, 31\}$ then
two of the jerseys have the same number.

Pigeons: \underline{Jerseys}

Pigeonholes:  \underline{Integers in the set $\{1, \ldots, 31\}$}

Pigeon $p$ is in hole $h$ if:  \underline{Jersey $p$ has number $h$ on it.}

\problempart {\bf (2 points).  Theorem 2}\\ If the numbers on the
jerseys are integers in the set $\{1, \ldots, 100\}$ then the
difference between the numbers on some pair of jerseys is a multiple
of 31.

Pigeons: Jerseys

Pigeonholes:  \underline{\hspace{3in}}

Pigeon $p$ is in hole $h$ if:  \underline{\hspace{3in}}

\solution{\bigskip {\bf Solution:}

Pigeonholes:  Integers in the set $\{0, \ldots, 30\}$.

Pigeon $p$ is in hole $h$ if: The number on jersey $p$ is equal to $h$
modulo 31.
}


\problempart {\bf (4 points).  Theorem 3}\\ If the numbers on the
jerseys are integers in the set $\{1, \ldots, 100\}$ then if the
jerseys are lined up in ascending order by their numbers, there is a
nonempty consecutive subset of the jerseys whose numbers add up to a
multiple of 32.

Pigeons: \underline{\hspace{3in}}

Pigeonholes:  \underline{\hspace{3in}}

Pigeon $p$ is in hole $h$ if:  \underline{\hspace{3in}}

\solution{\bigskip {\bf Solution:}

Pigeons:  Sums of the first $i$ jerseys, from $i = 1$ to $32$

Pigeonholes:  Integers in the set $\{0, \ldots, 31\}$

Pigeon $p$ is in hole $h$ if:  $p \equiv h$ mod $32$.}


\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 10
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{6} \textbf {Die Rolling}

Say you roll a fair 6-sided die.  If you get a 6, you may roll again,
and add 6 to the outcome; if you roll multiple 6's in a row, you
continue to roll again.  So, for example, if you roll a 6 and then a
5, the outcome is 11; if you roll a 6, then a 6, then a 6, then a 2,
the outcome is 20.

What is the expected value of the outcome?  Your answer should be in
closed form.

\solution{\bigskip {\bf Solution:}

Let $R_i$ be the value of the $i$th die roll (if there is one).  Let
$Q$ be the number of die rolls.  Since Ex$(R_i)$ does not depend on $i$,
we can use Wald's theorem to find the solution.

Ex$(R_i) = \frac{1}{6} (1 + 2 + 3 + 4 + 5 + 6) = \frac{21}{6} = \frac{7}{2}$.

Ex$(Q) = \sum_{i=0}^{\infty} \frac{1}{6^i} = \frac{1}{1 - (1/6)} =
\frac{6}{5}$.

So, Ex($\sum_{i=1}^Q R_i) = $Ex($R_i$)Ex($Q$) = $\frac{42}{10} =
\frac{21}{5}$.

Another way of doing this problem would be to note that 

$Ex(X) = \frac{1}{6}(1 + 2 + 3 + 4 + 5 + (6 + Ex(X))) = \frac{7}{2} + Ex(X)/6$.

Solving gives

$\frac{5 Ex(X)}{6} = \frac{7}{2}$

so 

$Ex(X) = \frac{42}{10} = \frac{21}{5}$
}


\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 11
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{10} \textbf {Chess Matches}

Math Moose and Theory Pig have been playing a series of chess games,
and have noticed a number of facts:

\begin{itemize}
\item  Math Moose plays white in any given game with probability 8/17.

\item If Math Moose plays white, he is equally likely to win or lose.

\item If Math Moose plays black, then with probability 8/9, he loses.

\item If Math Moose wins, he always takes Theory Pig's queen at
some point in the game.

\item If Math Moose plays white and loses, he takes Theory Pig's queen
with probability 1/2.

\item If Math Moose plays black and loses, he takes Theory Pig's queen
with probability 1/4.
\end{itemize}

\problempart {\bf (4 points)} Define the sample space, and give the
probability associated with each outcome.

\solution{\bigskip {\bf Solution:}
The outcomes are that Math Moose...:

plays white, wins, and takes the queen: 4/17\\
plays white, loses, and takes the queen: 2/17\\
plays white, loses, and doesn't take the queen: 2/17\\
plays black, wins, and takes the queen: 1/17\\
plays black, loses, and takes the queen: 2/17\\
plays black, loses, and doesn't take the queen: 6/17\\
plays white, wins, and doesn't take the queen: 0\\
plays black, wins, and doesn't take the queen: 0\\
}
\smallspace
\smallspace


\problempart {\bf (3 points)} What is the probability that Math Moose
plays white, given that he wins?

\solution{\bigskip {\bf Solution:}
The probability is $\frac{4/17}{5/17} = \frac{4}{5}$.}
\smallspace


\problempart {\bf (3 points)} What is the probability that Math Moose
wins, given that he takes Theory Pig's queen?

\solution{\bigskip {\bf Solution:}
The probability is $\frac{5/17}{9/17} = \frac{5}{9}$.}

\nextproblem

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 12
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{8} \textbf {Overloading Circuits}

A memory card produced by NP Computer Hardware, Inc., consists of
infinitely many memory cells in series.  The card is attached to a
computer at one end.  If there is a power surge, the first memory cell
burns out.  Furthermore, if a memory cell burns out, the next memory
cell after that one burns out with probability $p$.  Otherwise, memory
cells have no chance of burning out in a power surge.

\problempart {\bf (5 points)} Express the expected number of memory
cells that burn out in a power surge, in terms of $p$.  (Hint: use
linearity of expectation.)

\solution{\bigskip {\bf Solution:}

Let $X_i$ be an indicator variable which is 1 if during a power surge,
memory cell $i$ burns out, and is a 0 otherwise.

We are asked to find Ex$(\sum_{i=0}^{\infty} X_i) =
\sum_{i=0}^{\infty}$ Ex($X_i$).

The probability that $X_i$ is 1 is equal to $p$ times the probability
that $X_{i-1}$ is 1.  This gives the simple recurrence relation $X_n =
pX_{n-1}$ with initial condition $X_0 = 1$, which simplifies to $X_n =
p^n$.  Thus, the value we want is $\sum_{i=0}^{\infty} p^n =
\frac{1}{1-p}$, provided that $p < 1$.  If $p=1$ all the memory cells
burn out.}

\mediumspace

\problempart {\bf (3 points)} It is discovered
that the mean number of memory cells that burn out from a power surge is
10.  What is $p$?

\solution{\bigskip {\bf Solution:}

If $10 = \frac{1}{1-p}$ then $10 - 10p = 1$ so $10p = 9$ so $p = 9/10$.
}


\end{problems}
\end{document}
