\documentclass[11pt,twoside]{article}
\usepackage{amsmath} %,graphicx}
\input{/a/class/6.042/fall99/inputs/macros-course}

\begin{document}

%\renewcommand{\solution}[1]{}

\handout{pracfinal}{Practice Questions for Final}{December 9, 1999}

\begin{problems}
\let\comp\circ

\problem \textbf{Short Answers.}
\bparts

\ppart An assembly line produced 10001 cars which passed inspection and 19
which did not.  What is the largest $n$ for which there must have been a
run of $n$ consecutive cars that passed inspection?  \brule{1.0in}
\solution{501}

\ppart %F96 Final

A bridge hand consists of 13 cards.  The {\em suit-distribution} of a hand
is the number of cards in each suit.  For example, one possible
suit-distribution is 4 spades, 3 hearts, 3 diamonds, and 3 clubs.  How many
suit-distributions are there?

\solution{This is equivalent to placing 13 balls (corresponding to each
card in a hand) to 4 bins (corresponding to each suit).  Thus the number of
distributions is $\binom{13 + 4 - 1}{4 - 1} = 560.$
}

\ppart In an employment interview for an expedition to the Sahara desert, a
weather forecaster honestly promises at least 95\% accuracy for his daily
predictions of sunshine versus rain.  Is this an impressive credential for
the job?  Briefly explain.

\solution{Unimpressive: he could be 95\% accurate by always predicting
sunshine.  It would be impressive if his daily prediction also was 95\%
accurate \emph{given that it rained}.}

\ppart In a simple path in an undirected tree with $n$ vertices, what is
the largest number of edges possible? \brule{0.7in}

\solution{$n-1$}

\ppart What is the coefficient of $x^{12}$ in the polynomial $(7x+3)^{50}$?
(Your answer may contain binomial coefficients and integer powers.)

\solution{$3^{50-12}7^{12}\binom{50}{12}$}

\ppart Write a closed form expression for
\iffalse
\[
\prod_{k=1}^\infty 2^{2^{(-k)}}.  \brule{1in}
\]
\fi
\[
\prod_{k=1}^\infty 2^{1/2^k}.  \brule{1in}
\]

\solution{$2^{\sum_{k=1}^\infty 1/2^k} = 2^1 = 2.$}

\eparts

\problem {\bf Pigeon Hole Principle}

\bparts

\ppart
Six people communicate via radio frequency with one another. Each pair
of people choose one of {\bf two} available frequencies with which to
communicate.  Show that there is a subset of 3 people who are each
using the identical frequency with which to communicate with others in
the subset.

\solution{
Each person communicates with five other persons.  By the pigeonhole principle,
this person (say $a$) communicates with another three persons (say $b$,$c$,and $d$)
using the same frequency.
If either of the pairs $(b,c), (b,d), (c,d)$ uses this frequency then we have three persons
using it to communicate with each other and we are done.
If not, then the pairs $(b,c), (b,d), (c,d)$ all use the other frequency, so we are done again.
}

\ppart
Now suppose there are seventeen people communicating via radio 
frequency with one another. Each pair
of people choose one of {\bf three} available frequencies with which to
communicate.  Show that there is a subset of 3 people who are each
using the identical frequency with which to communicate with others in
the subset.

\solution{
Now each person communicates with sixteen other people, 
and by pigeonhole uses the same frequency  with at least six of them.
If any pair among these six persons uses that same frequency then we are done.
If not, then these six persons communicate with one another using two 
different frequencies so we are back in part (a) of the problem.
}

\eparts

\problem \textbf{True/False?}

In this problem, $A$, $B$ and $C$ denote arbitrary sets. $f$ and $g$ are
functions as specified in each part and $I_A$ denotes the identity function 
on the set $A$.
For each statement indicate whether it is {\bf T}rue or {\bf F}alse. No
explanation is required.

\def\true{{\bf T}rue:}
\def\false{{\bf F}alse:}

\begin{list}{{\bf T\ \ F\ \ \ }}{\setlength{\leftmargin}{40pt}%
        \setlength{\labelwidth}{\leftmargin}%
}

\item[\true]
There exists an injection (one-to-one) $f:A\to B$ if and only if there
exists a surjection (onto) $g:B\to A$.

\item[\false]
Let $f:A\to B$ and $g:B\to A$. $f\comp g=I_B$ implies $g\comp
f=I_A$.

\item[\true]
Let $f:A\to B$ and $g:B\to C$. If both $f$ and $g$ are injections,
then $g\comp f$ is an injection.

\item[\false]
Let $f:A\to B$ and $g:B\to C$. $g\comp f$ is a surjection implies both
$f$ and $g$ are surjections.

\item[\false]
Let $f:A\to B$ be an injection. If $|B|\leq |A|$, then $f$ is a
bijection.

\item[\true]
Adding $k$ edges to an undirected graph increases its chromatic
       number (the number of colors needed to color the vertices)
       by at most $k$.

\item[\false]
The number of length-$3$ paths in an $n$-vertex undirected graph is
       $O(n^2)$.

\item[\false] 
The number of length-$3$ paths in an $n$ vertex tree is $O(n)$

\item[\true]
Reversing the directions of all edges in a directed graph leaves
       the number of simple directed cycles unchanged.

\item[\false]
If an undirected graph has the degree of every vertex divisible
       by a prime $p$, then $p$ must evenly divide the number of edges.

\end{list}

\problem \textbf{Cardinality.}  Let $P(A)$ denote the powerset of a
set $A$.  Prove there is no bijection between $S$ and $P(P(S))$ for any set
$S$.

\solution{By contradiction.  If there was such a bijection, then there is
an surjection from $S$ to $P(P(S))$.  But there is an obvious surjection
$P(P(S))$ to $P(S)$, namely map every one-element set $\set{T}\in P(P(S))$
to $T \in P(S)$ (and map all the other elements of $P(P(S))$ to an
arbitrary member of $P(S)$---say the empty set).  Since the composition of
surjections is a surjection, we conclude there is an surjection from $S$ to
$P(S)$, contradicting Cantor's Theorem.}

\problem \textbf{Inclusion-exclusion.}  Consider the seven letter
word \emph{almeyer}.

\bparts

\ppart\pts{5} How many different sequences of these seven letters are
there? \brule{1in}

\solution{$\binom{7}{1,1,1,2,1,1} = 7!/2!$}

\ppart\pts{10} How many such sequences are there that do not contain
either of the words \emph{eye} or \emph{ram}? \brule{1in}

\solution{
\begin{eqnarray*}
\mbox{Arrangements with eye: use} \set{eye,a,l,m,r} & = & 5!\\
\mbox{Arrangements with ram: use} \set{ram,l,e,y,e} & = & 5!/2!\\
\mbox{Arrangements with ram and eye: use} \set{ram,eye,l} & = & 3!\\
\mbox{Arrangements with neither ram nor eye}
      & = & 7!/2! - 5! - 5!/2! + 3! = 2346.
\end{eqnarray*}
}

\eparts

\problem \textbf{Bridge}

A bridge hand consists of 13 cards.  The {\em suit-distribution}
of a hand is the number of cards in each suit.  For example, one possible
suit-distribution is 4 spades, 3 hearts, 3 diamonds, and 3 clubs.  \bparts
\ppart How many different suit-distributions are there?

\solution{
This is equivalent to placing 13 balls (corresponding to each card in
a hand) to 4 bins (corresponding to each suit). Thus the number of
distributions is
\[
{\rm BP}(13,4) = {\binom{13 + 4 - 1}{4 - 1}} = 560{.}
\]
}

\ppart
How many different suit-distributions are there assuming that you get at
least one card in each suit?

\solution{
By using the same correspondence as in part (a), the number of
distributions is
\[
{\rm BP1}(13,4) = {\binom{13-1}{4-1}} = 220{.}
\]
}

\eparts

\problem \textbf{Conditional Probability.}  We consider a
hypothetical Institute with only two departments: EECS and Math, and
consider the experiment where we pick a random applicant for admission to
one of these departments.  Define the following events:
\begin{center}
\begin{tabular}{rcl}
A & ::= & applicant is accepted,\\
F & ::= & applicant is female,\\
M & ::= &  applicant is male,\\
MATH & ::= & applicant applied to Math,\\
EECS & ::= & applicant applied to EECS.
\end{tabular}
\end{center}
Assume that all applicants are either male or female, and that no
applicant applied to both departments.
\iffalse
That is, the events $F_{EECS}$,
$F_{CS}$, $\mbox{M-EECS}$, and $\mbox{M-CS}$ are all disjoint.
\fi

\bparts

\ppart The Institute is sued for gender discrimination, with
the plaintiff observing that in both EECS and Math, the probability that a
woman is accepted is less than the probability that a man is accepted.
This observation can be precisely expressed with two inequalities
between conditional probabilities involving the events above.  State these
inequalities.

\solution{
\begin{eqnarray*}
\Pr(A \mid F \intersect EECS) & < & \Pr(A \mid M \intersect EECS), \\
\Pr(A \mid F \intersect MATH) & < & \Pr(A \mid M \intersect MATH).
\end{eqnarray*}
}

\ppart The Institute's defense attorneys retort that overall among all
applicants, a woman is {\em more} likely to be accepted than a man.
Express this observation as an inequality between conditional probabilities
involving the events above.

\solution{
\begin{eqnarray*}
\prob{A \mid F} & > & \prob{A \mid M}
\end{eqnarray*}
}

\ppart Although the assertions above may appear to be logically
inconsistent, both the plaintiff's and the defense's claims about the
conditional probabilities can be correct. (Never mind whose interpretation
of the data we find more persuasive.)  Fill in the missing table entries
below with possible applicant statistics for which both the plaintiff and
the University attorneys' assertions are true.

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c|}
\hline
& &\hspace*{1in}&\\
     & Applied & Accepted & percent accepted\\
 & & & \\ \hline \hline & & &\\
Dept & Females & Females &  Females\\
& & & \\ \hline & & &\\
Math & & & \\ & & & \\ \hline & & &\\
EECS & 100 & 70 & 70\% \\ & & & \\ \hline & & &\\
Total & &  & \\ & & &\\ \hline \hline & & &\\
Dept & Males & Males & Males\\
& & & \\ \hline & & &\\
Math & 100 & 50 & 50\% \\ & & & \\ \hline & & &\\
EECS & & & \\ & & & \\ \hline & & &\\
Total & &  & \\
& & &\\
\hline
\end{tabular}
\end{center}

\solution{
\[
\begin{array}{ccr}
\mbox{Math} & \mbox{0 females accepted, 1 applied} & 0\% \\
          & \mbox{50 males accepted, 100 applied} & 50\% \\
\mbox{EECS} & \mbox{70 females accepted, 100 applied} & 70\% \\
          & \mbox{1 male accepted, 1 applied} & 100\% \\
\hline
\mbox{Overall} & \mbox{70 females accepted, 101 applied} & \approx 70\% \\
          & \mbox{51 males accepted, 101 applied} & \approx 51\%
\end{array}
\]
}

\eparts

\problem \textbf{Roulette wheel}

You are given a roulette wheel which contains the numbers from 1 to 2n
arranged in some way.  The wheel has a spinner and on each spin, you
get the two numbers at the opposite ends of the spinner.  How would
you arrange the numbers on the wheel to maximize the expected value
of:
\begin{enumerate}

\item The sum of the numbers chosen?  

\solution{It makes no difference how we arrange the numbers.  The
expected value is the same.  Why?  If we label the ends of the spinner
we can define 2 random variables $X$ and $Y$.  $X$ is the number
pointed to by one end of the spinner, and $Y$ is the other number.  We
wish to maximize $E(X+Y)$.  But clearly $E(X)=E(Y)=(2n+1)/2$ and by
linearity of expectation, $E(X+Y)$ is just $E(X)+E(Y)=2n+1$.}

\item The product of the numbers chosen?

\solution{The best way to do this is to ensure that $1$ is opposite
$2$, $3$ is opposite $4$, $\ldots$, and $2n-1$ is opposite $2n$.
Let's call this arrangement $A^*$. This will maximize the expected
value of the product.

Consider any arrangement that isn't the one described above.  It
therefore must contain an odd $i$ that isn't paired up with $i+1$.
Pick the smallest such $i$ and call it $k$.  Say $k$ is opposite $p$
and $k+1$ is opposite $q$.  We know that $p$ and $q$ are bigger than
$k$ (by choosing $k$ to be the smallest such number we are assured
that all numbers smaller than $k$ are ``properly'' paired up).  Now
consider the new arrangement where $k$ is paired with $k+1$ and $p$ is
paired with $q$.  It has a better expected product than the previous
arrangement.

To prove this note that since all pairs are equally likely when we turn the
spinner, it suffices to show that the sum of the products of the numbers
(denoted by $S$) is larger in the second arrangement.  
\begin{eqnarray*}
S_2 - S_1 & = & k(k+1) + pq - kp - (k+1)q \\
          & = & k^2 + k + pq - kp - kq - q \\
                  & = & k^2 + (1-p-q)k + (p-1)q \\
                  & = & (k-q)(k-(p-1))
\end{eqnarray*}

Thus $S_2 - S_1$ is greater than zero if $k$ is smaller than both $q$
and $p-1$.  But this is true because of our choice of $k$.  Thus the
second arrangement is better.

Now we can transform any arrangement that isn't equal to $A^*$ by
repeatedly applying the following operation:

``Find the smallest odd $i$ that isn't paired up with $i+1$.  If $i$
is paired with $p$ and $i+1$ with $q$ then pair $i$ with $i+1$ and $p$
with $q$''

Each time we perform this operation, we increase the expected value of
the product.  Thus $A^*$ must be the best arrangement since it is the
only arrangement where we cannot perform this operation.}

\end{enumerate}

\problem \textbf{Expectation and Variance}

Suppose the entries $a,b,c,d$ of a $2\times 2$ matrix 

$$
M=
\begin{pmatrix}
a & b\\ c & d \end{pmatrix}\quad
$$

are chosen independently at random according to the uniform
distribution on $\{0,1,2,3,4\}$.  Let $X = \det(M) = ad-bc$.
\bparts
\ppart What is $E(X)$?

Using linearity of expectation
\[
E(X) = E(ad-bc) = E(ad) - E(bc) = 0
\]
because $ad$ and $bc$ are identically distributed.

\ppart What is $E(X\mid b = 1)$?

Using linearity of expectation and the rule 
$E(XY)=E(X)E(Y)$ for independent random variables
we have
\begin{eqnarray*}
E(X|b=1) &=& E(ad|b=1)  - E(bc|b=1) \\
  &=& E(ad) - E(c) \\
  &=& E(a)E(d) - E(c) \\
  &=& 2\cdot 2 - 2 = 2
\end{eqnarray*}

\ppart What is $Var(X)$?

\begin{eqnarray*}
 Var(X) &=& E(X^2) - E(X)^2 \\
 &=& E(X^2)\\
 &=& E((ad-bc)^2) \\
 &=& E(a^2d^2+b^2c^2-2abcd) \\
 &=& E(a^2)E(d^2) + E(b^2)E(c^2) - 2E(a)E(b)E(c)E(d) \\
 &=& 6\cdot 6 + 6\cdot 6 - 2\cdot 2^4 = 40
\end{eqnarray*}

\eparts

\problem \textbf{Probability of Graph Assertions.}  A digraph with
vertices $\set{1,2,\dots, n}$ is called an \emph{$n$-digraph}.  (The edges
of an $n$-digraph may be \emph{any} pair of vertices; self-loops are
allowed.)  Given an $n$-digraph, $G$, let ``$d(x,y)$'' be the assertion
that $G$ has a directed edge from vertex $x$ to vertex $y$.

\bparts

\ppart\pts{1} How many $n$-digraphs are there? \brule{1in} \solution{$2^{n^2}$}

\ppart\pts{1} How many $n$-digraphs satisfy the assertion $\forall x, y : d(x,y)$?
\brule{1in}\solution{1}

\ppart\pts{3} How many $n$-digraphs satisfy the assertion $\exists x, y : d(x,y)$?
\brule{1in}\solution{$2^{n^2}-1$}

\medskip

Suppose we randomly select an $n$-digraph, with all $n$-digraphs equally
likely to be selected.

\ppart\pts{5} Explain why there is nonzero probability that the selected
$n$-digraph satisfies \emph{both} of the following assertions:
\[\begin{array}{l}
\forall x_1 \exists x_2 \exists x_3 \forall x_4 \forall x_5 \exists x_6 :
d(x_1,x_2) \vee d(x_3,x_4) \vee d(x_5,x_6) \vee  d(x_3,x_1)\\
\exists x_1 \forall x_2 \forall x_3 \exists x_4 \exists x_5 \exists x_6 :
d(x_1,x_2) \wedge d(x_3,x_4) \wedge d(x_5,x_6) \wedge  d(x_3,x_1)
\end{array}\]

\solution{We need only show that some $n$-digraph satisfies both assertions.
The complete $n$-digraph is one.}

\ppart A directed Hamiltonian cycle in a digraph is a directed cycle going
through each vertex exactly once.  What is the expected number of directed
Hamiltonian cycles in the selected graph?

\solution{
\begin{eqnarray*}
\lefteqn{ \expect{\mbox{number of cycles through a particular
Hamiltonian cycle of vertices}}}\\
 & = & \prob{\mbox{all edges present in a particular cycle of the
vertices}}\\
& = & 1/2^n.
\end{eqnarray*}
The number of Hamiltonian cycles is $n!/n$ so the expected number of cycles is
$n!/n2^n$.}

\eparts

\problem \textbf{Various Games}

What is your expected return in each of the following games?  You may
assume the various coin tosses and dice rolls are independent.

\bparts

\ppart You get to roll six ordinary six-sided dice.  You win the number of
dollars equal to the total of the numbers came up on the dice rolls.

\solution{
The expected return from a single dice is $7/2$. By linearity of 
expectation the total expected return is $6(7/2) = 21$.
}

\ppart
You roll one ordinary die.  You win a number of dollars that is
equal to six times the number that came up on the die. 

\solution{
Again by linearity of expectation, the expected return is $6(7/2)=21$.
}

\ppart
You toss a fair coin six times.  For each time it comes up heads,
you toss an ordinary six-sided die.  You win the number of dollars
equal to the total number of spots that appear on all the dice.

\solution{
If you get to roll $i$ times, the expected win is, by
linearity of expectation, $i(7/2)$.
So the expected win is
\begin{eqnarray*}
\lefteqn{\sum_{i=1}^6 \text{(expected win in $i$ rolls)}\cdot \prob{i \text{
rolls}}}\\
&  = & \sum_{i=1}^6 (7/2)i\cdot \prob{i \text{ rolls}}  \\
& = & (7/2)\expect{\text{number of heads}}\\
& = & (7/2)3 = \frac{21}{2}.
\end{eqnarray*}

}

\ppart You toss a fair coin repeatedly, until it comes up ``tails'' for
the first time.  (This could involve infinitely many tosses, if ``tails''
never comes up.)  After each coin toss, you toss an ordinary six-sided
die.  You win the number of dollars equal to the total number of spots
that appear on all the dice.

\solution{

By the same reasoning as in the previous part, the expected win is 
\begin{eqnarray*}
\lefteqn{\sum_{i=1}^\infty \text{(expected win in $i$ rolls)}\cdot \prob{i \text{ rolls}}}\\
& = & (7/2) \sum_{i=1}^\infty i\prob{i \text{ rolls}}\\
& = & (7/2)\expect{\text{number of rolls}}.
\end{eqnarray*}
We know the expected number of rolls is the same as the expected
number of tosses, which is $1/(1/2) = 2$, so the expected win is 7.

}

\ppart
You roll two six-sided dice.  You win the product of the number of
spots that appear on the two dice.

\solution{
$E[X]^2 = \frac{49}{4}$
}

\ppart
 You roll one ordinary die.  You win a number of dollars that is
the square of the number of spots.

\solution{
$E[X^2] = {\frac{1+4+9+16+25+36}{6}} = {\frac{91} {6}}$
}

\eparts

\problem \textbf{Emotional Quotient.}

There is a newly developed test called EQ ({\em Emotional Quotient}),
that is used to decide whether or not you will succeed in life.
EQ is expressed as a nonnegative integer.  
The average EQ over all humans is~1000.  

\bparts

\ppart
Knowing only the average EQ, find an upper bound for 
the fraction of humans that have EQ$\geq 1500$?

\solution{
We use Markov's inequality $\Pr(X \geq cE[X]) \leq 1/c$,
with $c = 1.5$, to obtain the upper bound $2/3$.
}

\ppart
Assuming that the standard deviation of 
EQ is~100, what fraction of humans can have EQ$\geq 1500$?

\solution{
We use Chebychev's inequality 
$\Pr(X \geq E[X] + c \sigma_X) \leq {\frac{1}{1+c^2}}$
with $c = 5$ to get an upper bound of ${\frac{1}{26}}$
}

\eparts

\problem \textbf{Spider's dinner}

The spider is expecting guests and wants to catch 500 flies for her
dinner.  The expected number of flies caught in the web per hour is $40$.

\bparts

\ppart
 
What is an upper bound to the probability that the spider will have caught 500
flies in 10 hours?

\solution{
Using Markov's inequality we obtain
$\Pr(X =(5/4)400) \leq \Pr(X \geq (5/4)400) \leq 4/5$
}

 
\ppart

What is a lower bound to the probability that the spider will have to 
wait more than 10 hours to catch 50 flies?

\solution{
The event that the fly has to wait more than 10 hours to catch 500 flies
is the same as the event that the spider will catch less than 500 flies
in 10 hours.
This is the complement of the event that the spider catches at least 500 flies
in 10 hours,
so by part (a) the answer is $1 - 4/5 = 1/5$.
}

\ppart

The spider checks her log and discovers that the standard deviation
for the number of flies caught in an hour is 20.
Find an upper bound on the probability that the spider will catch 500 flies
within 10 hours, using this additional information.

\solution{
Since the standard deviation for the number of flies caught in one hour is 20, 
the standard deviation for the number of flies caught in 10 hours is 
$10\cdot 20$, by the following analysis:
\newcommand{\kvar}[1]{\ensuremath{\mathrm{Var}[#1]}}
\newcommand{\kE}[1]{\ensuremath{\mathrm{E}[#1]}}
\begin{eqnarray*}
\kvar{10X} & = & \kE{(10X)^2} - (\kE{10X})^2 \\
& = & \kE{100X^2} - (10\kE{X})^2 \\
& = & 100\kE{X^2} - 100(\kE{X})^2 \\
& = & 100(\kE{X^2} - (\kE{X})^2) \\
& = & 100\kvar{X}
\end{eqnarray*}
so the standard deviation is $\sqrt{100\kvar{X}}=10\sqrt{\kvar{X}}$, or ten
times the standard deviation of the number of flies caught in one hour.

Using Chebychev's inequality we obtain
$$
\Pr(X = 500) \leq \Pr(X \geq 400 +  {\frac{1}{2}} \cdot 200) 
\leq {\frac{1}{1+\left(\frac{1}{2}\right)^2}} = {\frac{4}{5}}
$$
}

\eparts

\end{problems}

\end{document}
