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:
What we want to know is:
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:
So, a first couple (24,0) is "solved". At this point, the situation is the following: