\problemdata      
        {counting-2} % latex-friendly label for the prob.
        {Counting} % The topic(s) of the problem content.
        {?} % Source (if known)
        {S02 PS8; S00 PS7} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).


\begin{problem}
On the faculty of a school's EECS department (down the river
somewhere\ldots) there are 14~hackers and 8~theoriticians. 
\begin{problemparts}

\problempart 
How many ways are there to select a committee of 6~members if 
\emph{exactly}~1 hacker must be on the committee? (You may express 
this in terms of binomial coefficients.) 

\solution{
There are $\binom{14}{1}$ ways to choose the hacker and
$\binom{8}{5}$ ways to choose the 5~theoriticians. So, in total, we
have $\binom{14}{1}\binom{8}{5}$ ways to form the committee.
}

\problempart 
How many ways are there to select a committee of 6~members if \emph{at
least}~1 hacker must be on the committee? 
  
\solution{
The easiest way to solve this problem is to count the
complement. There are $\binom{22}{6}$ different committees, and
$\binom{8}{6}$ committees of just theoreticians. So there are
$\binom{22}{6} - \binom{8}{6}$ different possibilities.

Alternatively, we can count all possible combinations of people such 
that there is at least one hacker in every combination, but we must
remember not to count any combination multiple times. We can have
committees with:
\begin{itemize}
\item 1 hacker, 5 theoreticians: $\binom{14}{1}\binom{8}{5}$,
\item 2 hackers, 4 theoreticians: $\binom{14}{2}\binom{8}{4}$,
\item 3 hackers, 3 theoreticians: $\binom{14}{3}\binom{8}{3}$,
\item 4 hackers, 2 theoreticians: $\binom{14}{4}\binom{8}{2}$,
\item 5 hackers, 1 theoretician: $\binom{14}{5}\binom{8}{1}$,
\item 6 hackers, 0 theoreticians: $\binom{14}{6}\binom{8}{0}$.
\end{itemize}
So there are 
$$
\binom{14}{1}\binom{8}{5} + 
\binom{14}{2}\binom{8}{4} + 
\binom{14}{3}\binom{8}{3} + 
\binom{14}{4}\binom{8}{2} + 
\binom{14}{5}\binom{8}{1} + 
\binom{14}{6}\binom{8}{0}
$$ 
different possibilities.
}

\problempart 
How many ways are there to select a committee of 6~members if \emph{no
more than}~2 hackers can be on the committee?  

\solution{
There are again many ways to count this, but the key is to make sure 
that nothing is counted twice. Here is one way:
\begin{itemize}
\item no hacker, 6 theoreticians: $\binom{8}{6}$,
\item 1 hacker, 5 theoreticians: $\binom{14}{1}\binom{8}{5}$,
\item 2 hackers, 4 theoreticians: $\binom{14}{2}\binom{8}{4}$,
\end{itemize}
for a total of 
\begin{equation} \label{eq:sum}
\binom{8}{6}+\binom{14}{1}\binom{8}{5}+\binom{14}{2}\binom{8}{4}
\end{equation}
ways.
}

\problempart
Check that your answers to parts~(b) and~(c) are correct by arguing
that (i)~everything has been counted at least once and that
(ii)~nothing has been counted multiple times. 

\solution{
The idea of this part of the problem is not to give a rigorous proof 
but to be able to argue why someone should believe your answer (why
you should believe your own answer!). We give an argument for
part~(c).

To see why every committee is counted, it suffices to observe that
every committee of no more than 2 hackers must  contain 
\begin{itemize}
\item no hackers at all, or
\item 1 hacker, or
\item 2 hackers.
\end{itemize}
In any one of these three cases, the committe \emph{is} going to be
counted, by the corresponding term in the sum~\eqref{eq:sum}.

To see why no committee is counted more than once, first observe that
no committee can fall into more than one of the three cases above. So,
every committee is counted by exactly one of the terms
in~\eqref{eq:sum}. Moreover: 
\begin{itemize}
\item 
If the committee is counted in by the first term, then it is counted
exactly once, by the definition and relevant theorems concerning
combinations. 

\item
If the committee is counted in by the second term, then it
is counted exactly once, because \emph{the choices that correspond to
the two terms of the product} (choice of the hacker, choice of the
theoriticians) \emph{are not interchangeable} (in the sense explained
in class).

\item 
If the committee is counted in by the third term, the committee is
counted exactly once, again, for reasons similar to the previous
case. 

\end{itemize}
A similar argument can be given for our counting in part~(b).
}

\end{problemparts}
\end{problem}

