\problemdata                                                             
        {Handshaking} % latex-friendly label for the prob.
        {Induction} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 2, 5} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
I recently went to a party with my Significant Other; there
were 11 other couples there.  A lot of handshaking happened, but of
course no one shook hands with their Significant Other.  At the end,
it turned out that for every $k$ from $0$ to $22$, someone other than
me had shaken hands with exactly $k$ people.  How many people did I
shake hands with?  Prove your answer.
\bigskip

\solution{
\textbf{Solution}:
We will prove the following for a set of $n$ couples:
\begin{theorem}
Suppose at a party for $n$ couples (total) it turns out that
someone other than me has shaken $k$ hands for every $k$ from $0$ to $2n-2$. 
Then I must have shaken $n-1$ hands.
\end{theorem}

\begin{proof}
By induction on $n$.

\emph{Base case, $n=1$}: There are no other couples. My wife has shaken
$0$ hands (can't shake with me). I have shaken $0$ hands ($=n-1$). (some
party!)

\emph{Induction case}: Assume $P(n-1)$ is true for some $n>1$. To prove
$P(n)$, consider a party with $n$ couples.

Someone has shaken $2n-2$ hands, i.e., with everyone in the room except
themselves and their spouse. Therefore everyone else but this couple has
shaken hands at least once. So the one who hasn't shaken hands at all must
be this person's spouse. $2n-2$ is paired with $0$.  Consider the subparty
of the remaining $n-1$ couples. I must be in this group since there cannot
be two people who shook hands $2n-2$ times or $0$ times. Consider the
number of times this group of people has shaken hands among themselves,
i.e., not counting handshakes with the $2n-2, 0$ couple. Then the number
of handshakes I see is every number between $0$ and $2n-4$. This is
because this group of people has original handshake counts of
$1,2,3,\ldots, 2n-3$. Since everyone shakes the $2n-2$ person's hand once,
we are left with handshake counts of $0,1,\ldots,2n-4$.  This is exactly
the premise of $P(n-1)$. So by the I.H. I must have shaken $n-2$ hands
within this group. Adding the one handshake with the $2n-2, 0$ couple, I
must have shaken a total of $n-1$ hands.

\end{proof}

Note that there are 24 people (12 couples)in this case.  So $n=12$, and
the answer is that I shook 11 hands.
}

\end{problem}
                                 