\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{psfig}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{array}
\input{../handouts/macros-course}
%\input{macros-course}

\newif\ifspaceout
\spaceouttrue
\newcommand{\smallspace}{\ifspaceout\vspace{1in}\fi}
\newcommand{\mediumspace}{\ifspaceout\vspace{3in}\fi}
\newcommand{\largespace}{\ifspaceout\vspace{4in}\fi}
%\newcommand{\nextproblem}{\ifspaceout\newpage\fi}
\newcommand{\nextproblem}{\newpage}

\def\mychoose{\binom}
\newcommand{\nosolutions}[1]{\ifspaceout{#1}\fi}
\newcommand{\ignore}[1]{}

\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{::=}}}
\renewcommand{\th}{\ensuremath{^{th}}}
\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
    }
    
    
\newcolumntype{C}{>{$}c<{$}}
\newcolumntype{L}{>{$}l<{$}}
\newcolumntype{R}{>{$}r<{$}}    

  
\newcolumntype{S}{>{\[}c<{\]}}
\newcolumntype{T}{>{\[}l<{\]}}
\newcolumntype{U}{>{\[}r<{\]}}  
    

\makeatother

\askaboutsolutions

\begin{document}


\ifshowsolutions
\exam{~Final Exam Solutions}{May 24, 2001}
\spaceoutfalse
\else
\exam{~Final Exam}{May 24, 2001}
\fi

%\titlebar

\textbf{Your Name}:\ \mbox{}\hrulefill\mbox{}\par

\textbf{Circle the name of your Tutorial Instructor}:\\
\begin{center}
\begin{tabular}{c@{\hskip 3em}c@{\hskip 3em}c@{\hskip 3em}c}
George & Joe & Josh & Kavita \\
\ &&& \\
Ivan & Ray & Tina &
\end{tabular}
\end{center}

\medskip

\noindent Write the hour at which your Friday tutorial used to begin \brule{3em}

\medskip

\begin{closeitemize}
\item This exam is open book/notes.  

\item There are 17 pages with 14 problems totaling 150 points.  Problem 
  parts are labeled with their point values.

\item Put your name on the top of {\bf every} page --- \emph{these
    pages may be separated for grading}.

\item Write your solutions in the space provided.  If you need more
  space, write on the back of the sheet containing the problem.
  Please keep your entire answer to a problem on that problem's page.

\item You may assume any of the results presented in class or in the
  lecture notes.

\item Show your work, as partial credit will be given.  You will be
  graded not only on the correctness of your answer, but also on the
  clarity with which you express it.  {\bf Be neat and write legibly}.

\item GOOD LUCK!
\end{closeitemize}

\bigskip

\medskip

\hrule
\smallskip
\centerline{\textbf{DO NOT WRITE BELOW THIS LINE}}
\smallskip
\hrule

\medskip

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c||c|c|c|c|}
\hline
& &\hspace*{1in}& & &\hspace*{1in}& &\\
Problem & Points & Grade & Grader &
Problem & Points & Grade & Grader\\
& & & & & & & \\ \hline \hline & & & & & & & \\
1 & 10 & & &  8 & 15 & & \\
& & & & & & & \\ \hline & & & & & & & \\
2 & 10 & & &  9 &  5 & & \\
& & & & & & & \\ \hline & & & & & & & \\
3 & 20 & & & 10 & 10 & & \\
& & & & & & & \\ \hline & & & & & & & \\
4 & 10 & & & 11 & 10 & & \\
& & & & & & & \\ \hline & & & & & & & \\
5 & 10 & & & 12 & 15 & & \\
& & & & & & & \\ \hline & & & & & & & \\
6 & 10 & & & 13 & 10 & & \\
& & & & & & & \\ \hline & & & & & & & \\
7 & 10 & & & 14 & 10 & & \\
& & & & & & & \\ \hline\hline & & & & & & & \\
Subtotal & 80 & & & 70 & & &\\ 
& & & & & & & \\ \hline & & & & & & & \\
Total & & & & 150 & & &\\ 
& & & & & & & \\ \hline \\

\end{tabular}
\end{center}


\newpage

\begin{problems}


\problem\pts{10}\textbf{Quantifiers and Logic}
%from Rosen, Instructor's resource guide, page 329, exercise 31

Suppose the variable $x$ represents students, $F(x)$ means ``$x$ is a freshman", and $M(x)$ means ``$x$ is a math major". Match \emph{each} statement in the table below with one of the English sentences in this list:

\renewcommand{\labelenumi}{(\arabic{enumi})}
\begin{enumerate}
\item Some freshmen are math majors
\item Every math major is a freshman
\item No math major is a freshman


\end{enumerate}
The first entry in the table has been filled in as an example
\nosolutions{

\renewcommand{\arraystretch}{2} 
\begin{tabular}{|c|C|c|}
\hline
    & \text{Expression}& Corresponding Sentence \\\hline
 1 & \forall x [M(x)\implies \neg F(x)] &3\\ \hline
 2 & \neg \exists x [M(x) \And \neg F(x)] &\\ \hline
 3 & \forall x [F(x)\implies \neg M(x)]& \\ \hline
 4 & \forall x [M(x)\implies F(x)]& \\ \hline
 5 & \exists x [F(x)\And M(x)] &\\ \hline
 6 & \neg \forall x [\neg F(x)\Or \neg M(x)]& \\ \hline
% 7 & \forall x [\neg (M(x)\And \neg F(x))]& \\ \hline
% 8 & \forall x [\neg M(x) \Or \neg F(x)]& \\ \hline
% 9 & \neg \exists x [M(x)\And \neg F(x)]& \\ \hline
% 10 & \neg \exists x [M(x)\And F(x)] &\\ \hline
% 11 & \neg \forall x[F(x)\implies \neg M(x)]& \\ \hline
\end{tabular}
}
\solution{
\ssl

\renewcommand{\arraystretch}{2} 
\begin{tabular}{|c|C|c|}
\hline
    & \text{Expression}& Corresponding Sentence \\\hline
 1 & \forall x [M(x)\implies \neg F(x)] &3\\ \hline
 2 & \neg \exists x [M(x) \And \neg F(x)] &2\\ \hline
 3 & \forall x [F(x)\implies \neg M(x)]& 3\\ \hline
 4 & \forall x [M(x)\implies F(x)]& 2\\ \hline
 5 & \exists x [F(x)\And M(x)] &1\\ \hline
 6 & \neg \forall x [\neg F(x)\Or \neg M(x)]&1 \\ \hline
% 7 & \forall x [\neg (M(x)\And \neg F(x))]& 2\\ \hline
% 8 & \forall x [\neg M(x) \Or \neg F(x)]&3 \\ \hline
% 9 & \neg \exists x [M(x)\And \neg F(x)]& 2\\ \hline
% 10 & \neg \exists x [M(x)\And F(x)] &3\\ \hline
% 11 & \neg \forall x[F(x)\implies \neg M(x)]& 1\\ \hline
\end{tabular}

}



\nextproblem

\problem \pts{10}\textbf{Ordering}

\renewcommand{\arraystretch}{1} 
After graduating from MIT, you are hired by a startup company that
specializes in organizing frog races.  Your first assignment is to
plan the finals for a race near Johnstown, Pa.  The competition is run
in two stages.  First, some preliminary races are run between small
groups of the frogs.  Then, the results of those races are used to
determine the frogs' starting positions for the final, deciding race.
All the preliminary races have been run with the following results:


\begin{center}
\begin{tabular}{l|c|c|c|c}
  & Race 1 & Race 2 & Race 3 & Race 4 \\ 
\hline
  1st & Lars & Ivan & David & Ray \\
  2nd & Ray & Josh & Lars & George \\
  3rd & Kavita & Tina & Ivan & Tina \\
  4th & Be & Be & Joe & Joe
\end{tabular}

\end{center}



You must line up the 10 frogs for the final race so that no frog is
after a frog it has beaten in one of the preliminary rounds.  Give one
possible ordering.

\solution{\medskip
\textbf{Solution:}

Two possible orderings are:

David, Lars, Ivan, Josh, Ray, George, Tina, Joe, Kavita, Be

and

David, Lars, Ray, Kavita, George, Ivan, Josh, Tina, Be, Joe
\newpage
}

\nextproblem
\problem\pts{20} \textbf{Recurrences}
%from http://www.maths.lse.ac.uk/Courses/MA311/#hw
%Exercises 3

On working through a problem, a student is said to be at the $n\th$
stage if he or she is $n$ steps from the final solution. At any stage
the student has five choices. Two of these result in the student going
to the $(n - 1)\th$ stage, and three of them are better in that they
take him or her directly to the $(n-2)\th$ stage.  Let $f(n)$ be the
number of ways the student can reach the final solution if he or she
starts from the $n\th$ stage. This means that $f(0) = 1$, since in
stage 0 the student has reached the final solution. We also have that
$f(1) = 2$, since the student can only take the two steps that take
her or him to the final solution in stage 0.
\begin{problemparts}
\ppart\pts{2} Verify that $f(2) = 7$ (that is, argue why this must be so).
\solution{\ssl
At the $2^{nd}$ stage, the student has {\bf 3} ways to get straight to the final answer. He also has 2 different ways to get to stage 1, from which he has 2 different ways to get to the final answer (for a total of {\bf 4}). $3+4=7$}
\smallspace

\ppart\pts{3} Give a recurrence relation for $f(n)$.

\solution{\ssl
\[
f(n)=2f(n-1)+3f(n-2)
\]}

\smallspace

\ppart\pts{5} Solve the recurrence.

\largespace


\solution{\ssl
\[
f(n)=\frac{1}{4}\left(3^{n+1}+(-1)^n\right)
\]
}


\ppart\pts{5} Prove by induction that your answer in part~(c) is correct.

\largespace

\solution{\ssl
Since the recurrence involves 2 previous terms, we need strong induction.
\paragraph{Base Cases} Plug in 0, 1. We get $f(0)=1$, $f(1)=2$, as expected.
\paragraph{Inductive step} Assume that $\forall~n~~1\leq n \leq K$ the following relations hold

\[
\begin{array}{l}
f(n)=\frac{1}{4}\left(3^{n+1}+(-1)^n\right)\\
f(n-1)=\frac{1}{4}\left(3^{n}+(-1)^{n-1}\right)\\
\end{array}
\] 

Plugging into 
\[
f(n+1)=2f(n)+3f(n-1)
\]
we get
\[
f(n+1)=\frac{1}{4}\left(3^{n+2}+(-1)^{n+1}\right)
\] 
}

\ppart\pts{5} We now consider a student who chooses one of the 5
possible choices uniformly at random in each stage.  What is the
probability that the student will take the worst case number of steps,
namely $n$, to reach the solution?
\solution{\ssl
If $n=1$ then the student has to take 1 step no matter what, so the probability is 1. If $n\geq 2$ then at each step the student chooses one of the less efficient steps with probability $\frac25$, until he gets down to step 1, from which he will have no choice. So the probability will be $(\frac25)^{n-1}$
\newpage
}
\ignore{

\smallspace

\ppart\pts{5} Given $m \le n$, give a closed form expression for the
probability that the student will reach the final solution after
exactly $m$ choices?  (Hint: how many good and bad choices must there
be in the sequence of choices?)

}

\end{problemparts}



\nextproblem
\problem\pts{10} \textbf{Counting}
%From Rosen, Instructor's resource guide, page 357, exercise 38
\ppart\pts{5}
%From Rosen, Instructor's resource guide, page 356, exercise 32
A professor teaching 6.042 gives a multiple choice quiz that has 10
questions, each of which has 4 possible answers (a,b,c,d). What is the
\emph{minimum} number of students that must be in the professor's
class in order to guarantee that at least three answer sheets must be
identical? (assume that no answers are left blank).  Justify your
answer.

\solution{\ssl
There are $4^{10}$ possible answers. By the strong pigeonhole principle, in order to have the desired property, we need at least $2\cdot 4^{10}+1$ students.
}

\mediumspace

\ppart\pts{5}Let $s_1, s_2,\ldots, s_{101}$ be 101 strings of
1's and 0's that are at most 9 digits long. Prove that there exist 2
strings, $s_i$ and $s_j$, with $i\neq j$, that contain the same number
of 0's and the same number of 1's. (For example, strings 110001001 and
101000110 contain the same number of 0's and the same number of 1's)
[Note: You actually need much fewer than 101 strings to prove the
above---you can give a proof using a lower number of strings if you
would like to (for equal credit).]

\solution{\ssl We can associate a pair $(a,b)$ with each string, where
  $a$ is the number of 0's and $b$ is the number of 1's. There are
  \emph{at most} 100 such pairs (actually, the constraint about the
  length of the string implies that there are fewer than 100). We can
  consider the pairs to be the holes and the strings to be the
  pigeons. Since there are more pigeons than holes, one hole must have
  at least 2 pigeons. Two strings that are associated with the same
  pair will have the same number of 0's and the same number of 1's.
  
  If we take the constraint about the length into account, then we see that there can be only 55 $(a,b)$ pairs: for each possible length $i\in[0\ldots 9]$ there are $i+1$ possibilities for the number of $0$'s (or 1's, of course). Thus, the total number of \emph{legal} pairs $(a,b)$ is 
\[
\sum_{i=0}^{9}{i+1}=55
\]
Since there are (much) more pigeons than holes, one hole will have at least 2 pigeons.

}

\nextproblem
\problem\pts{10} \textbf{Graphs}

A \emph{complete} graph is a special kind of graph in which every pair of vertices is connected by an edge. Figure \ref{complete} depicts a complete graph on 5 vertices.
\begin{figure}[h]
\begin{center}
\includegraphics[height=5 cm,keepaspectratio=true]{K5}
\caption{A complete graph on 5 vertices}
\label{complete}
\end{center}
\end{figure}
 
Suppose you have a set of $n$ different (labeled) vertices.

\ppart\pts{2}
How many \emph{complete} graphs are there on $n$ vertices?

\solution{\ssl
One.
}

\ignore{%
  
\ppart How many simple paths are there in a complete graph?
\hint How many simple paths of length~$i$ are there?

\solution{\ssl Recall that a path is a sequence of vertices (from one
  to $n$ vertices) with no cycles.  Since order matters, for each path
  length $i$ ($1 \leq i \leq n$), we choose an $i$-permutation of the
  $n$ vertices, which can be done $n! \over (n-i)!$.  Summing over all
  path lengths gives
  \[\sum_{i=1}^{n} {n! \over (n-i)!}\]
  }

}

\ppart\pts{3} How many graphs (not necessarily complete) are there
on $n$~vertices?  

\solution{\ssl $2^{\binom{n}{2}}$ (for each possible edge, we choose
  whether it's in the graph or not).}

\smallspace

\ppart\pts{5} How many simple cycles are there in a complete graph?
(Recall that a simple cycle is a simple path containing at least three
edges that starts and ends at the same vertex.  Consider cycles with
the same edges to be equivalent, even if their starting vertices are
different.)  Your answer need not be in closed form; it can involve
summations.

\solution{\ssl%
  Let's count cycles of length $i$, then sum for $i = 3, 4, \ldots,
  n$.  (Usually we don't consider a cycle to be simple unless it
  contains at least three vertices, and no vertex appears more than
  once.)  To count the number of cycles with exactly $i$ vertices,
  there are $\binom{n}{i}$ choices for the $i$~vertices in the cycle,
  $i!$~ways of ordering $i$~vertices, but each cycle is actually being
  overcounted by a factor of~$i$ (since any vertex could be the start
  vertex), and a factor of~$2$ because a cycle is counted once for
  each possible direction of traversal. (It would also be reasonable
  not to divide by 2, since it makes sense to specify a direction for
  a cycle, e.g., if the graph is directed.)  Summing over all possible
  values of~$i$ gives the answer:
  \begin{displaymath}
    \frac{1}{2} \sum_{i=3}^{n} \binom{n}{i} (i-1)!
  \end{displaymath}
}

\nextproblem

\problem\pts{10} \textbf{More Counting}
% From http://www.maths.lse.ac.uk/Courses/MA311/#exams
% Final Exam, 2000

A drawer contains six distinguishable pairs of gloves. Six persons,
named A, B, C, D, E, and F, take a left-hand glove and a right-hand
glove (without replacement, so all gloves are gone at the end ).

\ppart\pts{2} In how many ways can this selection be done ?

\solution{\ssl $(6!)^2$.}

\smallspace

\ppart\pts{2} In how many ways can this be done such that B has
a non-matching pair and D has a matching pair ?

\solution{\ssl $(6!)(4\cdot4!)$.}

\smallspace

\ppart\pts{3} In how many ways can this be done if exactly four
people have a matching pair ?

\solution{\ssl $\binom{6}{4}(6!)$.}

\smallspace

\ppart\pts{3} In how many ways can this be done such that A
and~B have matching pairs but none of C, D, E, and F have matching
pairs?  \hint For a \emph{particular} choice of left-hand gloves,
consider denoting the set of events in which C gets a matching
right-hand glove by~$M_C$ (and likewise for all the others).

\solution{\ssl There are $6!$ ways to choose the left-hand gloves.
  Since A and B have matching pairs, we know what they get (no freedom
  there). Now, the remaining 4 must get non-matching pairs. The number
  of choices is equal to the number of derangements of 4 objects (see
  also problem 8d on the practice final), which, by the
  inclusion-exclusion formula, is equal to
  \[
  4![1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}]=9
  \]
  therefore, the total number of ways is $6!\cdot 9 = 6480$
\newpage
}

\ignore{
  \begin{displaymath}
    6!\biggl(
      4!-\binom{4}{1}3!+\binom{4}{2}2!-\binom{4}{3}1!+\binom{4}{4}0!
    \biggr)
    =
    720\cdot15
    =
    10800.
  \end{displaymath}}

\nextproblem
\problem\pts{10} \textbf{Binomial Coefficients}

\ignore{
\ppart\pts{2}
Give a closed-form formula for $\sum_{i=0}^{n} {n \choose i}$. Justify your answer

\solution{\ssl
\[\sum_{i=0}^{n} {n \choose i} = 2^n \]
}
\ppart\pts{3}What is
$${{n\choose 0}} - {{n\choose 1}} + {{n \choose 2}} - {{n \choose 3}} \ldots$$
Justify your answer
\solution{\ssl
Recall that 
$$(a+b)^n = \sum_{i=0}^n {{n \choose i}} a^i b^{n-i}$$

Now let $a=-1$ and $b=1$. Clearly $(a+b)^n=0$ for all $n>0$, so
$$0 = \sum_{i=0}^n {{n \choose i}} (-1)^i$$

Since ${n \choose i} = 0$ for all $i > n$, we can let the sum go to
infinity:
$$0 = \sum_{i=0}^\infty {{n \choose i}} (-1)^i$$

Finally, note that $(-1)^i$ alternates between $+1$ and $-1$, so this
sum expands to:

$$0 ={{n \choose 0}}  - {{n\choose 1}} + {{n \choose 2}} - {{n \choose 3}} \ldots$$
}
}

\ppart\pts{5} Prove algebraically that $\binom{2n}{n}$ is even.
\hint It may be helpful to draw Pascal's triangle in order to get some
intuition about why this must be true. However, your proof should make
no reference to Pascal's triangle whatsoever.

\solution{\ssl
\[
\binom{2n}{n}=\binom{2n-1}{n-1}+\binom{2n-1}{n}=2\binom{2n-1}{n}
\]
}

\largespace

\ppart\pts{5} Prove that $\binom{2n}{n}$ is even using a
combinatorial argument.

\solution{
\ssl
Suppose that you're looking for the number of bit strings of length $2n$ which have exactly $n$ 1's. There are $\binom{2n}{n}$ such strings. Now, look at one of these strings. It has $n$ 1's, so it also has $n$ 0's at the remaining positions. Somewhere else in our collection there exists exactly one string whose 1's are precisely at those positions occupied by the 0's in our first string. We can consider these two to be a \emph{pair}. It is easy to see that no string in our collection could possibly be ``single". Since all of our $\binom{2n}{n}$ occur in pairs, this number must be even.
} 

\nextproblem
\problem \pts{15}\textbf{Probability}
% From http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251/Site/
% Quiz 3 review
\ppart\pts{4} What's the probability that $0$ doesn't appear
among $k$~digits chosen independently and uniformly at random?

\solution{\ssl $9^k/10^k$.}

\smallspace

\ppart\pts{3} A box contains $90$ good and $10$ defective
screws. What's the probability that if we pick $10$~screws from the
box, none will be defective?

\solution{\ssl
$$\frac{\binom{90}{10}}{\binom{100}{10}} = \frac{(90!)^2}{100!80!}$$
}

\smallspace

\ppart\pts{3} First one digit is chosen uniformly at random from
$\{1,2,3,4,5\}$ and is removed from the set; then a second digit is
chosen uniformly at random from the remaining digits. What is the
probability that an odd digit is picked the second time?

\solution{\ssl Condition on the event that the first digit is odd, get
  $\frac{2}{4} \cdot \frac{3}{5}+\frac{3}{4} \cdot \frac{2}{5} =
  \frac{12}{20} = \frac{3}{5}$.}

\smallspace

\ppart\pts{3} Suppose that you \emph{randomly} permute the
digits $1, 2,\cdots,n$, i.e., you select a permutation uniformly at
random. What is the probability the digit $k$ ends up in the
$i\th$ position after the permutation?

\solution{\ssl $(n-1)!/ n! = 1/n$. This makes perfect sense, since it's a random permutation, so any digit ends up in position i with probability $\frac{1}{n}$.}

\smallspace

%From http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251/Site/
%Final exam review 1998

\ppart\pts{3} A fair coin is flipped $n$ times.  What's the
probability that all the heads occur at the end of the sequence?
\emph{Clarification:} If no heads occur, then ``all the heads are at
the end of the sequence'' (the statement is vacuously true).

\solution{\ssl $(n+1) {1/2}^{n}$.}



\nextproblem
\problem\pts{5} \textbf{More Probability}

%From ``A first course in Probability"
%p 119, exercise 6
Prove that if $E_1, E_2,\ldots,E_n$ are mutually independent events, then
\[
\Pr\left[E_1\union E_2\union \cdots \union E_n\right]=1-\prod^n_{i=1}\left[1-P(E_i)\right]
\]

\solution{\ssl
  \begin{eqnarray*}
    \Pr\left[E_1\union E_2\union \cdots \union E_n\right] &=&
    1 - \Pr\left[\overline{E_1\union E_2\union \cdots \union E_n}\right] \\
    &=&
    1 - \Pr\left[\overline{E_1} \intersect \overline{E_2} \intersect
      \cdots \intersect \overline{E_n}\right] \\
    &=&
    1 - \prod_{i=1}^n\Pr\left[\overline{E_i}\right] \\
    &=&
    1 - \prod_{i=1}^n\bigl(1 - \Pr[E_i]\bigr).
  \end{eqnarray*}
  
  The most common error here was to claim that since the $E_i$ are
  independent, $\Pr(E_1 \union \cdots \union E_n) = \Pr(E_1) + \cdots
  + \Pr(E_n)$. This is false, it holds when the events are disjoint.}

\nextproblem
\problem\pts{10} \textbf{Yet More Probability}

%\ppart
%From ``A first course in Probability"
%p 124, exercise 8
You ask your neighbor to water a sickly plant while you are on
vacation. Without water, it will die with probability $0.8$; with
water it will die with probability $0.15$. You assume a 90\%
probability that your neighbor will remember to water the plant.

\ppart\pts{5} What is the probability that the plant will be alive when you return?

\mediumspace
\solution{\ssl
0.785}


\ppart\pts{5} If it is dead, what is the probability that your neighbor forgot to water it?
\solution{\ssl
\[
\frac{16}{43}=0.372
\]

}
\nextproblem
\problem\pts{10} \textbf{Random variables}
% from http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251/Site/
% Quiz 3, 2000

David and Lars decide to select their lucky numbers from the set of
numbers $\{1,\ldots,n\}$, where $n=k^2$ for some positive integer $k$.
Lars selects his $k$ distinct lucky numbers uniformly at random.
David also selects his $k$ distinct lucky numbers uniformly at random,
independent of which numbers were selected by Lars.

\ppart\pts{5} What is the probability that the number~$i$ (where
$1 \le i \le n$) ends up in Lars's set of lucky numbers?

\solution{\ssl It may seem pretty obvious that since Lars chooses $k$
  out of $k^2$ numbers, there is a $k/k^2 = 1/k$ chance that a
  particular number gets chosen, but let's work this our carefully.
  We count the number of choices which include a specific number~$i$
  over the total number of choices Lars made:
  \[
  \frac{\mychoose{k^2-1}{k-1}}{\mychoose{k^2}{k}} = 
  \frac{(k^2-1)!}{(k-1)!(k^2-k)!}\frac{k!(k^2-k)!}{(k^2)!}=
  \frac{k}{k^2}=
  \frac{1}{k}
  \]
  }

\mediumspace

\ppart\pts{5} What is the expected size of the intersection of
the sets of lucky numbers chosen by Lars and David, i.e., what is the
expected number of lucky numbers that Lars and David agree on?

\solution{\ssl Let $Y$ be the number of lucky
numbers on which they agree. For $i\in\{1,\ldots,k^2\}$, let $X_i$ be
an indicator variable on whether they agree $i$ is a lucky number

Since $Y=\sum_{i=1}^{k^2} X_i$, by linearity of expectation:
\[
E[Y] = \sum_{i=1}^{k^2} E[X_i] = \sum_{i=1}^{k^2} \Pr(X_i=1).
\]
What the probability that $X_i=1$, or in other words the probability
that both Lars and David pick the number~$i$? Since their choices were
independent, we can just multiply the probability that Lars picks~$i$
with the probability that David picks~$i$ to get $\Pr(X_i=1)$.  Since
both Lars and David has a $1/k$ chance of picking $i$, so the
probability that they both did is $1/k^2$. For all $i$, $E[X_i]=1/k^2$
so
\[
E[Y] = k^2 \frac{1}{k^2} = 1
\]

}

\ignore{%

\mediumspace

\ppart\pts{5} What is the probability that Lars and David do not
agree on any lucky number?

\solution{\ssl Suppose that Lars has chosen his $k$~numbers. Then
  David can choose his $k$~numbers in $\binom{n}{k}$ ways;
  $\binom{n-k}{k}$ of those choices do not intersect with Lars's set at
  all. Therefore, the probability that Lars and David do not agree on
  an lucky number is $\binom{n-k}{k} / \binom{n}{k} = ((n-k)!)^2 /
  (n!(n-2k)!$.}

}

\ignore{
\ppart 
%from http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251/Site/
% final exam 1997
What is the expected sum of a randomly chosen subset $S$ of $\{1, 2,
3, \ldots, 20\}$? (In other words, $S$ is equally likely to be any of
the $2^{20}$ subsets.  The sum of $S$ is the sum of all its elements.
The sum of the empty set is 0. What is the expectation of this sum?)

\solution{\ssl

Define the random variable $X_i$ as follows: $X_i=i$ if $i$ is in the
chosen subset; otherwise $X_i=0$.  Thus $S = X_1 + X_2 + \cdots +
X_{20}$.  By linearity of expectation, $E[S] = E[X_1] + E[X_2] + \cdots
+ E[X_{20}]$.  Since each $i$ is equally likely to be in the set as not,
$E[X_i] = {i \over 2}$.  Thus
\begin{eqnarray*}
E[S] & = & \sum_{i=1}^{20} {i \over 2} \\
& = & {1 \over 2} \sum_{i=1}^{20} i \\
& = & {1 \over 2} {20 \cdot 21 \over 2} \\
& = & 105
\end{eqnarray*}
}
}

\ignore{

\nextproblem

\problem\pts{10} \textbf{Expectation}
%From ``A first course in Probability"
%p 392, exercises 3 and 9

Twenty individuals, consisting of 10 married couples, are to be seated
at 5 different tables, with 4 people at each table.

\ppart If the seating is done ``at random", what is the expected
number of married couples that are seated at the same table?

\ppart If two men and two women are randomly chosen to be seated
at each table, what is the expected number of married couples that are
seated at the same table?

\ppart Now, suppose that those 20 people are going to be seated
at \emph{seven} tables, 3 of which have 4 seats and 4 of which have 2
seats. If the people are randomly seated, find the expected value of
the number of married couples that are seated at the same table.

}

\nextproblem
\problem\pts{10} \textbf{Expected Value}

A new 24-hour cold is spreading around campus.  On the day they become
infected, a person meets $n$ people, each of whom catch the cold on
the following day independently with probability $p$.  Assume that one
person catches the cold on day 0.

\begin{problemparts}

\ppart \pts{3} Suppose that $r$ people are infected on day $k$. What is the
expected number of people infected on day $k+1$?

\smallspace

\solution{The number of infected people on day $k+1$ is $Y_1 + \cdots
  + Y_r$, where each $Y_i$ is $\mathrm{Bin}(n,p)$. Therefore, the
  expected number of infected people is $nrp$.

  Most people got this one right.}

\ppart \pts{3} Justify and then use Wald's theorem to prove by induction that
the expected number of people infected on day $k$ is $(np)^k$

\smallspace

\solution{\ssl Suppose that $Q_k$ persons have a cold on day~$k$. Let
  $X_{i,k}$ be the number of persons infected by person~$i$ on
  day~$k$. Then
  \begin{displaymath}
    Q_{k+1} = \sum_{i=1}^{Q_k}\sum_{j=1}^n X_{i,j}.
  \end{displaymath}
  Since $Q_k$ and the $X_{i,k}$ are independent, Wald's theorem
  applies, which gives
  \begin{displaymath}
    \Ex(Q_{k+1})
    =
    \Ex\biggl(\sum_{j=1}^n X_{i,j}\biggr) \Ex(Q_k).
    = np \Ex(Q_k).
  \end{displaymath}
  Note that $X_{i,k}$ is $\mathrm{Bin}(n,p)$; therefore $\Ex(X_{i,k})
  = np$ and $\Ex(Q_{k+1}) = np \Ex(Q_k)$. This is a linear recurrence
  for $\Ex(Q_k)$. Given the base case $Q_0 = 1$ it has the solution
  $\Ex(Q_k) = (np)^k$.
  
  Less than 5~people got this one right. Most people argued that since
  the expected number of people is something, these expected people
  are expected to infect some other people, which gives some new
  expected number of infected people. This is not valid reasoning, and
  Wald's theorem is indeed needed to make the argument formal. Others
  thought that the number of infected people is $(np)^k$ on day~$k$,
  when in fact this number is the expectation of the random variable
  denoting the number of infected people on day~$k$.}

\ppart \pts{4} Suppose that $np < 1$.  Show that the expected total number of
people who catch the cold is finite.  Determine this number.

\solution{\ssl The expected total number of people who catch the cold is
  \begin{displaymath}
    \sum_{k=0}^{\infty} (np)^k = \frac{1}{1 - np}\,.
  \end{displaymath}
  
  Most people got this one, some didn't compute the total number of
  infected, but rather the limit of $(np)^k$ as $k \rightarrow
  \infty$.}

\end{problemparts}

\nextproblem
\problem\pts{10}\textbf{Exponential distribution}

The 042 staff is taking a post-class vacation trip to California in
Professor Karger's car.  The tires on this car have an expected
lifetime of 20,000 miles before going flat.  Model the distances the
tires can go before going flat as independent, exponentially
distributed random variables.

\ppart\pts{3} A skilled driver, Professor Karger can ignore the first
flat tire and keep going until he gets a second flat.  What is the
expected distance Professor Karger can expect to drive before
stopping?
\smallspace
\solution{\ssl
For one tire, $\lambda=\frac1{20,000}$. For 4 tires, $4\lambda=\frac{1}{5,000}$. The expected distance before the \emph{first} tire goes flat is $\frac{1}{4\lambda}=5,000$ miles. After that, the expected distance for the second tire to go flat will be $\frac{1}{3\lambda}=\frac{20,000}{3}$. Therefore, Professor Karger can expect to drive for \[
5,000+\frac{20,000}{3}=11,667\]
miles before stopping.}



\ppart\pts{3} What is the probability that Professor Karger will have to
stop before the end of the 3000 mile trip to California?

\smallspace
\solution{\ssl
Let $p$ denote the probability that a particular tire will last for $\geq 3,000$ miles. Then:
\[
p=e^{-\frac{3,000}{20,000}}=e^{-\frac{3}{20}}=0.861
\]
The probability that Prof. Karger will \emph{not} have to stop is equal to the probability that he gets \emph{at most 1} flat tire during the trip, which is Pr(no flat tire)+Pr (exactly 1 flat tire). Therefore, the probability that he \emph{will} have to stop is 
\[
1-p^4-\binom{4}{3}p^3(1-p)=0.0959\]
Of course we get the same answer if we calculate the probability that \emph{at least} 2 tires go flat, which is: Pr(exactly 2 flat tires)+Pr(exactly 3 flat tires)+Pr(exactly 4 flat tires), or in other words
\[
(1-p)^4+\binom{4}{3}(1-p)^3p+\binom{4}{2}(1-p)^2p^2=0.0959
\]
 
} 
\ppart\pts{4} Thanks to his intensive training on the icy slopes of
Swedish mountains, Dr. Engebretsen can even handle two flat tires, so
long as they occur on the same side of the car.  How long can Dr.
Engebretsen expect to drive before two flat tires \emph{on opposite
  sides of the car} force him to pull over?
\solution{\ssl
The expected distance before the \emph{first} tire goes flat is $\frac{1}{4\lambda}=5,000$ miles. After that, the expected distance before \emph{one} of the two tires on the opposite side of the car goes flat will be $10,000$ miles. So the total is $15,000$ miles.
}




\nextproblem 
\problem \pts{10} \textbf{Connectivity}

MIT Information Services wants to put together a new computer cluster
involving $n$ computers.  They want to connect these computers to each
other with wires and a collection of hubs.  Each computer must have
exactly one wire attached to it, while each hub can have up to five
wires attached.  I.S. wants to minimize the number of hubs used to
build this network, in which every pair of computers must be connected
by a path of wires and hubs.

\ppart\pts{2} Supposing that I.S. uses $m$ hubs, what is the maximum
number of wires that can be attached to the hubs and computers without
leaving dangling ends?

\solution{\ssl $(5m+n)/2$.}

\smallspace

\ppart\pts{2} Again supposing that I.S. uses $m$ hubs, and momentarily
ignoring the restriction on the number of wires that may be attached
to a hub, what is the minimum necessary number of wires needed to
connect all the computers and hubs to each other (such that there is a
path along the wires and hubs between any two hubs or computers?

\solution{\ssl $m+n-1$.}

\smallspace

\ppart \pts{1} Compare the previous two quantities to prove that at
least $\lceil \frac{n-2}{3}\rceil$ hubs are needed to hook up
the network.

\mediumspace

\solution{\ssl Algebra on the previous two parts.}

\ppart\pts{5} Prove by induction that $\lceil \frac{n-2}{3}\rceil$
hubs are sufficient to build the desired network (The previous part
shows this result is tight).

\solution{\ssl The theorem is true for $n=1$ (no wires needed), for
  $n=2$ (connect directly to each other), and $n=3$ (use one hub in
  the obvious way).  To prove the theorem for $n>3$, consider an
  optimum network on $n-3$ computers; it used $\lceil
  \frac{n-2}{3}\rceil - 1$ hubs by induction.  Take some computer on
  this network, and replace it with a hub.  This decrease the number
  of computers by 1 and adds one hub with 4 unused connections.
  Attach 4 computers to these connections.  Overall we have added one
  hub and three computers (removed one and added four).  This proves
  the inductive step.}


\end{problems}

\end{document}


After graduating from MIT, you are hired by a startup company that
specializes in organizing frog races.  Your first assignment is to
plan the finals for a race near Johnstown, Pa.  The competition is run
in two stages.  First, some preliminary races are run between small
groups of the frogs.  Then, the results of those races are used to
determine the frogs' starting positions for the final, deciding race.
All the preliminary races have been run with the following results:


\begin{center}
\begin{tabular}{l|c|c|c|c}
  & Race 1 & Race 2 & Race 3 & Race 4 \\ 
\hline
  1st & Lars & Ivan & David & Ray \\
  2nd & Ray & Josh & Lars & George \\
  3rd & Kavita & Tina & Ivan & Tina \\
  4th & Be & Be & Joe & Joe
\end{tabular}

\end{center}



You must line the 10 frogs up for the final race so that no frog is
after a frog it has beaten in one of the preliminary rounds.  Give one
possible ordering.

\solution{\medskip
\textbf{Solution:}

Two possible orderings are:

David, Lars, Ivan, Josh, Ray, George, Tina, Joe, Kavita, Be

and

David, Lars, Ray, Kavita, George, Ivan, Josh, Tina, Be, Joe

}


\ignore{

\nextproblem
\problem\pts{10} \textbf{Recurrences}


% From http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251/Site/
% Final 1998
Solve the following recurrence:
\begin{eqnarray*}
T(n) & = & 6T(n-1) - 8T(n-2) \\
T(0) & = & 0 \\
T(1) & = & 1
\end{eqnarray*}
\medskip
\solution{\ssl
This problem is a linear recurrence (like the Fibonacci recurrence),
so we can solve it by assuming that all solutions have the form
$T(n) = \lambda^n$, and substituting to solve for $\lambda$:
\begin{eqnarray*}
\lambda^n = 6\lambda^{n-1} - 8\lambda{n-2} \\
\lambda^n - 6\lambda^{n-1} + 8\lambda{n-2} = 0 \\
\lambda^{n-2} (\lambda^2 - 6\lambda + 8) = 0 \\
\lambda^{n-2} (\lambda - 4) (\lambda - 2) = 0
\end{eqnarray*}

The values of $\lambda$ that satisfy this equation are $\lambda = 0,
2, 4$.  Thus $T(n)$ is a linear combination of $2^n$ and $4^n$ (since
$0^n$ contributes nothing).  Let $T(n) = a2^n + b4^n$, and solve for
$a$ and $b$ with the base cases:

\begin{eqnarray*}
T(0) = a2^0 + b4^0 = 0 \\
T(1) = a2^1 + b4^1 = 1 \\
\\
a + b = 0 \\
2a + 4b = 1 \\
\\
a = -{1 \over 2} \\
b = {1 \over 2}
\end{eqnarray*}

So the answer is
$$T(n) = -{1 \over 2}2^n + {1 \over 2}4^n$$
}



}




\ignore{
\nextproblem

\problem\pts{15} \textbf{Expectation and sums}

Short-term Capital Management (STCM) wants you to invest in a
fund with the following rules: You invest one million dollars in their
Forward Looking Internet Package (FLIP). Each year, the value of your
FLIP will double or halve (each with 50\% probability).  Once the
doubling/halving has been determined in a given year, STCM will pay
you one tenth of the current market value of your investment out of
their own pockets (i.e., that money they pay you every year is not
deducted from your investment). [In this problem, you can assume that
the interest rate is 0\%, i.e., the present value of an investment is
always equal to the value of the investment.]

\ppart\pts{5} What is the expected market value of your investment at
the end of $k$ years?

\solution{\ssl If the starting capital is~$D$, the value of the
  investment after $k$~years is $D \cdot 2^{X_1} \cdot 2^{X_2} \cdots
  2^{X_k}$ where $X_1$~is $1$ with probabilty $1/2$ and $-1$ with
  probability $1/2$. Since the $X_i$~are independent, the expectation
  of the products is the products of the expectations. Moreover,
  $\Ex(2^{X_i}) = (2^1 + 2^{-1})/2 = 5/4$. To sum up, the expected
  value after $k$~years is $10^6 \cdot (5/4)^k$.}

\mediumspace

\ppart\pts{5} Give a closed form expression for the total amount of
money you expect to receive over the 10~years.

\solution{\ssl
  \begin{displaymath}
    10^5 \sum_{k=1}^{10} (5/4)^k = 5 \cdot 10^5 \bigl((5/4)^{10}-1\bigr)
    = \frac{43585245}{1048576} \cdot 10^5
  \end{displaymath}}



\ignore{

\smallspace

\ppart What is the expected market value of your investment at the end
of $k$~years if your annual payment is taken from your investment
instead of from STCM's pockets?

\solution{\ssl $10^6 \cdot (0.9\cdot5/4)^k = 10^6 \cdot (9/8)^k$.}

}
\smallspace

\ppart\pts{5} Adam Smith analyzes the above questions the following
way.  Let $x_i=1$ if our money doubles after year $i$, and $-1$
otherwise.  Then the value of our investment after year $k$ is $ 10^6
\cdot 2^{x_0+x_1+\cdots+x_k}$. Note that
$E[x_i]=0$.  It follows that $2^{E[\sum x_i]}=1$, which implies that
the expected value of our investment in year $k$ is equal to our
original investment.  What is wrong with this analysis?

\solution{\ssl $\Ex(2^{x_0+x_1+\cdots+x_k}) \neq 2^{E[\sum x_i]}$.}
}



\ignore{
\nextproblem
\problem \pts {10} {\bf Random graphs}

A Hamiltonian tour is a cycle that includes all the vertices of the
graph exactly once.  Note that the tour has no specific start or end
point---it is simply the circular sequence of visited nodes.

\ppart Suppose that you have a \emph{complete} graph on $n$ vertices\footnote{see Figure \ref{complete} on page \pageref{complete} for an example of a complete graph on 5 vertices}. How many Hamiltonian tours does it have? \hint Beware of overcounting...

\ppart Now suppose that you write down $n$ vertices on a piece
of paper and then, for every pair $(u,v)$ of vertices on the page, you
create an edge between $u$ and $v$ independently with fixed
probability $p$.  What is the expected number of Hamiltonian tours?

\solution{\ssl
A Hamiltonian tour is a simple cycle that visits all the
vertices once, so the problem reduces to finding the expected number
of simple cycles with exactly $n$ nodes in the cycle. Each $n$-cycle
has $n$ edges as well, so given a possible cycle $c$, each edge is
distinct, so there is a $p^n$ 
chance of that particular cycle existing (since the edges are
distinct, the events are independent). This is also the expectation 
of the number of cycles on that particular path. (Formally, if we
define a random variable $\chi_c$ that takes on the value 1 when the
cycle exists and 0 when it does not, then $E[ \chi_c ] = p^n$.) If we
can find the number of possible cycles, we can then use linearity of
expectation to find the expectation easily. At first glance, there are 
$n!$ permutations of the nodes (the nodes are distinct), but we need
to take into account that cycles are the same through rotation and
through flipping (i.e. $ABCD = BCDA = ADCB$). So we are overcounting
by a factor of $2n$ ($n$ possible rotations, each with a possible
flip). Thus there are $\frac{n!}{2n} = \frac{(n-1)!}{2}$ possible
cycles (for instance, a square has 3 Hamiltonian cycles, but a
triangle only has one). By linearity of expectation, the expected
number of cycles is then:

$$ \frac{(n-1)!}{2} p^n $$
}

}

