## How many hands did Ernie shake?

This is not so much a puzzle, but a first-semester problem in discrete mathematics. Nevertheless, without the aid of graph theory it becomes an interesting and rewarding riddle. It goes like this:

Ernie and his wife went to a dinner party, in which there were other four invited couples.  As it is customary, at the beginning of the party people greeted each other, and some happened to interchange a handshake.  Of course, nobody shook hands with their spouses or with themselves.  After the dinner was over, Ernie’s wife asked everyone: “How many hands did you shake tonight?”  To her surprise, nobody offered the same figure—that is: someone reported not shaking any hands, someone else shook only one other person’s hand, a third person only shook two people’s hands, and so on.

How many hands did Ernie shake that evening?

### Solution

Let us try first a counting method.  We start by labeling each couple in the following fashion:

 $\begin{array}{|r|c||c|l|} \hline E & \hspace{0.5cm} & \times & EW \\ \hline H_1 & &\hspace{0.5cm} & W_1 \\ \hline H_2 & & & W_2 \\ \hline H_3 & & & W_3 \\ \hline H_4 & & & W_4 \\ \hline \end{array}$

This is: $E$ stands for Ernie, $EW$ stands for Ernie’s wife, $H_k$ stands for the husband from couple k, and $W_k$ stands for the wife from couple k.

It does not matter who is who at this point, but let us keep in mind that there are only nine table entries to fill (the symbol $\times$ next to Ernie’s wife indicates that she did not report any number of handshakes).  We need to fill the rest of the table with the number of handshakes that each person reported: 0, 1, 2, 3, 4, 5, 6, 7 and 8.

Let us assume that Ernie did shake eight hands: that would imply that he shook hands with everyone except his own wife, but in this case, it is not possible to assign  zero handshakes to anybody else in the table.  As a consequence, someone different than Ernie’s wife and Ernie gets an 8 in the table. Let us assume this is $W_4$. This fact immediately implies that everybody except $H_4$ received a handshake from $W_4$, and thus we have to assign zero handshakes to $H_4$.

The table looks like this now:

 $\begin{array}{|r|c||c|l|} \hline E & \hspace{0.5cm} & \times & EW \\ \hline H_1 & &\hspace{0.5cm} & W_1 \\ \hline H_2 & & & W_2 \\ \hline H_3 & & & W_3 \\ \hline H_4 & 0 & 8 & W_4 \\ \hline \end{array}$

This method of elimination can be taken further: Infere from the last table that neither Ernie nor his wife could have shaken either one or seven hands. Assign a 1 and a 7 to $H_3$ and $W_3$ respectively. Continue in this fashion, until you get the correct answer. What will that be?

### Miscellaneous

I have seen mention of this puzzle in other sites around. Check these links out: