\documentstyle[psfig,11pt]{article}


\newcounter{problem}

\newenvironment{problems}{\begin{enumerate}\setcounter{enumi}{\theproblem}}{\setcounter{problem}{\theenumi}\end{enumerate}}
%\newenvironment{problems}{\begin{enumerate}}{\end{enumerate}}

\pagestyle{empty}

\textheight 9.4in
\addtolength{\oddsidemargin}{-0.7in}
\addtolength{\textwidth}{1.2in}
\topmargin -0.3in
\headheight 0.1in
\headsep 0.1in

\begin{document}
{\large
\fbox{\parbox{6.1in}{
\hbox to \hsize{\ \ \ 10 Powerful Ideas  \hfil 
Bruce Maggs}
\vskip 0.1in
\hbox to \hsize{\ \ \ Quiz 1 Review Exercises \hfil Quiz 1: {\bf Monday, February 23, 1998}}
}}}
\vskip 0.1in

% magic for a Postscript figure:
%
%\begin{figure}[h]
%\centerline{\psfig{file=,width=}}
%\caption{}
%\end{figure}
 

% Topics
% - induction
% - asymptotic complexity: $O$, $\omega$, $\theta$
% - Fibonacci numbers and the golden ratio $\Phi$
% - recurrence relations
% - groups
% - counting

Solutions to these problems will be available on the course Web site
by Saturday.

\section*{Dating}

\begin{problems}

\item
{\small \it Show a set of bisexual dating preferences where there is no possible stable
pairing among the people.
}

Straight from Lecture 2:

\begin{center}
\begin{tabular}{ll}
{\bf person} & {\bf preference list}\\
\hline
$1$ & $2, 3, 4$\\
$2$ & $3, 1, 4$\\
$3$ & $1, 2, 4$\\
$4$ & {\em doesn't matter}
\end{tabular}
\end{center}


\end{problems}


\section*{Induction}

\begin{problems}
\item {\small \it Show {\bf by induction} that for all
integer $n\geq 1$, $\phi^n = F_n \phi + F_{n-1}$,
where $\phi$ is the golden ratio and $F_n$ is the $n$th Fibonacci
number.
}

{\bf Base case}.  $n=1$.  $\phi = F_1 \phi + F_0 = 1 \phi + 0 =
\phi$.

{\bf Inductive step}.  Assume $\phi^{n} = F_n \phi + F_{n-1}$.  Consider
$\phi^{n+1}$:

\begin{eqnarray*}
\phi^{n+1} & = & \phi^n \phi \\
& = & (F_n \phi + F_{n-1}) \phi \\
& = & F_n \phi^2 + F_{n-1} \phi \\
& = & F_n (\phi + 1) + F_{n-1} \phi \mbox{ because $\phi^2 = \phi + 1$} \\
& = & (F_n + F_{n-1}) \phi + F_n \\
& = & F_{n+1} \phi + F_n \mbox{ by definition of Fibonacci numbers}
\end{eqnarray*}

\item {\small \it Let's call a positive integer
{\em purple} if it is the sum of consecutive positive integers all of
which are less than itself.  For example, $9 = 2 + 3 + 4$ is a purple
number. Prove ({\bf not} by induction!) that a positive integer is purple if
and only if it is not a power of two. (Remember that the {\em if and
only if} means that you have two statements to prove.)
}

First we'll prove the forward direction: suppose $n$ is the sum of
consecutive positive integers.  Then for some $i>0$ and $k>1$,
\begin{eqnarray}
n &=& (i+1) + (i+2) + \ldots + (i + k) \nonumber\\
  &=& ki + (1 + 2 + \ldots + i) \nonumber\\
  &=& ki + {{k(k+1)}\over 2} \label{e1}
\end{eqnarray}
Now multiply both sides of (\ref{e1}) by 2 and factor out $k$ to get:
\begin{eqnarray}
2n &=& k (2i + k + 1)
\end{eqnarray}
Note that powers of $2$ have no odd factors greater than $1$. So if we can show
that $n$ has at least one odd factor greater than $1$, we've proven it's not a
power of $2$.  Let's consider the possibilities for $k$:
\begin{itemize}
\item [] {\bf $k$ is odd:} 
this means that $2n$ contains an odd factor (namely $k$).
\item [] {\bf $k$ is even:}
Then $2i+k+1$ is odd, again meaning that $2n$ has an odd factor.
\end{itemize}
In either case, $2n$ must have an odd factor, meaning that $n$ does as well. So
$n$ cannot be a power of $2$.

Now we'll prove the reverse direction: suppose $n$ is not a power of
two. The proof will be {\em constructive}: namely, we'll show how $n$
can be written as the sum of $k$ consecutive integers starting at
$i+1$.  Since $n$ is not a power of two, $n$ must have some odd factor
$o>1$. So $n$ may be written as $n=xo$ for some $x$. Therefore,
$2n=2xo$. Let's consider the possible ways $o$ and $2x$ could be
ordered.
\begin{itemize}
\item $o=2x$: This is impossible: the lefthand side of the equation is odd, and
the righthand side even.

\item $o>2x$: in this case, set $k=2x$ and $i=(o-1-2x)/2$. We have
\begin{eqnarray*}
n&=&xo\\
 &=& {k\over 2} (2i + 1 + k)\\
 &=& ki + k(k+1)/2\\
 &=& i+1 + i+2 + \ldots + i + k 
\end{eqnarray*}
where the last equality comes from applying Gauss' formula in reverse.

\item $o<2x$: in this case, set $k=o$ and $i=(2x-o-1)/2$. 
That this assignment of $k$ and $i$ satisfies $n = i+1 + i+2 + \ldots + i +
k$ may be shown in a completely analogous manner to the above.
\end{itemize}
We've shown that so long as $n$ isn't a power of two, we can always find a
$i>0$ and $k>1$ such that $n$ is the sum of the numbers from $i+1$ to
$i+k$. This completes the proof.

\item 
{\small \it A limo is two car lengths long and a car is a single car length
long. Let $T(n)$ be the number of distinct possible ways of parking
cars and limos along a curb that is $n$ car lengths long. Order
matters, but any two cars and any two limos are considered identical.
If the curb is 4 car lengths long, then the distinct possible parking
patterns are LL, LCC, CLC, CCL, and CCCC. Thus, $T(4) = 5$. Derive a
recurrence relation for $T$ that completely determines it, and justify
your answer.
}

By inspection, $T(0) = 1$ and $T(1) = 1$.  The first parked vehicle
can be either a car or a limo.  If it's a car, then you can fill up
the remaining $n-1$ spots $T(n-1)$ ways.  If it's a limo, then you can
fill up the remaining $n-2$ spots $T(n-2)$ ways.  Hence (by the
addition principle), the number of ways to fill up $n$ spots is
$T(n-1)$ + $T(n-2)$.

\end{problems}

% asymptotic complexity
\section*{Growth Rates}

\begin{problems}
\item
{\small \it Prove that big-$O$ is transitive: $f(n)=O(g(n))$ and $g(n)=O(h(n))$ implies
$f(n)=O(h(n))$.
}

Since $f = O(g)$, by definition there exist constants $c_1, N_1$ such
that for all $n > N_1$, $f(n) \leq c_1 g(n)$.  Likewise, since $g =
O(h)$, there exist $c_2, N_2$ such that for all $n > N_2$, $g(n) \leq
c_2 h(n)$.  For all $n > \max (N_1, N_2)$, both these constraints
hold, so $f(n) \leq c_1 g(n) \leq c_1 c_2 h(n)$.  Thus $f(n) =
O(h(n))$.

\item
{\small \it Find the flaw in the following inductive proof:\\
{\bf Prove:} $n^2 = O(n)$ \\
{\bf Base case:} for $n=1$, $1^2 = O(1)$. \\
{\bf Inductive step:} Suppose $(n-1)^2 = O(n-1)$.  
Since $n^2 = O((n-1)^2)$, and $n-1 = O(n)$, then by
transitivity of big-$O$ we have $n^2 = O(n)$.
}

The flaw is that in the inductive step, $n$ is a fixed constant.  So
when we write $n^2$ in the inductive step, we are referring to a
constant function, not to the function $f(n) = n^2$. Thus all the
inductive step proves is that for any constant function $f(n) = k$,
$f(n)^2 = O(f(n))$.  But this is trivial to prove without induction.

\item
{\small \it Show that $\log n! = \Theta (n \log n)$.
}

First, we show that $\log n! = O(n \log n)$.
\begin{eqnarray*}
\log n! & = & \log n + \log (n-1) + \log (n-2) + ... + \log 2 + \log 1 \\
        & = & \sum_{i = 1}^n \log i \\
        & \leq & \sum_{i = 1}^n \log n \\
        & =  & n \log n
\end{eqnarray*}
This shows that for all positive $n$, $\log n! \leq n \log n$, so
$\log n! = O(n \log n)$.

Next, we show that $\log n! = \Omega(n \log n)$.  
\begin{eqnarray*}
\log n! & = & \sum_{i = 1}^n \log i \\
& \geq & \sum_{i = \lfloor n/2 \rfloor + 1}^n \log i \\
& \geq & \sum_{i = \lfloor n/2 \rfloor + 1}^n \log \lceil n/2 \rceil \\
& = & \left\lceil \frac{n}{2} \right\rceil \log \left\lceil
\frac{n}{2} \right\rceil \\
& \geq & \frac{n}{2} \log \frac{n}{2} \\
& = & \frac{n}{2} (\log n - \log 2) \\
& \geq & \frac{n}{2} \left(\log n - \frac{1}{2} \log n \right) \mbox{
when $n \geq 4$} \\
& = & \frac{n}{4} \log n
\end{eqnarray*}

So $\log n! = \Omega (n \log n)$ and $\log n! = O(n \log n)$, so
$\log n! = \Theta(n \log n)$. 

Here's an alternate way of proving the lower bound.
\begin{eqnarray*}
\log n! & = & \sum_{i = 1}^n\log i \\
& = & \frac{1}{2} 2 \sum_{i = 1}^n\log i \\
& = & \frac{1}{2} \sum_{i = 1}^n (\log i + \log(n - i + 1)) \\
& = & \frac{1}{2} \sum_{i = 1}^n \log(i(n - i + 1)) \\
\end{eqnarray*}
We want $i(n - i + 1)$ to be greater than or equal to $n$ for $ 1 \leq
i \leq n$.
\begin{eqnarray*}
i (n - i + 1) & \geq & n \\
in - i^2 + i & \geq & n \\
0 & \geq & i^2 - (1 + n) i + n \\
0 & \geq & (i - n) (i - 1)
\end{eqnarray*}
So $i (n-i+1)$ is greater than or equal to n when $1 \leq i \leq n$.
So 
\begin{eqnarray*}
\log n! & \geq & \frac{1}{2} n \log n
\end{eqnarray*}

One common error was to make the claim that $n! = n^n + a_1 n^{n-1} +
a_2 n^{n-2} + ...$ and then argue that $n!$ must be $\Theta(n^n)$.
The initial claim makes no sense.  If you claim that two functions $f$
and $g$ are equal to one another, then you are claiming that for all
$x$ in the domain of $f$, $f(x) = g(x)$.  In the case above, the
domain of $n!$ is all positive integers.  To show that $n! = n^n + a_1
n^{n-1} + a_2 n^{n-2} + ...$, you must show that for all positive
integers $n$, $n!$ equals the expression on the right.  And in order
to do this, you'll have to derive values for $a_1$, $a_2$, ....  But
the values of $a_1$, $a_2$, ... are not constant for different values
of $n$, so the right hand side is not the polynomial it is claimed to
be.

Suppose I am allowed to choose different coefficients for the 
polynomial for different values of $n$.  If I choose $a_1 = -n$, and
all other $a_i = 0$, then the ``polynomial'' above has the value $n^n - n
n^{n-1} = 0 \neq \Theta(n^n)$.  Or I could choose $a_i = -(n-1)$ for
all $i$, and then the ``polynomial'' above has the value $n^n -
(n-1)n^{n-1} - (n-1)n^{n-2} - ... = 1 \neq \Theta(n^n)$.  

\end{problems}

% recurrence relations
\section*{Recurrences}

{\small \it Find closed form solutions to the following recurrence relations.}

\begin{problems}

\item
\begin{eqnarray*}
T(n) & = & T(n-1) + 2T(n-2) \mbox{ for }n > 1 \\
T(1) & = & 1 \\
T(0) & = & 0
\end{eqnarray*}

In general, when you see a recurrence relation of the form \mbox{$a_n = c_1
a_{n-1} + c_2 a_{n-2} + \ldots$}, the recommended approach is this:
\begin{itemize}
\item Substitute $a_n = \lambda^n$; solve for $\lambda$
\item You may get several roots\footnote{In fact, just by looking at the
recurrence you can tell how many roots you'll get, but this is a little past
our level.}, $\lambda_1, \lambda_2, \lambda_3 \ldots$. Write a solution
as $a_n = c_1 \lambda_1 + c_2 \lambda_2 + \ldots$, and use the boundary conditions to
solve for the constants  $c_i$. 
\end{itemize}
(A worked example is given in lecture 5.)

In this case, we'd try $T(n) = \lambda^n$, which gives
\begin{eqnarray*}
\lambda^n = \lambda^{n-1} + 2\lambda^{n-2} ~~~\mbox{or}\\
\lambda^{n-2}(\lambda^2 - \lambda  -2) = 0\\
\end{eqnarray*}

The roots are $\lambda=2, \lambda=-1$ and $\lambda=0$. So we form a solution $a_n=c_1 2^n +
c_2 (-1)^n + c_3 0^n$. Obviously we can chuck the third term, leaving $a_n=c_1
2^n + c_2 (-1)^n$. Now, since $a_0 = 0$ and $a_1=1$, we know that

\begin{eqnarray*}
0 &=& c_1 + c_2 \\
1 &=& c_1 2 -c_2
\end{eqnarray*}
Solving this set of equations gives $c_1 = 1/3$, $c_2 = -1/3$, so the solution
to the recurrence is $a_n = {1 \over 3} 2^n - {1\over 3}(-1)^n$. (You should
confirm this for yourself!)

\item
\begin{eqnarray*}
S(n) & = & S(n-1) + n\mbox{ for }n > 0 \\
S(0) & = & 1
\end{eqnarray*}

Here your best bet is to unravel the mummy: 
\begin{eqnarray*}
S_k=S_{k-1} + k= S_{k-2} + k + (k-1) = \ldots = k+(k-1)+(k-2)+\ldots + 1 + 1
\end{eqnarray*}
(The last $1$ comes from the boundary condition $S(0)=1$). 

Without the extra $1$, this is just the arithmetic sum, which little Gauss's
formula gives in closed form. Tacking back on the $1$, we have $S_n = n(n+1)/2
+ 1$.

\item
\begin{eqnarray*}
T(n) & = & 2 T(n-1) +1 \mbox{ for } n>0\\
T(0) & = & 0
\end{eqnarray*}

Most people did this by writing out the first few terms:
\begin{center}
\begin{tabular}{cc}
$n$ & $T(n)$\\
\hline
$0$ & $0$\\
$1$ & $1$\\
$2$ & $3$\\
$3$ & $7$\\
$4$ & $15$\\
$5$ & $31$\\
\end{tabular}
\end{center}
See a pattern? $T(n)$ seems to be $2^n-1$. But if you weren't sure, you could
also unravel the mummy:
\begin{eqnarray*}
T(n) &=& 2T(n-1) + 1\\
     &=& 2(2T(n-2) + 1) + 1 = 4T(n-2) + 2 + 1\\
     &=& 2(4T(n-3) + 1) + 4 + 2 + 1\\
     &\vdots&\\
     &=& 2^{n-1} + 2^{n-2} + \ldots + 16 + 8 + 4 + 2 + 1
\end{eqnarray*}
Notice that the last term is, in binary, an $(n-1)$-bit number with all
$1$'s. That's one less than $2^n$. 

In either case, the answer is $2^n-1$.

\item
\begin{eqnarray*}
Q(n) & = & {1 + Q(n-1) \over Q(n-2)} \mbox{ for }n>1 \\
Q(1) & = & \beta \\
Q(0) & = & \alpha
\end{eqnarray*}

Unfortunately, this is a problem you can expend a lot of energy on
without getting anywhere, unless you happen to have the right
approach.  That approach is writing out the first few terms:

\begin{itemize}
\item [] $Q_0 = \alpha$
\item [] $Q_1 = \beta$
\item [] $Q_2 = {{1+\beta}\over\alpha}$ 
\item [] $Q_3 = {{1 + {{1+\beta}\over\alpha}}\over \beta} =
{{1+\alpha+\beta}\over{\alpha \beta}}$
\item [] $Q_4 = {{1+ {{1+\alpha+\beta}\over{\alpha \beta}}}\over{1+\beta}}
 = {{1+\alpha}\over \beta}$
\item [] $Q_5 = {1 + {{1+\alpha}\over\beta}\over{{1+\alpha+\beta}\over{\alpha
\beta}}} = \alpha$
\item [] $Q_6 = {{1 + \alpha}\over{{1+\alpha}\over\beta}}=\beta$
\end{itemize}

So this is a repeating sequence: $Q(n)$ = $Q(n \mbox{~mod~} 5)$.

\item
{\small \it 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, give a closed form solution for the number of nodes in an
$n$-level ternary tree have.
}

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*}

\end{problems}

% groups
\section*{Groups}

\begin{problems}

\item
{\small \it List all subgroups of $Z_4=\{0,1,2,3\}$ with the operation $+$ mod $4$.  Now
list all subsets of $\{0,1,2,3\}$. Does the null set (denoted
$\emptyset$) belong to either list?
}


Subgroups: $\{0,1,2,3\}$, $\{0\}$, $\{0,2\}$. 

Subsets: $\emptyset$, $\{0\}$, $\{1\}$, $\{2\}$, $\{3\}$, $\{1,2\}$, $\{1,3\}$,
$\{1,4\}$, $\{2,3\}$, $\{2,4\}$, $\{3,4\}$, $\{1,2,3\}$, $\{1,2,4\}$,
$\{2,3,4\}$, $\{1,2,3,4\}$.

Sets and groups. Two different things. A group has structure---it must
contain an identity element, an inverse and be associative---while a
set does not. A subset of a set is just some number (perhaps $0$) of
objects from the set. A valid subset of a set is the null set,
$\emptyset$. On the other hand, a subgroup always contains at least
one element. Furthermore, any group has among its subgroups at least
$\{e\}$, the group consisting just of the identity element.

\item 
{\small \it The group $S_n$, called the {\em symmetric group}, is the
group of permutations of $n$ elements, using composition as its
operation. For instance, $\{1,4,3,2\}$ is one member of $S_4$.
\begin{enumerate}
\item Assuming $S_n$ is indeed a group, what would its identity element be?
\item What is $\mid S_n \mid$, the size of the group?
\item Prove that $S_n$ is indeed a group for any $n$.
\item Does $S_n$ have any subgroups?
\end{enumerate}
}

\begin{enumerate}
\item The permutation which leaves the elements fixed: $\{1,2,3, \ldots n\}$.
\item $\mid S_n \mid = n!$
\item Do we have closure? Sure---since the composition of two permutations is
itself a permutation. From (a), we have the identity element. What about
inverse? Let's consider some arbitrary element $\{p_1,p_2,p_3,\ldots p_n\}$ of
$S_n$. This maps the $i$th element into the $p_i$th. The inverse permutation
maps the $p_i$'th into the $i$th. Proving associativity is straightforward
symbolic manipulation.
\item The answer to this question is {\em always} yes, since a group is always 
a subgroup of itself. And in the case where the group contains more than one
element, the identity element itself is also a subgroup. In this case, that
means $S_n$ and $\{1,2,3,\ldots n\}$ are subgroups. There are non-trivial
subgroups as well: can you think of any?
\end{enumerate}


\item
{\small \it Given any group $(G,\star)$ and any non-empty subset $H$ of $G$ such
that $a,b \in H$ implies $a^{-1} \star b \in H$, show that $(H,\star)$
is a subgroup.
}

If $a \in H$, then $a^{-1}\star a \in H$, so $e \in H$. So $H$ contains the
identity element. Since $1 \in H$, we know that for any $a\in H$, $a^{-1} \star
1 \in H$, so $H$ contains the inverse of all its elements. Now take any $a,b
\in H$. Since $a \in H$, $a^{-1} \in H$, and so 
$a^{-1}{}^{-1}\star b = a\star b \in H$, so we've shown closure. Associativity,
the final requirement, is inherited from the parent group $G$.


\end{problems}

% counting and probability
\section*{Counting}

\begin{problems}

\item
{\small \it Give a closed form solution to $3+6+9+\ldots + 3n$.
}

This is just little Gauss's formula, rather poorly disguised:
\begin{eqnarray*}
3(1+2+3+\ldots n) = {{3 n (n+1)}\over{2}}
\end{eqnarray*}

\item
{\small \it What is the formula for the power series expansion of ${(x+y)}^n$?
}

${(x+y)}^n = \sum_{i=0}^n {{n} \choose{k}} x^k y^{n-k}$

\item
{\small \it How many subsets can be formed from the elements of an $n$ element set?
}

Study Bird says... $2^n$

\item
{\small \it How many r-bit binary sequences have an odd number of 1s?
}

One answer is ${{r}\choose{1}} +{{r}\choose{3}} +{{r}\choose{5}} +
\ldots$. But on a test, we'd probably ask you for a closed-form
expression. Can you think of one?

The binomial formula, $(x + y) ^n = \sum_i {{n}\choose{i}} x^i
y^{n-i}$, comes in handy here. If you set $x=-1$ and $y=1$, then
$(-1+1)^n=\sum_i {{n}\choose{i}} (-1)^i$. When $i$ is even, $-1^i=1$,
and when $i$ is odd, $-1^i=-1$. So we have
\begin{eqnarray*}
\sum_{i \mbox{~even}} {{n}\choose{i}} = \sum_{i \mbox{~odd}} {{n}\choose{i}} 
\end{eqnarray*}
Therefore, the sum of the ``even'' terms equals the sum of the odd
terms. Since there are $2^r$ binary sequences overall, there are $2^{r-1}$
binary sequences with an odd number of ones. 

(An interesting observation: remember that the $n$'th row of Pascal's
triangle gives ${n}\choose{i}$ for $0 \le i \le n$.  What the above
statement shows is that the sum of the even entries from any row of
Pascal's triangle equals the sum of the odd entries (try it!).)

\item
{\small \it How many ways are there to rearrange the letters in the word EFFORTLESS?
}

${{10}\choose{2! 2! 2!}}$. There are $10$ places to put the first E, $9$
places to put the first F, $8$ places to put the second F, and so on. But then
we've overcounted, since the 2 F's, the 2 E's and the 2 S's are
indistinguishable. 

\item
{\small \it Show that when $n \geq m$
\[{m \choose m}+{m+1 \choose m}+\cdots+{n \choose m} = {n+1 \choose m+1}\]
}

Once again, it's Pascal's triangle to the rescue. Recall that the value in a
particular cell of Pascal's triangle is equal to the sum of the two cells
directly above it. Since the cell in row $n$ and column $m$ equals
${{n}\choose{m}}$, this observation amounts to
\begin{eqnarray}
{{n}\choose{m}} = {{n-1}\choose{m-1}} + {{n-1}\choose{m}}
\label{eq:Pascal} 
\end{eqnarray}

If you didn't think to use Pascal's triangle, you can still get
(\ref{eq:Pascal}) by the following argument. Select one object out of the $n$.
Now, picking $m$ objects from $n$ can be done in two ways: either by selecting
the one object, and then $m-1$ from the remaining $n-1$, or by completely
ignoring the one and just choosing $m$ from the remaining $n-1$. 

Using this observation,
\begin{eqnarray*}
{{n+1}\choose{m+1}} &=&{n \choose m} + {n \choose {m+1}}\\
 &=& {n \choose m} + {n-1 \choose {m}} + {n-1 \choose {m+1}}\\
 &=& {n \choose m} + {n-1 \choose {m}} + {n-2 \choose {m}} + {n-2 \choose {m+1}}\\
 &\vdots& \\
 &=& {m \choose m}+{m+1 \choose m}+\cdots+{n \choose m} 
\end{eqnarray*}

We're just expanding one more term in each equation. You'd probably want to
dress this up in a nice inductive proof in a homework assignment, but this is
fine for an exam solution.

\item
{\small \it What is the coefficient of $a^4b^6$ in $(a^2+b)^8$?
}

If we make the substitution $x=a^2$, the problem becomes: find the coefficient
of $x^2b^6$ in  $(x+b)^8$. Recall the binomial expansion:
\begin{eqnarray*}
(x+y)^n = \sum_{k=0}^n {{n}\choose{k}} x^k y^{n-k}
\end{eqnarray*}
The coefficient for $k=2$ is ${{8}\choose{2}}=8*7/2=28$.

\item
{\small \it How many integer solutions to the following equations?
\[ X_1 + X_2 + X_3 + X_4 + X_5 = 50,\ \  X_i \geq 0  \]
}

${{54} \choose{4}}$. This is just like the problem of dividing $50$ gold
bars among $5$ thieves: let $X_i$ be the number of gold pieces given to the
$i$'th thief.  See lecture 11.


\item
{\small \it An $n$-input, $m$-output boolean function is a function from $\{0,1\}^n$
to $\{0,1\}^m$.  (Think of a circuit with $n$ inputs and $m$ outputs.)
How many $n$-input, 1-output boolean functions are there?  How many
$n$-input, $m$-output boolean functions are there?
}

To specify an $n$-input, $m$-output boolean function $f$, we need to say what 
$f$ maps each of the $2^n$ different inputs to. There are $2^m$ choices for
each input, or 
\begin{eqnarray*}
\left( 2^n \right)^{\left( 2^m \right)}
\end{eqnarray*}
possible functions. 

For the special case where $m=1$, there are $\left(2^n\right)^2$ functions.

\item
{\small \it How many ways can three distinct numbers be chosen from the set
${1,2,\ldots,100}$ such that their sum is even?
}

There are $50$ even numbers and $50$ odd numbers in the set. We can
get an even sum by choosing three even numbers, or by choosing two odd
and one even number. There are ${50}\choose{3}$ ways to do the first
and $50\cdot {{50}\choose{2}}$ ways to do the second. Total:
${{50}\choose{3}}+50\cdot {{50}\choose{2}}$.

\item
{\small \it How many ways are there to seat 5 children in a row of 12 chairs?
}

First pick the chairs (${12}\choose{5}$ ways) and then arrange the children in
the chairs ($5!$), for a total of ${{12}\choose{5}} 5!$.

\item
{\small \it A {\em chord} is a line segment connecting two points on a
circle.  Suppose you are given $n$ points on a circle such that no
three of the chords connecting them intersect in the same point.  Into
how many line segments are the chords divided by their intersections?
}

First, we count the chords: $n \choose 2$ chords, one for each pair of
the $n$ points.  Next we count the intersection points of the chords.
Unfortunately not every pair of chords intersects.  But for every set
of four points A, B, C, D, exactly one pair of chords between them
intersects.  (Imagine the points at the four corners of a
quadrilateral ABCD.  Then the sides AB/CD and AD/CB do not intersect,
but the diagonals AC/BD do intersect.)  Thus we have one intersection
point for every four points on the circle, so there are $n \choose 4$
intersection points.

Now that we know the number of chords and the number of intersection
points, we can count the total number of line segments into which the
chords are divided by their intersections.  If a chord contains $k$
intersection points, then it is divided into $k+1$ line segments.  In
other words (remember the chocolate bars problem?), we start with ${n
\choose 2}$ unbroken chords, and every intersection point breaking a 
chord creates a new line segment.  Since every intersection point
breaks two chords, the total number of line segments is
\[{n \choose 2} + 2 \cdot {n \choose 4}\]


\item
{\small \it How many ways can 3 exams be scheduled in a 5-day period such that no
two exams are held the same day?
}

There are ${5}\choose{3}$ ways
to pick the three days on which to hold exams, and once you've selected the
days there are $3!$ ways to arrange the exams in these days:
\mbox{${{5}\choose{3}} 3!$}.


\item
{\small \it A palindrome is a word that reads the same forwards and backwards.
How many seven-letter palindromes can be made from the English
alphabet?
}

There are $26$ choices for the first letter. Once that's been chosen, the last
letter is fixed. Similarly, there are $26$ choices for both the second and
third letters. And the fourth (middle) letter can be anything. So there are
$26^4$ possibilities overall. 

\item
{\small \it Show that the product of any $k$ consecutive integers is divisible by
$k!$
}

Suppose the product is $(n+1)(n+2) \cdots (n+k)$ for some arbitrary
integer $n$.  If the product includes a zero factor, then the product
is zero, which is clearly divisible by $k!$ So suppose the product
doesn't include 0; then either the factors are all positive or
all negative.  Suppose they are all positive; then we can write
\[{n \choose k} = {(n+k)! \over n! k!} = {(n+1)(n+2) \cdots (n+k) \over k!}\]
which is an integer, so $k!$ must divide the product.  If all the
factors are negative, then factor out -1 to get $(-1)^k$ times a
product of $k$ successive positive integers, which must be divisible
by $k!$ by the previous argument.

\item
{\small \it How many ways are there to place $r$ red balls and $w$ white balls
into $n$ distinct boxes such that each box contains at least one ball
of each color?
}

There are ${r-1 \choose n-1}$ ways to place the red balls.  One way to
see it is to line up the $r$ red balls and choose $n-1$ of the $r-1$
places between balls for the box dividers.  Similarly, there are ${w-1
\choose n-1}$ ways to place the white balls.  By the product rule, the
number of ways to place both red and white balls is \[{r-1
\choose n-1}{w-1 \choose n-1}\]

\item
{\small \it Imagine a town with East-West streets numbered 1 through n, and
North-South avenues numbered 1 through m. A taxi cab picks up a passenger at the
corner of 1st street and 1st avenue. The passenger wishes to be delivered to
nth street and mth avenue. It is quite clear that the passenger will be
angry if the cab chooses a route longer than $(n-1)+(m-1)$ blocks, so we won't
allow the cabby to take a route longer than this. In other words, the cabby
must always be increasing his street number or his avenue number.
Suppose that there is an accident at ith street and
jth avenue. How many routes can the cabby take that avoid the
intersection with the accident?
}

To start, let's forget about the accident and count the number of ``legal''
(non-backtracking) ways the cabby could go. He needs to traverse $m-1$ E-W
blocks and $n-1$ N-S blocks, and he can do this in any order. So there are
${m-1+n-1}\choose{m-1}$ ways he can go (this is the number of ways to put the
E-W blocks in his route.) 

But the accident eliminates some possibilities. How many? In other words, how
many ways are there to start from $(1,1)$, go to $(i,j)$, and from there go to
$(n,m)$? There are ${{i-1+j-1}\choose{i-1}}$ ways to get to $(i,j)$, and from
there ${{m-j+n-i}\choose{n-i}}$ ways to get to $(m,n)$. The number of
paths from $(1,1)$ to $(m,n)$ is the product of these numbers. Subtracting this
from the total number of paths gives the answer, 

\begin{eqnarray*}
{{m-1+n-1}\choose{m-1}} - {{{i-1+j-1}\choose{i-1}}} {{{m-j+n-i}\choose{n-i}}}
\end{eqnarray*}

\end{problems}


\end{document}

