\problemdata
{S00 tut1}
{intro-logic}
{handshakes}

\begin{problem}
\begin{problemparts}

\problempart
Use induction on $n$ to prove that the following inequality
holds for all integers $n \geq 1$ and for all non-negative real
numbers $x_1, \ldots, x_n$.

\begin{eqnarray*}
(x_1 + x_2 + \ldots + x_n)^2 & \geq & x_1^2 + x_2^2 + \ldots + x_n^2
\end{eqnarray*}


\problempart
{\em Handshakes. } I recently went to a party with my spouse; there
were 11 other married couples there.  A lot of handshaking happened
(but of course no one shook hands with their spouse).  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.

Note that there are 24 people (12 couples) in this case.

\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}

{\em Proof.}
By induction on $n$.

I.H. $P(n)$ : At an $n$ couple party, if someone other than me shakes $k$ 
hands 
for every $k$ from $0$ to $2n-2$ then I must have shaken $n-1$ hands.

Base: $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!)

I.H. Assume $P(n-1)$ is true. 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.
\qed

For $n=12$, the answer is that I shook 11 hands.
}
\end{problemparts}
\end{problem}
 
