Solution (1/2)

Our subject M obtained answers all different. As he asked 25 people (13 couples but himself), and that these answers are integers, positive or zero, and less than or equal to 24 (12 couples, because each guest greats neither its spouse nor itself), we conclude that the answers are from 0 up to and including 24.

We will attempt to represent the situation graphically. Each column stands for a guest's number of handshake. We will use the following legend:

• The shaken hand is unknown.
• The shaken hand has just been found.
• The shaken hand has already been found before.
• M may have shaken more hands.

What we want to know is:

• How many hands M has shaken.
• Who is the wife W of M. She is necessarily one of the guest 0 to 24.

For the moment, we know nothing. The situation is then the following:

Let's consider the guest 24 and see which hands he has shaken. As he can't have shaken 0's hand, nor his own, he has necessarily shaken the ones of all other guests, that is 1 to 23, as well as M's one.

From this it can be deduced:

• That M shook at least one hand, 24's one.
• That the spouse of 24 can only be 0, the only one guest he did not shake the hand of.

So, a first couple (24,0) is "solved". At this point, the situation is the following:

next page