\documentstyle[12pt,psfig]{cmu-art}
%\setlength{\textwidth}{6.50in}
%\addtolength{\oddsidemargin}{-0.75in}
%\addtolength{\evensidemargin}{-0.75in}
%\topmargin -1in
\begin{document}
\centerline{\psfig{figure=tpi.eps,height=1.0in,width=4.0in}}
{\large
\fbox{\parbox{6.1in}{
\hbox to \hsize{\ \ \ Final Exam \hfil Steven Rudich \hfil May 9, 1997\ \ \ }

\vskip 0.1in
}}}

\newcommand{\problem}[3]{\noindent {\bf #1}. [#2 points] \\ #3}

\newcommand{\wisdom}[2]{\begin{quotation}
 \begin{center} \bf #1 \end{center} #2 \end{quotation} }

\wisdom{Repeat After Me.}{This part is to test your ability to study 
material and repeat it.
}

\problem{1}{2}
{
Give a formula for $n$ choose $k$.
}



\problem{3}{3}
{
Give the definition of a tree.
}


\problem{3}{5}
{Show that at any party with six people there are either three mutual acquaintances or
three mutual strangers. (You may assume that any two people are either acquaintances
or strangers.)
}





\wisdom{Basic Techniques.}{This part will test your ability to reason with some
of the basic techniques learned in the class. 
}

\problem{4}{5}
{Every node of a ternary tree has $3$ children (except for the leaf
nodes, which have no children).  If a one-level ternary tree contains
1 node, how many nodes does an $n$-level ternary tree have? Your
solution must be in closed form. I.e., no summation in the exression
that gives the solution.}


\problem{5}{5}
{Prove that $1 + 2 + 3 + \cdots + n$ is divisible by $n$ if and only
if $n$ is odd.}


\problem{6}{10}
{$f(0) =2,$ $f(1) = 1$, for $x>1,\  f(x) = f(x-1) + 2 f(x-2)$. Give a closed
form solution for $f$.
}


\wisdom{A Moment's Thought!}{This section tests your ability to think a little
bit more insightfully. You must give complete explanations of your answers.
{\bf Do seven of the eight problems. Do not do all eight; if you do we will
grade seven of our choice.} }

\problem{7}{10}
{
Give a closed-form solution to \[\sum_{k=0}^{n} {n \choose k} 3^k (-1)^{n-k}\]
}


\problem{8}{10}
{Let $x_1, x_2, \ldots, x_m$ be any $m$ integers.  Prove that there
must exist a pair whose difference is divisible by $m-1$.}




\problem{9}{10}
{
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?)
}


\problem{10}{10}
{
Count the number of ways to choose distinct subsets $A_0$, $A_1$, $A_2, \ldots, A_n$ of
$\{ \ 1, 2, 3, \ldots , n \ \}$ such that $A_0 \subset A_1 \subset A_2 \subset \cdots
\subset A_n$. ($A \subset B$ means that $A$ is a subset of $B$.) Your solution
should be inclosed form if possible.}


\problem{11}{10}
{Count the number of ways to choose subsets $A_0$, $A_1$, $A_2, \ldots, A_n$ of
$\{ \ 1, 2, 3, \ldots , n \ \}$ such that $A_0 \subset A_1 \subset A_2 \subset \cdots
\subset A_n$. The subsets are {\em not} required to be distinct. Your solution
should be in closed form if possible.}


\problem{12}{10}
{Consider a dial that is equally likely to point to each of $n$ regions numbered
$1, 2, \ldots, n$. When we spin the dial three times what is the probability that
the sum of the selected numbers is $n$?}


\problem{13}{10} 
{Let $F$ be the field of integers modulo $7$. Find the degree two, univariate
polynomial over $F$ passing through the points $(1,6)$, $(2,4)$ and $(3,4)$.
}


\problem{14}{10}
{Find a simple, Eulerian graph with an even number of vertices and an
odd number of edges. Recall that a simple graph has no self loops or multiple
edges. An Eulerian graph is a graph with an Euler tour.}


\problem{15}{10}
{Prove that every graph with $n$ vertices and $n-k$ edges has at least $k$
components.}



\end{document}


