\problemdata                                                             
        {pigeonhole-1} % latex-friendly label for the prob.
        {pigeonhole principle} % The topic(s) of the problem content.  
        {first part made up (RAD), second part Rosen 4.2.30 (first time use} % Source (if known)                                          
        {S02 cp7M} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
\begin{problemparts}

\problempart Say that I have a regular deck of 52 cards. How many
cards do I need to pull from the deck before I am guaranteed to have
two of the same suite? How many do I need to pull before I am
guaranteed to have two spades? \footnote{Note: there are four suites
(spades, clubs, diamonds and hearts) and there are 13 cards in each
suite.}

\solution{There are four suites, so by the pigeonhole principle, if I
draw five cards I am guaranteed to have two of the same suite. However
it could be a long time before I get two spades --- I could have the
bad luck of first drawing all hearts, clubs and diamonds (39 cards),
but then the next two cards I would draw would be spades. So 41 cards
would guarantee two spades.}

\problempart Prove that at a party where there are at least two
people, there are two people who know the same number of people
there. Assume that ``knowing'' is a two-way relationship.

\solution{Since there are $n$ people, the number of other people a
person could know is between 0 and $n-1$ inclusive. However, both 0
and $n-1$ cannot both occur. If there is a person who knows nobody,
then there cannot be a person who knows everybody. As a result, there
are only $n-1$ choices for how many people a person knows. By the
pigeonhole principle, since we have $n$ people and $n-1$ slots to put
them in, two must end up in the same slot.

{\em NOTE:} This problem can be restated as a graph theorem -- {\em An
undirected graph with $n$ nodes must have at least two nodes with the
same degree!}

}

\end{problemparts}
\end{problem} 

                                 