\documentstyle[12pt]{article}

\setlength{\textheight}{8.5in}

\input{/a/class/6.042/spring94/handouts/macros-course}
\newcommand\npage{\vspace{2in}}
%\newcommand\npage{\newpage}
\newcommand\tfitem{\item [{\bf T / F \hspace*{.1in} }]}
\newcommand\Ex{\mbox{Ex}}
\newcommand\vari{\mbox{Var}}
\newcommand\Prob{\mbox{Prob}}
\setcounter{page}{0}

\begin{document}

%\handout{practice-quiz-2}{Practice Quiz 2}{April 15, 1994}
\handout{finalanswers}{Final Exam Solutions}{May 17, 1994}

\bigskip

\vspace{2in}

\renewcommand{\arraystretch}{1.2}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
Problem&Points&Grade\\ \hline \hline
Initials & 4 & \\ \hline
1 & 15 & \\ \hline
2 & 18 & \\ \hline
3 & 15 & \\ \hline
4 & 20 & \\ \hline
5 & 17 & \\ \hline
6 & 20 & \\ \hline
7 & 17 & \\ \hline
8 & 20 & \\ \hline
9 & 17 & \\ \hline
10 & 17 & \\ \hline \hline
Total & 180 & \\ \hline
\end{tabular}
\end{center}
\renewcommand{\arraystretch}{1}

\bigskip
\bigskip
\noindent Name:\ \mbox{}\hrulefill\mbox{}\par

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\begin{problems}


% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \problem 
% %		The second part was too small to be its own problem...
% %		...or so I thought...
% %	\begin{problemparts}
% %	\problempart
% 
% Take an equilateral triangle, divide each side into $n$ equal segments
% and connect the division points with all possible segments that are parallel
% to the original sides.
% Find a formula in terms of $n$ for  the number of small triangles 
% that result, and prove that your formula holds.
% 
% For example, if $n=3$, there are 9 small triangles, as illustrated below.
% 
% \begin{figure}[htb]
% \setlength{\unitlength}{.5in}
% 
% \begin{picture}(3,3)(-5,0)
% 
% %	\thicklines
% \put(0,0){\line(1,0){3}}
% \put(1,0){\line(-3,5){.5}}
% \put(2,0){\line(-3,5){1}}
% \put(3,0){\line(-3,5){1.5}}
% \put(0,0){\line(3,5){1.5}}
% \put(1,0){\line(3,5){1}}
% \put(2,0){\line(3,5){.5}}
% \put(.5,.833){\line(1,0){2}}
% \put(1,1.667){\line(1,0){1}}
% 
% \end{picture}
% \end{figure}
% 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\problem \points{15}

Show that for all positive integers $m$ and $n$, there exist positive
integers $i \neq j$ such that $m$ evenly divides $n^i-n^j$.  (\hint
Pigeonhole principle.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vspace{2in}
\npage
\problem \points{18}

Circle {\bf T} or {\bf F} to answer true or false for each of the
following statements.  Wrong answers will be penalized, so do not
guess unless you are reasonably sure.

Let $f:A\rightarrow B$ and $g:B\rightarrow C$ and let
$p,r,s$ and $t$ be functions from $\nat$ to $\reals$.
Recall that $g\circ f$ is defined as $(g\circ f)(x) = g(f(x))$.
\bigskip
\begin{itemize}
\setlength\itemindent{.5in}
%	\setlength\itemsep{2in}
% \tfitem If $f$ maps $A$ onto $B$ and $g$ maps $B$ onto $C$,
% then $g\circ f$ maps $A$ onto~$C$.
\tfitem If $f$ and $g$ are both bijections, then so is $g\circ f$.
\tfitem If $g\circ f$ is a bijection, then so are $f$ and $g$.
% \tfitem 
%  If $p(n) \sim s(n)$ and $r(n) \sim t(n)$, then $p(n)r(n) \sim s(n)t(n)$.
% \tfitem If $p(n)=5$, then $p(n)=O(n^2)$.
\tfitem If $p(n) = \left\{ \begin{array}{ll}
 \frac{1}{100} + \frac{1}{101} + \frac{1}{102} + \cdots + \frac{1}{n} & 
 \mbox{ if $n\geq 100$} \\
 \rule{0pt}{15pt} 0 & \mbox{ if $n<100$}
			\end{array} \right. $ ,
	then $p(n)=\Omega(\lg n)$.
\tfitem  If $p(n)=o(t(n))$, then $e^{t(n)+p(n)} \sim e^{t(n)}$.
\tfitem  $\lg\sqrt{n}=o(\lg n)$.
% \tfitem  $\lg^2(\lg n)=o(\lg n)$.
\tfitem ${n \choose n/3} =\Omega \left( 2^n/\sqrt{n}\right)$.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem \points{15}

Prove by induction that the recurrence $T(n)=4T(n/5)+n$ has 
solution $T(n)= O(n)$. (Assume that $T(n)$ is constant for $n\leq 2$.)

\vspace{1in}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage\problem \points{20}

Consider the set $F$ of all functions from set $A$ to set $B$, where
$|A|=m$ and $|B|=n$.
That is, $F = \{ f \mid f:A\rightarrow B\}$.

\begin{problemparts}
\setlength\itemsep{.5in}
\problempart
What is the size of $F$?
\problempart
How many functions $f\in F$ are injective (one-to-one) if\ldots
	\begin{enumerate}
	\setlength\itemsep{.5in}
	\item \ldots $m < n$? 
	\item \ldots $m = n$? 
	\item \ldots $m > n$?
	\end{enumerate}
\newpage
\problempart
How many functions $f\in F$ are surjective (onto) if\ldots
	\begin{enumerate}
	\setlength\itemsep{.5in}
	\item \ldots $m < n$? 
	\item \ldots $m = n$? 
	\item \ldots $m > n = 2$?
	\end{enumerate}

\problempart
Assume now that $B=\{0,1\}$.
Suppose a function $f$ is chosen uniformly at random from~$F$.
What is the probability that $f$ maps exactly $n/2$ elements of $A$ to~$1$?
%	That is, what is Prob$[|f^{-1}(1)| = n/2]$?
Give an exact asymptotic ($\sim$) bound in terms of $n$.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\problem\points{17}

In the lottery game Keno, a participant selects 20 different numbers from 
the set $S=\{1,\ldots, 80\}$.  
To determine winners, the lottery randomly selects 10 different numbers from 
$S$, and anyone who selected those 10 numbers (among his or her 20 numbers)
wins.  

\begin{problemparts}
\setlength\itemsep{2in}
\problempart
What is the probability of winning Keno?
(You may leave factorials and powers in your answer.)

\problempart
The game Teno is the played in the same manner as Keno, except that 
the lottery selects 11 numbers instead of 10, and anyone who selects
10 of those 11 (from among his or her 20 numbers) wins.
What is the probability of winning Teno?
(You may leave factorials and powers in your answer.)

\problempart
By what factor, rounded to the closest integer, is the probability of
winning Teno greater than the probability of winning Keno?
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage
\problem \points{20}

At the carnival, there is a betting game played with 
three fair and (mutually) independent dice.
You may bet \$1 on any of the six values $\set{1,2,3,4,5,6}$, 
and you win $\$d$ (plus you get your original bet back) 
if your value matches $d$ of the dice.  For example, 
if you bet \$1 on number 3, and the three dice show two 3's and one 6,
you win~\$2.

Slow Joe thinks the game is fair since if he simultaneously 
bets \$1 on each of the 6 choices, and the dice come up $a,b,c$, 
he wins 3 bets plus \$3, for a total of \$6, which is what he wagered.  
Slow Joe figures that he does the same if some value comes up more than once.
\begin{problemparts}
\setlength\itemsep{1in}
\problempart
What is the probability that 
	\begin{enumerate}
	\setlength\itemsep{.5in}
	\item	All three dice have different values?
	\item   Two dice have the same value and the third die has a 
		different value?
	\item	All three dice have the same value?
	\end{enumerate}
\vspace*{-.5in}
\problempart
What is the expected return (net winnings) if you wager \$6, placing
\$1 on each of the six values?  Justify your answer.

\problempart
What is the expected return if you wager \$1 
on only one of the six values?
Justify your reasoning.
\vspace*{-.5in}
\problempart 
Set up this game so that it is fair by fixing the three prizes
$i_1, i_2, i_3$ so that if you match $d$ of the dice, you win~$\$i_d$ (plus
you get your your original \$1 bet back).
%	If you want to bet $\$k$ (on a single throw of the dice),
%	what strategy should you follow to maximize your return?
%	What is the expected return (net winnings) if you wager $\$k$?  
%     Does the answer to the last question depend on how you spread the $\$k$?
%	Why or why not?
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\problem \points{17}
Let $S$ be a sample space.
Say random variable $X:S\to \nat$ has distribution
\[
X = \left\{ \begin{array}{ll} 	2 & \mbox{with probability } 1/4,\\
				3 & \mbox{with probability } 1/4,\\
				5 & \mbox{with probability } 1/2;
	\end{array}
	\right.
\]
and random variable $Y:S\to\nat$ has distribution 
\[
Y = \left\{ \begin{array}{ll} 	1 & \mbox{with probability } 2/3,\\
				4 & \mbox{with probability } 1/3;
	\end{array}
	\right.
\]
where $X$ and $Y$ are independent.

Let random variable $Z:S\to \nat$ be given by $Z = \max (X,Y)$.
\bigskip
\begin{problemparts}
\setlength\itemsep{2.5in}
\problempart
What is the expected value of~$Z$?
\problempart
What is the variance of~$Z$?
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage

\problem \points{20}
Let $R$ be a random variable with distribution
$$\Prob[R=m]=\lambda^m/(m!e^\lambda)$$ for $m\in\nat$, where $\lambda$ is a 
positive constant.
Let $S_n=R_1+\cdots+R_n$ where $R_i$ are (mutually) independent identically  
distributed random variables with same distribution as~$R$.
\begin{problemparts}
\setlength\itemsep{1in}
\problempart
Show that the probability generating function for $R$ is
$G(x)=e^{\lambda (x-1)}$.  State any identities you use to derive
this formula.  

\problempart Use the generating function $G(x)$ to verify that $\sum_m
\Prob[R=m] = 1$.

\problempart
What is the probability generating function for $S_n$?

\problempart
What is $\Prob[S_n=m]$?  

\problempart
What is $\Ex[R]$?

\problempart
What is $\Ex[S]$?

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \npage\problem
% 
% Let $S$ be a sample space, and 
% let $R:S\rightarrow \reals$ be a random variable with $\Ex[R]=10$.
% \begin{problemparts}
% \setlength\itemsep{4in}
% 
% \problempart Give the tightest upper and lower bounds that you can for
% $\Prob[R\geq20]$.  That is, give the greatest $p\in\reals$ and the
% least $q\in\reals$ such that $p\leq \Prob[R\geq 20] \leq q$.
% 
% \problempart Suppose the standard deviation of $R$ is 2.  Give the
% tightest upper and lower bounds that you can for $\Prob[R\geq 20]$.
% 
% \problempart Suppose the kurtosis of $R$ is 16.  Give the tightest
% upper and lower bounds for $\Prob[R\geq 20]$.  Recall that the
% kurtosis of $R$ is defined as $\Ex[(R-\Ex[R])^4]$.
% 
% \end{problemparts}
% 
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\npage\problem\points{17}

Let $R_1,\ldots,R_n$ be (mutually) independent identically distributed 
random variables, and let each have the same distribution as random 
variable $R$.  
Let $V$ be a random variable (mutually independent of the $R_i$)
with range $\{1,\ldots, n\}$.   Let $Z=R_1+\cdots+R_V$.  

This setup corresponds to an experiment where we first select an integer $k$ 
according to the distribution of $V$ and then conduct $k$ independent trials 
of selecting a value for $R$ and summing the $k$ values.

Show that $\Ex(Z)=\Ex(R)\cdot \Ex(V)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vspace{1in}
\npage\problem \points{17}

Recall the Gambler's Ruin problem from lecture.  Assume the game is
fair---that is, $p=1/2$.  Suppose you have a goal of reaching $\$ T$.
Let $P_n$ be the probability that, starting with $\$n$, where $n\leq
T$, you reach your goal before going broke.  In lecture we showed that
$P_n = n/T$.

Suppose you start with $\$n$ and continue to play until you are broke.
Let random variable $M$ be the maximum number of dollars you ever
have.  Determine the expected value of~$M$.

\end{problems}
\end{document}
