\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{\ \ \ Quiz 1 Solutions \hfil Bruce Maggs \hfil Feb 23, 1997\ \ \ }

\vskip 0.1in
}}}


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

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

\wisdom{Repeat After Me.}{This part is to test your ability to study 
material that has been pre-digested and labeled as useful or
likely to appear on exams. If you do not do well on this section, your
study habits could use adjustment.}

\problem{1}{5}
{What is $6 + 12 + 18 + 24 + \cdots + (6\cdot n)$ (for any integer
$n > 0$)?}

\begin{eqnarray*}
6 + 12 + 18 + 24 + \cdots + (6\cdot n) & = & 6 (1 + 2 + 3 + 4 + \cdots + n) \\
& = & 6 {n (n+1) \over 2} \\
& = & 3 n (n+1)
\end{eqnarray*}

\problem{2}{5}
{
What is $1 + \frac{1}{3} + \frac{1}{3^2} + \frac{1}{3^3} +  \cdots $?
}

\begin{eqnarray*}
1 + \frac{1}{3} + \frac{1}{3^2} + \frac{1}{3^3} +  \cdots & = & {1 \over 1-1/3} \\
& = & {3 \over 2}
\end{eqnarray*}

\problem{3}{5}
{
How many ways are there to rearrange the letters in MISSISSIPPI?
}

Since the 11 letters of MISSISSIPPI consist of 4 S's, 4 I's, 2 P's, and
1 M, we get:
$${11 \choose 4;4;2;1} = {11! \over 4!4!2!1!}$$

\problem{4}{5}
{
How many subsets of $\{1,2,3,4,5,6,7,8,9\}$ are there?
}

The number of subsets of a 9-element set is $2^9$.

\problem{5}{5}
{
How many subsets of $\{1,2,3,4,5,6,7,8,9\}$ 
have an even number of elements?
}

The even-sized subsets can be placed in 1-to-1 onto correspondence
with the odd-sized subsets, by pairing each even-sized subset $S$ that
contains 1 with $S - \{1\}$, and each even-sized subset $T$ that omits
1 with $T \cup \{1\}$.  So exactly half of the subsets are even-sized,
$2^8$ in all.

\problem{6}{5}
{
Write down a formula for the number of ways to choose $m$ people from
a set of $n$, when the order of selection matters.
}

The standard formula is $P(n;m) = {n! \over (n-m)!}$. There are $n$
choices for the first person, $n-1$ for the second, $n-2$ for the
third, and so on down to $n-m+1$ for the m'th person.  A convenient
way to write the product $n(n-1) \cdots (n-m+1)$ is ${n! \over
(n-m)!}$

Another way to count the set is to choose the $m$ people regardless of
order (${n \choose m}$ ways), then order them ($m!$ ways).  This gives
the equivalent expression ${n \choose m}m!$.

% 7.  If a chicken and a half lays an egg and a half in a day and a
% half, how many eggs will three chickens lay in three days?


\wisdom{Reading Solutions.}{This section tests your ability to read the
homework solutions that we hand out.}

\problem{7}{10}
{What is the maximum number of days that the Traditional Marriage
Algorithm will take to terminate when there are $n$ boys and $n$
girls?  Remember that it will always take at least one day.}

As explained in the solutions to assignment 2, TMA takes at most $n^2
- 2n + 2$ days to terminate.

\problem{8}{10}
{
Prove that $f(x) = 2x - 1$ solves the following recurrence
relation: $f(x) = 2f(x/2) + 1$, $f(1) = 1$.
}

We can prove $f(x) = 2x - 1$ simply by showing that it satisfies the
recurrence equations.

\begin{eqnarray*}
f(x) & = & 2f(x/2) + 1 \\
     & = & 2(2(x/2)-1) + 1 \\
     & = & 2x - 2 + 1 \\
     & = & 2x - 1 \\ 
\\
f(1) & = & 2 \cdot 1 - 1 \\
     & = & 1
\end{eqnarray*}

\newpage

\wisdom{Basic Techniques.}{This part will test your ability to apply techniques
for which I have given explicit recipes. If you do not do well on this section,
your study habits could use adjustment.}

\problem{9}{10}
{
Give a closed-form solution to the following recurrence.  Show your
work.

\begin{eqnarray*}
f(n) & = & 8f(n-1) - 15f(n-2) \\
f(0) & = & 0 \\
f(1) & = & 4
\end{eqnarray*}
}

Assume that the solution of $f(n)$ is of the form $f(n) = \lambda^n$.
Substituting this into the recurrence equation gives:
\begin{eqnarray*}
\lambda^n = 8 \lambda^{n-1} - 15 \lambda^{n-2} \\
\lambda^{n-2} (\lambda^2 - 8 \lambda + 15) & = & 0\\
\lambda^{n-2} (\lambda - 5) (\lambda - 3) & = & 0
\end{eqnarray*}

Since the recurrence is linear, any solution of the form $f(n) = c_0
0^n + c_1 5^n + c_2 3^n$ will satisfy the equation.  The $c_0 0^n$
term is constant zero, so it can be omitted.  It remains to solve for
$c_1$ and $c_2$, using the base cases:
\begin{eqnarray*}
f(0) & = & c_1 5^0 + c_2 3^0 \\ 
0 & = & c_1 + c_2 \\
\\
f(1) & = & c_1 5^1 + c_2 3^1 \\ 
4 & = & 5c_1 + 3c_2 \\
\end{eqnarray*}

Solving this system of equations gives $c_1 = 2$ and $c_2 = -2$, so the final answer is
$$f(n) = 2 \cdot 5^n - 2 \cdot 3^n$$


\newpage

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


\problem{10}{5}
{Show how to compute $11^4$ using the binomial theorem.}

The binomial theorem states that $(x+y)^n = \sum_{k=0}^n {n \choose k} x^k y^{n-k}$.

We could apply the theorem using any $x,y$ such that $x+y = 11$, but
the simplest choice for computation seems to be $10+1=11$.  Thus:
\begin{eqnarray*}
11^4 & = & (10 + 1)^4 \\
     & = & \sum_{k=0}^4 {4 \choose k} 10^k 1^{4-k} \\
     & = & {4 \choose 0} 10^0 + {4 \choose 1} 10^1 + {4 \choose 2} 10^2 + {4 \choose 3} 10^3 + {4 \choose 4} 10^4 \\
     & = & {4! \over {0!4!}} \cdot 1 + {4! \over {1!3!}} \cdot 10 
           + {4! \over {2!2!}} \cdot 100 + {4! \over {3!1!}} \cdot 1000
           + {4! \over {4!0!}} \cdot 10000 \\
     & = & 1 + 40 + 600 + 4000 + 10000 \\
     & = & 14641
\end{eqnarray*}

\problem{11}{10}
{
Prove that $\{2^i\}$, where $i$ is any integer, is a group with respect
to multiplication.
}

To show that this set is a group under multiplication, we need to
prove the four group properties:

\begin{itemize}
\item[Closure:]
For any two elements $2^i$ and $2^j$, their product $2^i
\cdot 2^j = 2^{i+j}$ is also a member of the set, so the set is
closed.   

\item[Associativity:]
For any three elements $2^i$, $2^j$, and $2^k$, we have $(2^i \cdot
2^j) \cdot 2^k = 2^i \cdot (2^j \cdot 2^k)$ because multiplication is
associative.  (Some people confused associativity with commutativity,
and proved that $2^i \cdot 2^j = 2^j \cdot 2^i$.  Commutativity is not
necessary for a group.)

\item[Identity:]
There exists an identity element $2^0 = 1$ such that for any element
$2^i$, $2^0 \cdot 2^i = 2^i \cdot 2^0 = 2^i$.

\item[Identity:]
For any element $2^i$, there exists an inverse $2^{-i}$ such that $2^i
\cdot 2^{-i} = 2^{-i} \cdot 2^i = 2^0$.
\end{itemize}

\problem{12}{10}
{6 college suitemates order three pizzas, each with 12 slices. 
If each student must eat an even number of slices, how many ways
are there to allocate the pizza slices to the students?}

This is an example of the pirates and gold bars problem: we have $n$
identical objects (here, slices of pizza) to be divided among $k$
people.  To deal with the constraint that each student must eat an
even number of slices, we can allocate the pizza slices in pairs.
There are 18 pairs of slices and 6 people, so the answer is
$${18 + 6 - 1 \choose 6 - 1} = {23 \choose 5}$$

\problem{13}{15}
{Suppose that in the city walk problem, you now have the option of
going diagonally through any city block, instead of going north
or east.  How many paths are there from the origin ($0$th St.\ and
$0$th Avenue) to your home at $y$'th St.\ and $x$'th Avenue?  You may
leave your answer as a summation.
}

Recall how we solved this problem when only north and east moves were
allowed (no diagonals).  In that case, each path was $x+y$ blocks
long, corresponding to some arrangement of north and east moves.  In
other words, it was the number of ways to arrange a word with $x$ E's
and $y$ N's, or ${x+y \choose x} = {(x+y)! \over x!y!}$.

Now let's consider using diagonal moves.  Each path corresponds to
some arrangement of E's, N's, and D's, but the number of each kind of
move depends on how many D moves are taken.  

Let's first count the number of paths that make exactly $d$ diagonal
moves.  A path with $d$ diagonal moves must make exactly $x-d$ east
moves and $y-d$ north moves.  Thus each path with $d$ diagonal moves
corresponds to some arrangement of $x-d$ E's, $y-d$ N's and $d$ D's,
giving a total of ${(x+y-d)! \over (x-d)!(y-d)!d!}$ such paths.

Using the sum rule, we can add the paths with 0 diagonal moves, 1
diagonal move, and so forth, up to $\min(x,y)$, which is the maximum
number of diagonal moves possible.  So the answer is the sum:
$$\sum_{d=0}^{d=\min(x,y)} {(x+y-d)! \over (x-d)!(y-d)!d!}$$

\end{document}


