\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{psfig}
\usepackage{graphics}
\input{../handouts/macros-course}


\newif\ifspaceout
\spaceouttrue
\newcommand{\smallspace}{\ifspaceout\vspace{1in}\fi}
\newcommand{\mediumspace}{\ifspaceout\vspace{3in}\fi}
\newcommand{\largespace}{\ifspaceout\vspace{4in}\fi}
\newcommand{\nextproblem}{\ifspaceout\newpage\fi}


\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}

\newcommand{\bij}{\mathbin{\mbox{\rm bij}}}
\newcommand{\inj}{\mathbin{\mbox{\rm inj}}}
\newcommand{\sur}{\mathbin{\mbox{\rm sur}}}
\newcommand{\ran}[1]{\text{range}(#1)}
\newcommand{\Union}{\bigcup}

\newcommand{\eqdef}{\mathbin{\mbox{::=}}}

\newcommand{\ROT}{\mbox{ROT}}
\newcommand{\FBT}{\mbox{FBT}}
\newcommand{\brep}{\mbox{rot-to-fbt}}
\newcommand{\unrep}{\mbox{fbt-to-rot}}
\newcommand{\nil}{\mbox{\texttt{()}}}
\newcommand{\sz}{\mbox{size}}
\newcommand{\cons}{\mbox{cons}}
\newcommand{\sbtr}{\mbox{subtrees}}
\newcommand{\kcomp}[1]{\bar{#1}}

\newcommand{\fins}{\mathcal{F}}

\newcommand{\kpfend}{}

\newcommand{\kskip}[1]{}

\newcommand{\pts}[1]{\relax[#1 points]\enskip\ignorespaces}
\newcommand{\onept}{\relax[1 point]\enskip\ignorespaces}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
    \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother

\askaboutsolutions

\begin{document}
%\querysol{q2}{Quiz 2}{April 18 2001}{q2sol}{Quiz 2 Solutions}{April 18 2001}

\ifshowsolutions
\qsol{2}{April 20 2001}
\spaceoutfalse
\else
\exam{Quiz 2}{April 18 2001}
\fi

%\titlebar

\textbf{Your Name}:\ \mbox{}\hrulefill\mbox{}\par

\textbf{Circle the name of your Tutorial Instructor}:\\
\begin{center}
\begin{tabular}{c@{\hskip 3em}c@{\hskip 3em}c@{\hskip 3em}c}
George & Joe & Josh & Kavita \\
\ &&& \\
Ivan & Ray & Tina &
\end{tabular}
\end{center}

\medskip

\noindent Write the hour at which your Friday recitation begins \brule{3em}

\medskip

\begin{closeitemize}
\item This quiz is open book/notes.  

\item There are 8 pages with 7 problems totaling 70 points.  Problem 
  parts are labeled with their point values.

\item Put your name on the top of {\bf every} page --- \emph{these
    pages may be separated for grading}.

\item Write your solutions in the space provided.  If you need more
  space, write on the back of the sheet containing the problem.
  Please keep your entire answer to a problem on that problem's page.

\item You may assume any of the results presented in class or in the
  lecture notes.

\item Show your work, as partial credit will be given.  You will be
  graded not only on the correctness of your answer, but also on the
  clarity with which you express it.  {\bf Be neat and write legibly}.

\item GOOD LUCK!
\end{closeitemize}

\bigskip

\medskip

\hrule
\smallskip
\centerline{\textbf{DO NOT WRITE BELOW THIS LINE}}
\smallskip
\hrule

\medskip

\begin{center}
\renewcommand{\arraystretch}{.3}
\begin{tabular}{|c|c|c|c|}
\hline
& &\hspace*{1in}&\\
Problem & Points & Grade & Grader\\
& & & \\ \hline \hline
& & & \\
1 &  10 & & \\ & & & \\\hline & & &\\
2 &  10 & & \\ & & & \\\hline & & &\\
3 &  10 & & \\ & & & \\\hline & & &\\
4 &  10 & & \\ & & & \\\hline & & &\\
5 &  10 & & \\ & & & \\\hline & & &\\
6 &  8 & & \\ & & & \\\hline & & &\\
7 &  12 & & \\ & & & \\\hline & & &\\
\hline
\hline
& & &\\
Total & 70 & & \\
& & &\\
\hline
\end{tabular}
\end{center}


\newpage

\begin{problems}
% from spring 00, the problem topics to be included are:
% recurrence, inclusion-exclusion, stars and bars, 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% annuities problem from the problem base..
\problem {\bf (10 points)}

Recently, David Bowie, a British music star, sold a portion of the
future profits from his music for \$55 million dollars to Prudential
Insurance.  This deal spawned others among superstar entertainers and
athletes.

(If you don't have a calculator, you don't have to compute numerical
answers. BUT, your answer should be in closed form, in particular, it
must not contain any summations.)

\begin{problemparts}

\problempart Manny Ramirez's contract with the Red Sox is that they will
pay him \$20 million a year for the next eight years. To be specific, assume
he will be paid \$20 million a year today (the first year) and on the same
day of each future year through the eighth year. A little-known provision of his
contract provides him with a ``bonus'' based on performance, which
will be paid out only once, on the same day in the ninth year. Manny has
offered to transfer his salary and bonus 
to a group of investors for \$160 million
dollars paid to him today. How large must the ``bonus'' be for the
investors to break even, assuming an interest rate of 10\% a year?
{\bf (5 points)}

%\vspace*{2.6in}
\solution{ {\bf{Solution:}}
Let x be the ``bonus'' Manny must recieve on the the ninth year.

\begin{eqnarray*}
160 million 
        & = & \sum_{i=0}^{7} \frac{20 \text{ million}}{(1+0.1)^i} + \frac{x}{(1+0.1)^8}\\
        & = &   \frac{20 \text{ million*}(1-\frac{1}{(1+0.1)^8})}{1-\frac{1}{(1+0.1)}} + \frac{x}{(1+0.1)^8}\\
        & = &   \$117.368 \text{ million} + x \cdot 0.4665 \\
\end{eqnarray*}

Solving the above equation for \emph{x}, we get \emph{x} = 91.4 million.

Common errors for this part include: not using the right indices in the sum, not discounting the bonus and assuming that it was paid today, and discounting the bonus by the wrong amount.
}

\problempart Britney Spears figures that she can generate at least \$20
million from her music starting today and on
the same day of all future years for eternity.  What
should an investor who wants a 10\% return pay today for the rights to her
income? {\bf (5 points)}

\medskip
\solution{ {\bf{Solution:}}

Let $M = \$20,000,000$.  Britney is worth

\begin{eqnarray*}
\sum_{i=0}^{\infty} \frac{M}{(1+0.1)^i}
        & = &   \frac{M}{1 - \frac{1}{1+0.1}} \\
        & = &   \$220 \text{ million}
\end{eqnarray*}

Since the investor wants a 10\% return, he should pay

\begin{eqnarray*}
\$220 \text{ million} / 1.1  & = &     \$200 \text{ million}
\end{eqnarray*}

The biggest mistake in this problem was not understanding what ``10\% return'' meant.  This simply means that the investor wants to make 10\% on however much he pays today, and so, $220\text{ million} = 110\%$ of the investment. 
}

\end{problemparts}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% fall 97 final

\problem {\bf (10 points)}

For each of the following recurrences, find a closed-form solution
for $T(n)$.
\bparts

\ppart

$$
T(n+1) = 8T(n) - 16T(n-1)
$$

with the initial conditions $T(0) = 1, T(1) =12$. {\bf (5 points)}
%\vspace*{3.5in}

\solution{\textbf{Solution:}
  The characteristic polynomial $x^2-8x+16 = (x-4)^2$ has a
  double root at~$4$; thus the solution has the form $T(n) = a4^n + bn4^n$.
  Plugging in the initial conditions gives the linear equations
  $1 = T(0) = a$ and $12 = T(1) = 4a + 4b = 4 + 4b$. Thus, the solution is
  $T(n) = (1 + 2n)4^n$.}

\ppart

$$
T(n+1) = 8T(n) - 16T(n-1) + 2^n
$$

with the initial conditions $T(0) = \frac52, T(1) = 5$. {\bf (5 points)}

\solution{\textbf{Solution:}
  A particular solution is of the form $k2^n$.
  Plugging in the equation we obtain $k=\frac12$.
  We proved in the first part of the problem that the homogeneous
  solution is $a4^n + bn4^n$.

  So the general solution has the form
  $a4^n + bn4^n + 2^{n-1}$
  We use the initial conditions to solve for $a,b$ to obtain
  $a = 2$, $b = -1$

  So the answer is $T(n) = (2-n)4^n+2^{n-1}.$

  Common errors on this part of the problem included reusing constants from part a or solving for them without including the particular solution in.  This error cost a couple of points.  Another common error was shifting all the n's but not shifting the n term on $2^n$.  This also cost two points.  Any arithmetic mistakes cost a point.  
}
\newpage
\eparts

\problem
{\bf (10 points)}

How many $6$-digit natural numbers are there that do not contain
``$123$'' or ``$456$'' as a subsequence? (for purposes of this problem
numbers may have leading $0$'s, so the 6-digit natural numbers are
$000000$, $000001$, $\ldots$, $999998$, $999999$).

\bigskip
\solution{ {\bf{Solution:}}
Let
\begin{itemize}
\item $A$ be the set of all six-digit strings, using the digits
$\{0, 1, \ldots, 9\}$.
\item $B$ be the set of six-digit strings that contain the subsequence
$123$.
\item $C$ be the set of all six-digit strings that contain the subsequence
$456$.
\item $D$ be the set of all six-digit strings that do not contain 
$123$ or $456$.
\end{itemize}
We're interested in figuring out $| D |$.
Since $$D = A - (B \cup C),$$
and $B \cup C \subseteq A$,
we can use the inclusion-exclusion formula:
$$| D | = | A | - |B \cup C| = | A | - | B | - | C | + | B \cap C |.$$

First, $|A| = 10^6$, since we can put any of ten digits in each of
six places.  

Now, a string can contain $123$ in any of four positions; once this
position is chosen, we have $1000$ choices for the remaining positions.
However, this approach counts the string $123123$ twice, so 
the total size of $B$ is
$$| B | = 4(1000) - 1 = 3999.$$
By the same reasoning, we get
$$| C | = 3999.$$

Finally, there are only two strings in $B \cap C$, namely $123456$ 
and $456123$.  Thus,
$$| B \cap C | = 2.$$
Plugging this into our formula, we get
$$| D | = 10^6  - 3999 - 3999 + 2 = 992004.$$


By far the most common error was to fail to adjust for the overcount 
of the sequences $123123$, $123456$, $456123$, and $456456$.  Some 
students did not allow for repetition of digits or tried to 
compute permutations of some digits using factorials.
}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem 
{\bf (10 points)}
%The Theory of numbers by Niven..., page 208

Let \emph{S} be any set of $2n+1$ integers selected from $1, 2,
\dots, 3n$.
\bparts

\ppart Prove that there must be three consecutive integers that are
in the set \emph{S}.

\solution{ {\bf{Solution:}}
Let the $n$ successive triples of consecutive integers
$(1,2,3),(4,5,6),(7,8,9) \dots (3n-2,3n-1,3n)$ be the holes.  Assign each
pigeon to the hole in which it occurs.  Since there are more than twice as
many pigeons as holes, three pigeons must occupy one hole, say
$(k,k+1,k+2)$.  These are three consecutive pigeons.}

%\vspace*{3.5in}
\ppart Show that among any set of $2n+1$ integers selected from
$1, 2, \dots, 3n$, there must be two that are relatively prime and one of
these two is divisible by three.

\solution{ {\bf{Solution:}}
Of any three consecutive integers $(k,k+1,k+2)$, one must be divisible by
three.  Say it is either $k$ or $k+1$.  Now there are no common divisors of
$k$ and $k+1$, because if $k+1$ was divided by any divisor of $k$ there
would be a remainder of 1.  So in this case, $k$ and $k+1$ are the desired
two relatively prime pigeons, and one of them is divisible by three.  If
neither $k$ nor $k+1$ is divisible by three, then $k+2$ must be divisible
by three, so in this case, by the same reasoning, $k+1$ and $k+2$ will be
the desired two pigeons.

\paragraph{Comments:}
\begin{itemize}
\item Many people didn't realize that they needed to use the generalized pigeonhole principle in this problem, and thought that, since you have $2n+1$ holes, you must somehow figure out what the $2n$ pigeons are. 
\item Others didn't know how to apply the generalized pigeonhole principle: If you have $n$ holes and $n+1$ pigeons, there must be at least one hole with 2 pigeons. If you have $n$ holes and $2n+1$ pigeons, you will have at least one hole with $3$ pigeons. In general, if you have $H$ holes and $P$ pigeons, you're guaranteed to have at least one hole with $\lceil \frac{P}{H}\rceil$ pigeons. In this problem, you needed to argue that 3 pigeons would end up in the same hole, which would imply that there are 3 consecutive numbers. So, since you have $2n+1$ pigeons, you needed to figure out what the $n$ holes were.
\item Several people resorted to some kind of ``proof by example'', bypassing a pigeonhole argument altogether. That is, they argued something like: ``the only way you can avoid having 3 consecutive numbers is by leaving out every third number, like this: $\fbox{12}~3~\fbox{45}~6~\fbox{78}~9 \ldots n$''. Such proofs are not acceptable because they do not consider possible alternatives. If you want to claim that this is the only way you can do it, you have to \emph{prove} it first. Proofs ``by intimidation'' or ``by emphatic assertion'' are not accepted in this class. You'll need to wait until you start producing published papers before you start using those.
\item Several others tried to correlate this problem to some of the pigeonhole problems we've seen in the problem sets and tutorials, and defined the holes as the numbers modulo 3, or wrote each number as $a\cdot 3^b$ and tried to derive something from there. These techniques did not work here, since the problem was asking for something completely different.
\item In part (b), many failed to realize that the results from part (a) could be used in part (b). Moreover, many did not notice that the question was asking for two numbers that are relatively prime and one of \emph{those two} is a multiple of 3. So they went on to prove these two things independently (that is, prove the existence of two relatively prime numbers, and then prove the existence of a multiple of 3). 
\item Pigeons is not spelled ``pidgeons'', despite the fact that the second spelling has received the majority vote of the students.

\end{itemize}
}


\eparts
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%some more sums.
 \problem  {\bf (10 points)} 

Short analyses.  {\bf
  Be careful} to look at the summation indices.

\begin{problemparts}

\ppart 
What is the product of the first $n$ odd powers of two:
$\prod\limits_{k=1}^n2^{2k-1}$?    {\bf (3 points) }

\medskip
\solution{ {\bf{Solution:}}
\[
\Pi_{k=1}^n2^{2k-1} = 2^{\sum_{k=1}^n{2k-1}}
= 2^{2\sum_{k=1}^n k-\sum_{k=1}^n 1}
= 2^{n(n+1) - n}
= 2^{n^2}
\]
}
%\vspace*{2in}
\ppart What is $\sum\limits_{k=a}^b k$?    {\bf (3 points)}

\medskip
\solution{ {\bf{Solution:}}
\[
\sum_{k=a}^b k = 
\sum_{k=1}^b k - \sum_{k=1}^{a-1} k = 
\frac{b(b+1)}{2} - \frac{a(a-1)}{2}
\]

Also, some students computed the same answer directly
in the form
\[
\frac{(a+b)(b-a+1)}{2}
\]
by noticing that the first and last terms sum
to $(a + b)$, the second and next to last terms also
sum to $(a + b)$, etc. This means that we are adding
the term $(a + b)$ a number of times equal to
$\frac{(b - a + 1)}{2}$ sinc there are $(b -a + 1)$ terms
and we take two for each $(a + b)$.

The most common mistake on this part was to sum
up to $a$ instead of $a-1$ using the first approach.
}
%\vspace*{2in}

\ppart
Find upper and lower bounds for 
$$
\sum_{k=1}^n\frac{1}{\sqrt{k}}
$$
which differ by at most 1.    {\bf (4 points)}
\medskip
\solution{ 

{\bf Solution:}
\begin{eqnarray*}
\int_0^n \frac{1}{\sqrt{x+1}} \ dx \leq & \sum_{k=1}^n \frac{1}{\sqrt{k}} & \leq \int_0^n \frac{1}{\sqrt{x}}\ dx \\
\int_0^n \frac{1}{\sqrt{x+1}} \ dx \leq & \sum_{k=1}^n \frac{1}{\sqrt{k}} & \leq 1 + \int_1^n \frac{1}{\sqrt{x}}\ dx \\
2\sqrt{n+1} - 2 \leq & \sum_{k=1}^n \frac{1}{\sqrt{k}} & \leq 1 + 2\sqrt{n} - 2\\
2\sqrt{n+1} - 2 \leq & \sum_{k=1}^n \frac{1}{\sqrt{k}} & \leq 2\sqrt{n} - 1
\end{eqnarray*}

The most common mistake on this part of the problem was
having the wrong limits of integration (going from $1$ to $n$
instead of from $0$ to $n$). The more severe (and less common)
mistake was to switch the two functions for the upper and lower
bound.
}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% a true/false question.. we can try maybe?  makes grading nice..
\newpage \problem {\bf (8 points)} Circle T or F for all questions,
even if you have to guess.

\begin{tabbing}
123\=456\=789\=012\=\kill

\\
    \> T \> F \>  There is a surjection $f:\naturals \rightarrow \reals$.\\
\solution{
   \> \> \>  {\bf FALSE}  $\reals$ are uncountable, $\naturals$ are countable so no surjection can exist. \\ }
\\
    \> T \> F \>  Any binary relation on the natural numbers is countable.
\\
\solution{
   \> \> \>  {\bf TRUE}, since $\naturals$ is countable, we know
$\naturals\times\naturals$ is countable and a binary
relation \\
   \> \> \> on $\naturals$ is by definition a subset of $\naturals\times
\naturals$. \\}
\\
%    \> T \> F \>  If a set $A$ contains an uncountable subset $B$, then $A$ is
% uncountable.\\
%\solution{
%   \> \> \>  {\bf TRUE}\\}
%%\\
    \> T \> F \>  If an uncountable set $A$ contains a countable subset $B$,
               then $A-B$ is uncountable.\\
\solution{
   \> \> \>  {\bf TRUE}; if $A-B$ were countable, then $A\subseteq B\cup (A-B)$ would
be a union\\
   \> \> \>  of two countable sets and therefore countable.\\}
\\
    \> T \> F \>  If $f:A\rightarrow B$ is a surjection,  
          $f^{-1}:B\rightarrow A$ is an injection.\\
\solution{
   \> \> \>  {\bf FALSE}, $f^{-1}$ may not even be a function (if $f$ maps
two elements of $A$ to\\
   \> \> \>  the same element of $B$) \\}
\\
    \> T \> F \>  If an uncountable set $A$ contains an uncountable subset $B$,
               then $A-B$ is countable.\\
\solution{
   \> \> \>  {\bf FALSE}, consider $B=\reals^{+}$, $A=\reals$. \\}
\\
    \> T \> F \>  The set of functions from $\{0,1\}$ to $\naturals$ is uncountable.\\
\solution{
   \> \> \>  {\bf FALSE} since it is the set of all fourtuples $(0, a, 1, b)$ where $a,b \in \naturals$\\}
\\
    \> T \> F \>  The set of functions from $\naturals$ to $\{0,1\}$ is uncountable.\\
\solution{
   \> \> \>  {\bf TRUE} since it is equinumerous to ${\cal P}(\naturals)$\\}
\\
    \> T \> F \>  The expansion of $(x - 1)^{120}$ has three identical nonzero
coefficients.\\
\solution{
   \> \> \>  {\bf FALSE}, looking at Pascal's triangle binomial coefficients
 \\
   \> \> \> increase to a maximum and then decrease. The coeffs. of $(x-1)^{120}$\\
   \> \> \> are binomial coeffs. and their negatives, so at most two can be equal.\\
}
%    \> T \> F \>  If $p > 5$ is prime, then $p \mid {p \choose {p-4}}$.\\
%\solution{
%   \> \> \>  {\bf TRUE} $p \choose {p-4}$ = $\frac{p!}{(p-4)!4!} = \frac{p \cdot (p-1) \cdot (p-2) \cdot (p-3)}{4 \cdot 3 \cdot 2}$ \\
%\text{Since p is not 0 mod 2, or 0 mod 3, or 0 mod 4, (p-1) and (p-3)
%must be both 0 mod 2.  
%Likewise, either (p-1) or (p-2) must be 0 mod 3 and 
%either (p-1) or (p-3) is 0 mod 4.  If (p-1) is 0 mod 3 and 0 mod 4, then
%it must be also 0 mod 12, and since (p-3) is 0 mod 2, we know the equation
%must be 0 mod p.  In any other case, we have one number each that is
%0 mod 2,3, and 4, so again, the equation is 0 mod p.}\\}
\end{tabbing}

{\bf Comments:}

There's not too much to say about this problem since we didn't ask for
justification. Numbers 6 and 7, about countability of sets of functions,
seemed to trip up many people.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
\problem
{\bf (12 points)}
For each of the following problems, determine the value or expression
requested.  Briefly justify your answers.

\bparts

\ppart How many of the billion numbers in the range from 1 to and including
1,000,000,000 contain the digit~$1$?  
(\hint Don't do inclusion/exclusion.) {\bf (3 points)}
\medskip
\bigskip

\solution{
{\bf Solution:}
We can count up how many DO NOT contain the digit 1 and subtract:

(Total Number) - (number without 1's) 

$1,000,000,000 - (9^9 - 1) = 612,579,512$

(the minus is for 0 which is not in our range)
}

%\vspace{1in}
\ppart Consider the set of $10^n$ $n$-digit integers (where leading
0's are permitted).  Consider two integers to be equivalent if the
digits of one are a permutation of the digits of the other.  How many
equivalence classes of the $10^n$ $n$-digit integers are there? 
{\bf (3 points)}

\solution{
{\bf Solution:}

Here, we can use a stars and bars idea.  Let there be 9 bars for each number from 0-9.  There are n stars for the number of digits.  

$ 9+n \choose n $
} 

%\vspace{1in}

\ppart How many ways are there to order the 26 letters of the alphabet
so that no two of the vowels {\tt a}, {\tt e}, {\tt i}, {\tt o}, {\tt
u} appear consecutively and the last letter in the ordering is not a vowel?  
{\bf (3 points)}

\solution{
{\bf Solution:}

Here, we can again use a stars and bars idea.  We can let the 21 bars
be the consonant letters in the alphabet.  We can let our 5 stars be
the vowels.  Now, we must choose 5 places to place our stars such that no
two stars are next to each other.  We simply choose 5 out of 21 of our bars
and stick our stars to the left of each of the chosen bars.  Once we have
choosen these, we can order the vowels and consonants as we like.

$ 21 \choose 5$ $ \cdot 21! \cdot 5! $
}
%\vspace{1in}
\ppart How many ways are there to order the 26 letters of the alphabet
so that there are {\em at least two} non-vowels between any pair of vowels,
and the last two letters in the ordering are not vowels? {\bf (3 points)}

\solution{
{\bf Solution:}

Glue two consonants to the right of every vowel. Let these object be
the bars and the remaining consonants be the bars. There are 11
remaining consonants, i.e., stars, and 5 bars. Therefore, there are
\begin{displaymath}
  \binom{16}{5}
\end{displaymath}
ways to arrange the stars and bars. Each such arrangement corresponds
to a unique ordering of vowels and consonants. To count the number of
orderings of letters, we need to multiply this by $5!21!$ since there
are 5~vowels and 21~consonants. So, the final answer is
\begin{displaymath}
  \binom{16}{5}5!21! = \frac{16!21!}{11!}\,.
\end{displaymath}


Common errors: These all required some insight into the problem and
were very difficult to do if you attempted some other method
(especially inclusion/exclusion).  The most common mistakes beyond
that were to forget about 0 in part a or to not order the cards in
parts c and d.
}

%\vspace{1.3in}
%\ppart \phantom{H}
\eparts
%possible combinatorial problem on picking 5 cards from deck of 52
%this is the one David proposed today

%possible recurrence problem, how many calls are made to fib in computing
%fib(n) by the stupid recursive algorithm.
\end{problems}

\end{document}


