\documentclass[12pt,twoside]{article}
\usepackage{light}

\hidesolutions

\begin{document}

\generic{Counting Miniquiz - Side Sections}{April 5, 2005}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Ishan Sachdev, famed 6.042 TA, has decided to try out for the US
olympic boxing team.  To prepare, he's watched all of the
\textit{Rocky} movies and spent hours in front of a mirror sneering,
``Yo, you wanna piece a' \textit{me}?!''.

Ishan figures that $n$ people (including himself) are competing for
spots on the team and only $k$ will be selected.  In how many
different ways can the team be selected?

\solution[\vspace{0.5in}]{
\[
\binom{n}{k}
\]
}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
A deck contains $n$ red cards (numbered $1, \ldots, n$) and $2n$ black
cards (numbered $1, \ldots, 2n$).

\bparts

\ppart In how many ways can we select $n$ cards from this deck, if
exactly $r$ of them must be red and the remaining $n - r$ must be
black?

\solution[\vspace{1in}]{
\[
\binom{n}{r} \cdot \binom{2n}{n - r}
\]
}

\ppart Suppose we select $n$ cards from the deck.  The number of red
cards that we select, $r$, must be between 0 and $n$.  Use the Sum
Rule and your previous answer to determine the total number of ways to
select $n$ cards.  Leave your answer as a summation.

\solution[\vspace{1in}]{
\[
\sum_{r=0}^{n} \binom{n}{r} \cdot \binom{2n}{n - r}
\]
}

\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\iffalse
\newpage

\begin{center}
{\LARGE \textbf{A Puzzle}}
\end{center}

This is one of the stranger mathematical puzzles in the ``Google
aptitude test''.

\begin{quotation}
\noindent {\Large 'Tis known in refined company, that choosing K
things out of N can be done in ways as many as choosing N minus K from
N: I pick K, you the remaining.

\bigskip

\noindent Find though a cooler bijection, where you show a knack
uncanny, of making your choices contain all K of mine. Oh, for
pedantry: let K be no more than half N.}
\end{quotation}

The first sentence is a crude combinatorial proof that:
%
\[
\binom{N}{K} = \binom{N}{N-K}
\]
%
The second sentence evidently refers to another, more complicated
identity.  Can you figure out what the identity is and then prove it
combinatorially?

\solution{
My best guess is:
%
\[
\binom{N}{K} \binom{N-K}{N-2K} = \frac{N!}{K!\ K!\ (N-2K)!}
\]
%
I can choose my things in $\binom{N}{K}$ ways.  Now suppose that you
still choose $N-K$ things, but $K$ of are mine.  Then you're
effectively choosing $N-2K$ things out of the $N-K$ that I did not
select.  This gives the left side.

On the other hand, we can divide all items into three classes:
%
\begin{itemize}

\item[(A)] The $K$ items that we both selected.

\item[(B)] The $N-2k$ items that you selected, but I did not.

\item[(C)] The $K$ items that no one selected.

\end{itemize}
%
The number of ways to assign items to classes is:
%
\[
\frac{N!}{K!\ K!\ (N-2K)!}
\]
%
by the Bookkeeper Rule.
}
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
