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

\hidesolutions

\begin{document}

\generic{Counting Miniquiz - Middle Section}{April 5, 2005}

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

\begin{problem}
Ishan, famed 6.042 TA, has decided to try out for the US olympic
boxing team.  After all, 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.  There are only two
possibilities:

\bparts

\ppart Ishan is selected for the team, and his $k - 1$ teammates are
selected from among the other $n - 1$ competitors.  In how many
different ways can this happen?

\solution[\vspace{1in}]{
\[
\binom{n-1}{k-1}
\]
}

\ppart Ishan is not selected for the team, and all $k$ team members
are selected from among the other $n - 1$ competitors.  In how many
different ways can this happen?

\solution[\vspace{1in}]{
\[
\binom{n - 1}{k}
\]
}


\ppart Use the Sum Rule and your answers to the two previous problem
parts to determine all possible ways to select the US olympic boxing
team.

\solution[\vspace{1in}]{
\[
\binom{n-1}{k-1} + \binom{n - 1}{k}
\]
}

\eparts

\end{problem}

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

\begin{problem}
A deck contains $n$ red cards (numbered $1, \ldots, n$) and $2n$ black
cards (numbered $1, \ldots, 2n$).  In how many different ways can $n$
different cards be selected from this deck?

\solution{
\[
\binom{3n}{n}
\]
}
\end{problem}

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

\iffalse
\newpage

\section{A Puzzle}

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}
