\problemdata       % Takes 5 *mandatory* arguments
  {hand-shaking}           % latex-friendly label for the prob.
  {induction}              % The topic(s) of the problem content.
  {}                       % Source (if known)
  {S99 tut; S02 cp2F-4}    % Usage (list ones you are aware of).
  {Nick Matsakis, S02}     % Last revision info (author, date).
%from Spring99 tutorial -- cute puzzle on simple induction, maybe skip.

\begin{problem} I recently went to a party with my Significant Other.  There
were at total of $12$ couples at the party.  A lot of handshaking
happened, but of course no one shook hands with more than 22 people,
because no one shook hands with their Significant Other or with
themselves.  At the end, it turned out that no two other people shook
hands with the same number of people.  How many people did I shake hands
with?  Prove it.

\solution{I shake 11 hands.

To see why, we will prove the general result for a set of $n$ couples:
\begin{theorem}\label{shake}
Suppose at a party for exactly $n$ couples, no two other people besides me
shook hands with the same number of people.  Then I must have shaken hands
with $n-1$ people.
\end{theorem}

\begin{proof}
By induction on $n$.  The induction hypothesis, $P(n)$, is
Theorem~\ref{shake}.

\emph{Base case} ($n=1$).  Me and mine are the only couple at the party
(some party \texttt{:-(}).  Since I don't shake hands with my spouse, I
have shaken $0= n-1$ hands.

{Induction case}: Assume $P(n)$ is true for $n\geq 1$ in order to
prove $P(n+1)$.

Consider a party with $n+1$ couples where all the people besides me shake
hands with different numbers of people.

Now there are $2n+1$ people besides me, and the largest number of people
anyone can shake hands with is $2n$.  Since there are only $2n+1$ integers
between 0 and $2n$, and none of the other people shake the same number of
hands, there must be one other person who has shaken $2n$ hands; likewise,
there must be one other person who has shaken 0 hands.  Now the person who
shook $2n$ hands---call this person the \emph{lead shaker}---must have
shaken with everyone in the room except themselves and their spouse.  So
the person who shook 0 hands must be the lead shaker's spouse, and
everyone else, including me, must have shaken the lead shaker's hand.

Now suppose we remove the lead couple, and consider the subparty of the
remaining $n$ couples.  I'm in this subparty since the lead couple were
people other than me.  Consider the number of times other people in this
subparty have shaken hands among themselves, \ie not counting handshakes
with the lead couple.  For each person in the subparty, this number is
exactly one less than before, because we no longer count the shake with
the lead shaker.  So in the subparty, it's still the case that no two
other people shake hands with the same number of people.  This is exactly
the premise of $P(n)$.  So we conclude from $P(n)$ that I must have shaken
$n-1$ hands within the subparty.  Adding the one handshake with the lead
shaker, I must have shaken a total of $n$ hands in the original party with
$n+1$ couples.  So we have proved $P(n+1)$.

\end{proof}

So with $n= 12$ couples, the answer is that I shook $n-1= 11$ hands.}
\end{problem}

