\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 Solutions \hfil Steven Rudich \hfil May 9, 1997\ \ \ }

\vskip 0.1in
}}}

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

\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$.
}

\[n! \over k! (n-k)!\]



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

A tree is a connected graph with no cycles.



\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.)
}

This question is equivalent to a problem we studied in Lecture 25: any
2-coloring of the edges of a complete graph on 6 nodes will contain a
monochromatic triangle.

Proof: let $v$ be an arbitrary node in the complete graph.  $v$ has 5
neighbors; by the pigeonhole principle, at least 3 of them are
connected to $v$ by edges of the same color (call it blue).  If two of
the 3 neighbors are connected by a blue edge, it forms a blue
triangle.  If not, then the 3 neighbors themselves form a triangle of
the opposite color.  QED.





\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.}

The $i$th level of the ternary tree contains $3^i$ nodes, so a tree
with levels $0, 1, \ldots, n-1$ has 
\begin{eqnarray*}
\sum_{i=0}^{n-1} 3^i & = & {3^n - 1 \over 3-1} \\
& = & {3^n - 1 \over 2}
\end{eqnarray*}



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

By Little Gauss' formula, $1 + 2 + 3 + \cdots + n = {n(n+1) \over 2}$.
This number is divisible by $n$ if and only if $n+1 \over 2$ is an
integer, which is true if and only if $n+1$ is even, which is true 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$.
}

Applying the method of linear recurrence relations, we let $f(x) =
\lambda^x$ and solve for $\lambda$:
\[\lambda^x = \lambda^{x-1} + 2 \lambda^{x-2}\]
Dividing through by $\lambda^{x-2}$ gives
\begin{eqnarray*}
\lambda^2 = \lambda + 2 \\
\lambda^2 - \lambda - 2 = 0 \\
(\lambda + 1) (\lambda - 2) = 0
\end{eqnarray*}

This gives two possible solutions, $\lambda_1 = -1$ and $\lambda_2 =
2$.  The solution is some linear combination of these two solutions,
$f(x) = a(-1)^x + b2^x$.  To find $a$ and $b$, substitute the base cases:
\begin{eqnarray*}
f(0) = a + b = 2 \\
f(1) = 2a - b = 1 \\
\end{eqnarray*}

Solving gives $a=1$ and $b=1$.  Thus the closed form solution for $f$ is
\[f(x) = (-1)^x + 2^x\]



\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}\]
}

Use the binomial theorem, 
\[(x+y)^n = \sum_{k=0}^{n} {n \choose k} x^k y^{n-k}\]

With $x=3$ and $y=-1$, we get
\[2^n\]



\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$.}

By the pigeonhole principle, at least two of the $m$ integers must be
congruent modulo $m-1$ -- so $x_i = x_j \pmod{m-1}$ for some $i \neq
j$.  Thus $x_i - x_j = 0 \pmod{m-1}$, so $x_i - x_j$ 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?)
}

Define the random variable $X_i$ as follows: $X_i=i$ if $i$ is in the
chosen subset; otherwise $X_i=0$.  Thus $S = X_1 + X_2 + \cdots +
X_{20}$.  By linearity of expectation, $E[S] = E[X_1] + E[X_2] + \cdots
+ E[X_{20}]$.  Since each $i$ is equally likely to be in the set as not,
$E[X_i] = {i \over 2}$.  Thus
\begin{eqnarray*}
E[S] & = & \sum_{i=1}^{20} {i \over 2} \\
& = & {1 \over 2} \sum_{i=1}^{20} i \\
& = & {1 \over 2} {20 \cdot 21 \over 2} \\
& = & 105
\end{eqnarray*}


\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.}

Let us count the ways by assigning elements of the set to the {\em
difference sets}: $A_0, A_1-A_0, A_2-A_1, \ldots, A_n-A_{n-1}$.  We'll
also allow some elements to be assigned to a set $X$ (the trash can),
meaning that they aren't used.  

Because the subsets must be distinct, each of the difference sets
$A_1-A_0, \ldots, A_n-A_{n-1}$ must contain at least one element.
Since there are $n$ such difference sets and only $n$ elements, each
difference set must contain exactly one element, and $A_0$ and $X$
(the leftovers) must be empty sets.  So the number of ways to choose
the subsets is just the number of permutations of $n$ elements, \[n!\]



\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.}

Use the same setup as the previous problem: let us count the number of
ways to assigning elements to $A_0, A_1-A_0, A_2-A_1, \ldots,
A_n-A_{n-1},$ and $X$ (the trash can).  Now, however, there are no
constraints, so each of the $n$ elements can choose any of the $n+2$
sets, which gives \[(n+2)^n\]



\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$?}


Let $x_1, x_2, x_3$ be the values of the three spins.  Assuming the dial is
``fair,'' the probability that of seeing a sum of $n$ is is the number of
solutions to $x_1+x_2+x_3=n$ (subject to $x_i\ge 1$), divided by the total
number of results.

Using a ``pirates and gold bars'' approach, there are ${{n-1} \choose {n-3}}$
solutions to $x+y+z=n$ subject to $x\ge 1, y\ge 1, z\ge 1$. So the answer is
$$\frac{{{n-1} \choose {n-3}}}{n^3}$$



\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)$.
}

The polynomial we're looking for has the form $y = ax^2 +bx+c$. We have
three unknowns $a,b,c$, and the three points given. Substituting for $(x,y)$:

\def\mod{{~~\mbox{mod}~~}}
\begin{itemize}
\item $6=a+b+c \mod 7$
\item $4=4a+2b+c \mod 7$
\item $4=2a+3b+c \mod 7$
\end{itemize}
Solving this system equations (with all arithmetic done modulo $7$) gives
$a=1; b=2; c=3$ or $y=x^2+2x+3$. 



\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.}

\centerline{\psfig{figure=final-eulerian-graph.eps,height=1.0in,width=4.0in}}


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

We will make use of the fact that in a connected graph, $E\ge V + 1$, where $E$
is the number of edges and $V$ is the number of vertices.

Assume by way of contradiction that the graph has $j<k$ components. Say
component $i$ has $V_i$ vertices, in which case (by the above) it has at least
$V_i-1$ edges. So the total number of edges in the graph is $\sum_{i=1}^j V_i
-1 = n - j$. But it is given that there are $n-k$ edges in the graph, so we
have arrived at a contradiction.

\end{document}


