\documentstyle[12pt,macpsfig,amssymb,xspace]{article}
\input{/a/class/6.042/fall94/handouts/macros-course}

	\addtolength{\topmargin}{-.2in}
	\setlength{\textheight}{8.5in}

\setcounter{page}{0}

\renewcommand{\bar}{\overline}

%\newcommand{\pr}{\problem}
\newcommand{\pr}{\newpage\problem}
\renewcommand{\bparts}{\begin{testproblemparts}}
\renewcommand{\eparts}{\end{testproblemparts}}

\newcommand\tfitem{\item [{\bf T / F \hspace*{.1in} }]}
%\renewcommand{\theproblem}{Problem \arabic{problemnum}}

%%	Keith:
%%	We can use these macros for probality, expectation, variance.
%%	

\newcommand\Ex[1]{\mbox{Ex}[\, #1 \, ]}
\newcommand\vari[1]{\mbox{Var}(\, #1 \,)}
\newcommand\Prob[1]{\mbox{Prob}[\, #1 \, ]}


\begin{document}

\examinitials{Final Exam}{December 20, 1994}


\begin{closeitemize}

\item Put your name on the top of each page.

%	\item The exam ends at noon. It contains 12 problems on
%	pages numbered 1 through~?????.
%	You have 180 minutes to earn 180 points.

\item This quiz is closed book.  You may use two $8\frac{1}{2}''\times 11''$ 
handwritten crib sheets.  You may {\bf not} use a calculator.

\item Write your solutions in the space provided.  If you need more
space, write on the back of the sheet containing the problem.  
%	Please do not
%	put part of the answer to one problem on the back of the sheet for
%	another problem.

%	\item Do not spend too much time on any problem.  Read them all
%	through first and work them in the order that allows you to make the
%	most progress.

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

\end{closeitemize}

\medskip

\renewcommand{\arraystretch}{.5}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
& &\hspace*{1in}\\
Problem&Points&Grade\\
& &\\
\hline
\hline
& &\\
1  & 15 & \\ & &\\ \hline	& &\\
2  & 15 & \\& &\\\hline& &\\
3  & 15 & \\& &\\\hline& &\\
4  & 15 & \\& &\\\hline& &\\
5  & 15 & \\& &\\\hline& &\\
6  & 15 & \\& &\\\hline& &\\
7  & 15 & \\& &\\\hline& &\\
8  & 15 & \\& &\\\hline& &\\
9  & 15 & \\& &\\\hline& &\\
10 & 15 & \\& &\\\hline& &\\
11 & 15 & \\& &\\\hline& &\\
12 & 15 & \\& &\\
\hline
\hline
& &\\
Total & 180 & \\
& &\\
\hline
\end{tabular}
\end{center}
\renewcommand{\arraystretch}{1}
\bigskip
\bigskip
\bigskip

\noindent Name:\ \mbox{}\hrulefill\mbox{}\par
\bigskip \bigskip
\noindent Please circle your TA's name: 
 \hspace{.5in} Andrew 
 \hspace{.5in} David
 \hspace{.5in} Keith
 \hspace{.5in} Victor

\newpage
\begin{problems}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr
\points{15}

\bparts
\ppart
\setlength{\itemsep}{3.5in}
Let $G=(V,E)$ be a directed graph in which each vertex has out-degree at 
least~$1$.
Prove by induction that 
$G$ contains a directed path of length~$m$ for all $m\in\nats$.
\ppart
Use the pigeonhole principle to prove that
if directed graph
$G=(V,E)$ has a path with $|V|$ edges, then $G$ contains a cycle.
\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr
\points{15}
For each of the following statements, 
(1) circle {\bf T} or {\bf F}  to indicate whether the statement is 
true or false, respectively, and 
(2) justify your answer succinctly.
The justification counts for more points than does the correct 
{\bf T}/{\bf F} answer.
A formal proof is not necessary, but you should be able to write a
one- or two-sentence explanation or picture that conveys the essential idea.

\begin{list}{{\bf T\ \ F\ \ \ }}{\setlength{\leftmargin}{40pt}%
	\setlength{\labelwidth}{\leftmargin}%
	\setlength{\itemsep}{1.3in}%
	\addtolength{\labelwidth}{-\labelsep}
}

%\item  $\forall X\subseteq \reals$, if $X$ is uncountable, 
%	then $\reals - X$ is countable.

\item  $f(x)= x^3+x$ is a bijection from $\reals$ to $\reals$.

\item  $f(x)= x^3-x$ is a bijection from $\reals$ to $\reals$.

\item  $\forall a,b,c\in\nats$, if $a\divides c$ and $b\divides c$, 
	then $ab \divides c$.

\item  $\forall a,b\in\nats$, we have $\gcd(7a+2b,3a+b) = \gcd(a,b)$.

%\item  $\forall a,b\in\nats$, we have $\gcd(7a+3b,3a+b) = \gcd(a,b)$.
%\item  For all positive integers $n$, we have $n$ divides $2n \choose n$.
%\item  For all finite sets $A$ and $B$, if $A$ is a proper subset of~$B$, 
%	then there is no bijection between $A$ and~$B$.  

\item  For all countably infinite sets $A$ and $B$, 
	if $A$ is a proper subset of~$B$,
	then there is no bijection between $A$ and~$B$.  

\end{list}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr
\points{15}

For each of the following pairs of functions $f(n)$ and $g(n)$, fill
in the blank with $o$, $O$, $\omega$, $\Omega$, and $\Theta$ depending 
depending on
whether $f(n)=o(g(n))$, $f(n)=O(g(n))$, $f(n)=\omega(g(n))$,
$f(n)=\Omega(g(n))$, or $f(n)=\Theta(g(n))$.
If there is more than one relation between $f(n)$ and $g(n)$, write
the strongest one.  
Suboptimal answers will get partial credit but
incorrect answers will be penalized, 
so do not guess unless you are reasonably sure.
As usual, $\lg n$ denotes logarithm to the base~2.
The first line is an example solution.

\def\blank{\rule[-2pt]{.5in}{.5pt}}
\[
\renewcommand{\arraystretch}{4}		%make it 4 later.
\begin{array}{rcl}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8^{\lg n} 	& = & \blank  (n^3)\\  %%  EXAMPLE  %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
n! 		& = & \blank (6^n) \\
2^{(\lg^3 n)} 	& = & \blank (n^4) \\
	\makebox[0in][r]{(for any constant $k$,) }
{n\choose k}	& = & \blank  (n^k) \\
%%	(\lg n / \lg\lg n)!& = & \blank & (n^2\lg n)
\displaystyle \sum_{i=1}^n  \frac{1}{i}
		& = & \blank (1)  \\
\displaystyle \sum_{i=n}^\infty \frac{1}{i^2}
		& = & \blank (1) 
\end{array}
\]



\remove{
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \pr
  \points{15}

  In an $\nats^+$-weighted undirected graph, each
  edge is assigned a positive integer weight.  
  The \defi{weighted-degree} of a node is the sum
  of the weights of its incident edges.

  Consider the following set of weighted degrees:
  $1, 3, 5, 7, \ldots, 2n-1$.

  \bparts 
  \ppart Show that if $n$ is odd, then no graph on $n$ nodes has 
  this set of weighted-degrees.

  \ppart Show that if $n>2$ is even, then there exists a graph on $n$ nodes
  with this set of weighted-degrees.\\
  Do this by constructing such a graph for each even~$n>2$.
  You may do this inductively, by constructing a graph for $n+2$
  from the graph already constructed for~$n$.  (Don't forget the base case.)

  \eparts 
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr
\points{15}

Let 
\[
T(n)= T(\lfloor 9n/10\rfloor)+n
\]
for all positive integers $n$, and let $T(0)=0$.
Prove by induction that $T(n)=O(n)$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr
\points{15}
There are $k$ (distinguishable) students taking an exam who must be seated 
in a row of $n$ seats so that no two students 
are seated next to each other.
How many ways can the students be seated?


\remove{
  There are 75 students in 6.042/18.062 taking an exam in a room that has 
  11 rows of seats, and 13 seats in each row.
  For certain reasons, 
  %	n order to ensure 
  %	that the random variables in the next problem are independent, 
  we insist that no two students in the same row sit next to each other.

  \bparts
  \ppart
  How many ways can 6 {\em indistinguishable} students be seated in a row?
  5 students?
  \ppart
  Two seatings are {\em row-equivalent} if in each row 
  the two seatings have the same number of students.
  %	there is some row
  %	in which the seatings put a different number of students.
  %	For example, one seating may put 7 students in each of the first 
  %	ten rows and 4 students in the last row;
  %	a row-inequivalent seating 
  How many row-inequivalent seatings are there?
  (You may leave factorials in your answer.)
  \ppart
  How many ways can the 74 (distinguishable) students be seated?  
  (You may leave factorials in your answer.)
  \eparts
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr
\points{15}

Assume that the annual inflation rate is forever fixed at $p= 5\%$.
Suppose Marilyn offers to pay Bobo $\$1000n$ dollars at the end of year $n$ for
every $n\geq 1$.  
So, at the end of year~1, Bobo gets $\$1000$;
at the end of year 2, Bobo gets another $\$2000$, 
at the end of year 3, Bobo gets another $\$3000$, and so on, forever.
In return, Marilyn wants an up front payment of $\$1,000,000$.  
Bobo figures this is a good deal since he (or his descendants) 
will be making an infinite amount of money in the future.  
Is Bobo right about it being a good deal?  
What is the present value of all future payments?  
You should not need a calculator to compute the exact answer.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr
\points{15}
Actually, the lottery game Keno$^{\sc r}$ is played in the following manner:
The participant bets \$1 and 
picks from 1 to 12 numbers from $\set{1,\ldots, 80}$.
The lottery picks 20 different numbers from $\set{1,\ldots, 80}$, 
randomly and uniformly among all subsets of size~20.

The ``$k$-spot game'' is when the participant's set has $k$ numbers.
The participant's winnings depend on how many numbers he or she chose and 
how many of them are in the lottery's set.

\bparts
\ppart
The $1$-spot game pays \$2.50 if the number chosen is among 
the lottery's set of~20.
Is the $1$-spot game fair?   Justify your answer by computing 
the expected return (recall that you pay \$1 to play).
\ppart
What is the probability of matching exactly 1 number in the 2-spot game?\\
(You may leave factorials in your answer.)
\ppart
What is the probability of matching all 12 numbers in the 12-spot game?
\eparts



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr
\points{15}

Observe that
\begin{eqnarray*}
1 & = & 1 \\
4 & = & 1 + 3 \\
9 & = & 1 + 3 + 5 \\
16 & = & 1 + 3 + 5 + 7 \\
25 & = & 1 + 3 + 5 + 7 + 9
\end{eqnarray*}
Use generating functions to derive and prove a general formula.
For this problem, you {\em must\/} use generating functions.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr
\points{15}

The winner of a playoff series is the first team to win 2 games.
Suppose the two teams are equally likely to win the first game, 
but thereafter, a team wins with probability $2/3$ if it won the 
preceding game.

\bparts

\ppart  What is the probability that a third game will be needed before
a winner is determined?

\ppart  What is the expected number of games to be played, assuming
that they will stop as soon as one team has won $2$ games?

\ppart  What is the probability that the winner of the series
won the first game?

\eparts



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr
\points{15}

Let $R_1$ and $R_2$ be two independent outcomes of a fair 6-sided die.
\bparts
\ppart
What is $\Ex{R_1^2 R_2}$?  
\ppart
What is $\Ex{2^{R_1}}$?  
\ppart
What is $\vari{R_1+R_2}$?
\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr
\points{15}

The prosecution at OJ's trial is attempting to tie OJ to the
crime by a new analysis of {\em blood thickness}.  
Blood thickness is expressed as a natural number.  
The average blood thickness over all humans is~100.  
OJ has very thick blood: its thickness is~150.  

\bparts
\ppart
Knowing only the average thickness, 
what bounds (upper and lower) can you prove on the fraction of humans
that can have blood thickness~150?  
\ppart
At the trial, the prosecution reveals that the standard deviation of 
blood thickness is~5.  It is further revealed that the blood found at 
the scene of the crime has thickness~150.  
Using Chebyshev's theorem, what can you say about the
fraction of humans that might have commited the crime?  
\eparts



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\pentium}{Pentium$^{\sc r}$\xspace}
\pr
\points{15}

A \pentium chip has 1000 components.
Past experience with Intel engineers indicates that 
300 of these components fail with probability $1/15$,
300 fail with probability $1/10$, 
and 400 fail with probability $1/8$.
Assume that all component failures are independent.
\bparts
\setlength{\itemsep}{3.5in}	
\ppart
What is the expected number of components that will fail on a \pentium chip?
\ppart
Derive a formula for the exact probability that a \pentium chip has 
no failures.
\ppart
Derive an upper bound of the form $e^{-x}$, where $x$ is an integer,
on the probability that a \pentium chip has no failures.
\ppart
Using Chernoff's bound, 
derive an upper bound of the same form 
on the probability that 272 or more components
fail on \pentium chip.
\eparts



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



\end{problems}

\end{document}
