# A complicated handshake problem

I am struggling with the following problem.
Suppose there are two distinct parties having the same number of people. In the first party, each person shakes hands with every other person in that party exactly once. Then one person leaves and everyone remaining shakes hands with everyone else once again exactly once. This procedure continues (i.e. one person leaves after which the remaining people shake hands again) until there are two people remaining, who shake hands once.
In the second party, a different handshake game is played. One person is selected to be VIP and every non-VIP party member shakes hands with the VIP exactly once. The VIP then leaves the party with one other person and two new people enter the party and both become VIPs. All non-VIPs shake hands with each of these two VIPs exactly once (the VIPs do not shake with each other). Then the two VIPs leave with one other person and three new people enter the party and become VIPs, and every non-VIP at the party shakes with each VIP exactly once (VIPs do not shake with each other). This process continues until only one person remains and shakes with each of the new VIPs (who are one less in number than the original people at the party).
If 165 total handshakes occurred in the the second party, how many total handshakes occurred in the first party?

I am lost in how to approach this problem, particularly in expressing the number of handshakes in the first party. However, for the second party, I gather that the total number of handshakes given $N$ people initially present, expressed as a dot product between two vectors, is $(1, 2,...,N-1) \cdot (N-1, N-2,...,1)$, which must equal 165. I am not sure how to solve for $N$ and approach the first party.

Let $n$ be the number of people at each party. The straightforward way to find $n$ is to write your dot product as

$$\sum_{k=1}^{n-1}k(n-k)=n\sum_{k=1}^{n-1}k-\sum_{k=1}^{n-1}k^2$$

and use formulas that you probably already know to evaluate the two summations in terms of $n$. Then set the resulting polynomial in $n$ equal to $165$ and solve for $n$. Just for fun, I’ll offer a less straightforward but slicker combinatorial approach.

Suppose that you want to choose a $3$-element subset of the set $S=\{0,1,\ldots,n\}$. This set has $n+1$ elements, so it $\binom{n+1}3$ $3$-element subsets. I can also count these subsets according to their middle elements. Say the middle element is $k$; $k$ can be anything from $1$ through $n-1$. There are $k$ members of $S$ less than $k$ and $n-k$ members of $S$ greater than $k$, so there are $k(n-k)$ ways to choose one of each so as to make a $3$-element set with $k$ as its middle member. Summing over $k$, we see that

$$\sum_{k=1}^{n-1}k(n-k)=\binom{n+1}3\;.$$

If $n$ is the number of people at each party, we now know that $\binom{n+1}3=165$, i.e., that

$$\frac{(n+1)n(n-1)}{3!}=165\;,$$

or $(n+1)n(n-1)=990$. The lefthand side is roughly $n^3$, and $10^3=1000$ is pretty close to $990$, so we try $n=10$, and it works: $11\cdot10\cdot9=990$.

The number of handshakes in the first party is actually a little easier to compute. At each stage there is one handshake for each pair of people present, so When $k$ people are present, there are $\binom{k}2$ handshakes. The number of people present runs from $n$ down to $2$, so the total number of handshakes is

$$\sum_{k=2}^n\binom{k}2=\sum_{k=2}^n\frac{k(k-1)}2=\frac12\left(\sum_{k=2}^nk^2-\sum_{k=2}^nk\right)\;.$$

You can evaluate this using the same summation formulas as before or, in a pinch, by actually doing the arithmetic, since we know now that $n=10$. The slick way is to use a combinatorial identity known as the hockey stick identity, which says (in this particular case) that

$$\sum_{k=2}^n\binom{k}2=\binom{n+1}3\;.\tag{1}$$

And with this approach we see that the number of handshakes at the two parties will always be the same so long as the parties start with the same number of guests and use these handshaking schemes!

To prove this particular case of the hockey stick identity, I just notice that the lefthand side of $(1)$ is yet a third way to count the $3$-element subsets of the set $S$ above: it’s what you get when you count them according to their largest element instead of their middle element. The largest element can be anything from $2$ through $n$. If $k$ is the largest element, the other two elements must be chosen from the $k$ members of $S$ less than $k$, and there are $\binom{k}2$ ways to do that. Summing over $k$ then yields the identity $(1)$.

If there are $N$ people at a party they exchange $\binom{N}{2}$ handshakes among them. You can understand that as follows: everyone exchanges exactly one handshake with everybody else. So you can think of each handshake as a $2$-element subset of the set of $n$ people. Thus, counting the number of handshakes is equivalent to counting the number of $2$-element subsets.

So, for your first party, since people leave one-after-the-other, the total number of handshakes is: $$\sum_{k=2}^{N}\binom{k}{2}=\binom{2}{2}+\binom{3}{2}+...+\binom{N-1}{2}+\binom{N}{2}$$ Now, use your result for the second party, solve for $N$ $$\sum_{i=1}^{N-1}i(N-i)= \\ =1\times 9+2\times 8+3\times 7+4\times 6+5\times 5 +6\times 4+7\times 3+8\times2+9\times1=165 \Rightarrow \\ \Rightarrow N=10$$ and plug it in the above formula to calculate $\sum_{k=2}^{N}\binom{k}{2}=\sum_{k=2}^{10}\binom{k}{2}$, to get the result for the first party: $$\sum_{k=2}^{10}\binom{k}{2}=\binom{2}{2}+\binom{3}{2}+...+\binom{9}{2}+\binom{10}{2}= \\ = 1+3+6+10+15+21+28+36+45= 165$$

Note that

$\begin{array}\\ \sum_{k=1}^{n-1}k(n-k) &=\sum_{k=1}^{n-1}(kn-k^2)\\ &=n\sum_{k=1}^{n-1}k-\sum_{k=1}^{n-1}k^2\\ &=\frac{n^2(n-1)}{2}-\frac{(n-1)n(2n-1)}{6}\\ &=\frac{3n^2(n-1)-(n-1)n(2n-1)}{6}\\ &=\frac{n(n-1)(3n-(2n-1))}{6}\\ &=\frac{n(n-1)(n+1)}{6} \end{array}$