\documentstyle[12pt,macpsfig,amssymb]{article}
\input{macros-course}

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

\newcommand{\pr}{\problem}

\begin{document}

\handout{final95}{Practice Problems}{November 26, 1996}
\center{(Final Examination, Fall 1995)}

\begin{problems}

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

\pr
Prove {\bf using induction} that the sum of the cubes of three consecutive
positive integers is divisible by $9$.


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

\pr  
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{itemize}
\item 
$\forall X\subseteq \reals$, if $X$ is uncountable, then $\reals - X$
       is countable.

\item  
$f(x)= |x|$ is an injection from $\reals$ to $\reals$.

\item  
$f(x)= x^{1995}$ is a surjection from $\reals$ to $\reals$.

\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 
Let $a_n$ be the probability that you pick the maximum on picking a
number uniformly at random from an array of $n$ distinct
numbers. Assume $a_0 = 0$. Then the OGF for $a_n$ is $x/(1-x)^2$.

\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr  
Short answer questions. Justify your answer succinctly.
\bparts 
\ppart
What is the coefficient of $x^3$ in the binomial expansion of
$(1-x)^{-\frac12}$?.

\ppart
Evaluate the sum
\[ {\displaystyle \sum_{i=0}^\infty \sum_{j=0}^\infty x^{i-j}y^{i+j} } \]

\ppart
Find the number of three letter words over the alphabet a,b,\ldots,z that do not contain ``ab'' or ``ba''.

\eparts

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

\pr  
Let $A$ and $B$ be two equivalence relations on the set $S =
\{1,2,\ldots, n\}$.  Prove that $A\bigcap B$ is an equivalence
relation too. (Recall that a relation on a set $S$ is a subset of $S\times S$.)


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

\pr  
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 
 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.  
As usual, $\lg n$ denotes logarithm to the base~2. Each part is worth 2 points.

\def\blank{\rule[-2pt]{.5in}{.5pt}}
\[
%\renewcommand{\arraystrech}{4}         %make it 4 later.
\begin{array}{rcl}
 10^{\lg n}       & = & \blank  (n^{\lg 10})\\
 (n!)^2              & = & \blank (n^n) \\
  2^{(\lg^3 n)}   & = & \blank (n^{4\lg\lg n}) \\
  
{n\choose k}    & = & \blank  (n^k) ~~~~~~\mbox{for any constant $k$}\\
 \displaystyle \sum_{i=1}^n \frac{1}{i^5}
                & = & \blank (1) 
\end{array}
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr  
\bparts
\ppart
Let
\[ T(n) = 2T(\lfloor n/4\rfloor) + T(\lfloor n/3\rfloor) + 2n \] for all positive integers $n$ and let $T(0) = 0$. Prove {\bf by induction} that $T(n) = O(n)$.
\ppart
Solve
\[ T(n) = 5T(n-1) - 4T(n-2) \] for all $n \geq 2$. $T(0) = 3$ and $T(1) = 6$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr  
\bparts
\ppart
How many ways can you arrange $39$ identical black balls and $13$
identical white balls in a row, so that no two white balls are
adjacent?
\ppart
A standard deck of $52$ cards is shuffled completely (i.e. any of the
permutations are equally likely.)  What is the {\bf probability} that
no two spades are adjacent in the shuffled deck?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pr  
A pitcher's record is $21$ wins and $4$ losses. {\bf Prove} that he must
have enjoyed a winning streak of $5$ games.

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

\pr  
$10\%$ of the theorems in the lecture notes contain typos. For any
   theorem, it is the case that if you ask a TA whether it has a typo
   the probability that her answer is correct is $0.8$.
\bparts
\ppart 
Given a theorem selected uniformly at random, if a TA tells you that
it has a typo, what is the probability that it does?
\ppart 
Suppose TAs answer independently from each other. 
If $2$ TAs tell you a theorem has a typo, what is the probability that it does?
\eparts

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


\pr  
An integer $X$ is drawn from the set $1,2,\ldots,n$ uniformly at random. 
\bparts
\ppart 
Prove that the probability that $X$ is divisible by $k$ is $(1/n)(\lfloor
n/k\rfloor)$.
\ppart
Prove that the expected number of divisors of $X$ is $\Theta(\log_e n)$
\eparts

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


\pr  
\bparts
\ppart 
Let $G$ be a graph with $E$ edges.  If each vertex
is colored red or blue independently with equal probability then what is
the expected number of edges with differently colored endpoints.
\ppart 
Let $N(i,j), 1\leq i, j \leq n$ represent the number of times 
person $i$ calls person $j$, per month.  Calls within an area code
cost $L$, and calls between area codes cost $D$.  If the phone company
randomly assigns each person to one of $k$ area codes, then what is
its expected monthly revenue?
\eparts

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

\pr 
$100$ students take an exam. The total number of points for the exam is $207$. 
\bparts
\ppart
If the mean on the exam is $60$ then what is a nontrivial upper bound
on the number of students who scored {\bf more than} $120$?
\ppart
If the mean on the exam is $60$ and the variance is $72$ then what is
the best upper bound you can give on the number of students who scored
{\bf more than} $120$?

\eparts

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

\pr 
An exam has $100$ true/false questions and $100$ multiple choice questions. Each true/false question is worth $1$
point while each multiple choice question is worth $2$ points. The maximum score is $300$. There is a student who 
answers at random. She is correct with probability $1/2$ on each true/false question and with probability $1/4$ on each multiple choice question.
\bparts
\ppart
What is the expected score of the student?
\ppart 
What is the standard deviation of the student's score?
\ppart
What is the best upper bound you can give on the probability that the
student scores more than $272$ points?

\eparts

 \end{problems}
\end{document}
