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?



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?



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

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: