Handshakes solution

See the original puzzle

Here's a grid showing the unique solution. "M" represents Martin, and "P" represents his partner. Person 1 is partnered with 2, 3 with 4, 5 with 6, and 7 with 8.

The proof of this solution follows.

There are ten people at the party. No one shakes hands with themself or with their partner. Therefore, each person can shake hands with up to eight different people. So when Martin asks everyone how many times they shook hands, each person gives an answer that is between 0 and 8. He got nine different answers, meaning that each number 0-8 was given exactly once.

The person who shook hands 8 times must have shaken hands with everyone at the party but his/her own partner. Therefore, the partner must be the single party-goer who shook hands 0 times.

Similarly, the person who answered 7 must be the partner of the person who answered 1. This is because the person who answered 7 must have shaken hands with everyone except his/her partner, and the person who answered 0. The person who answered 1 must have shaken hands with the person who answered 8, and no one else.

Similarly, the people who answered 6 and 2 must be partnered. The same goes for 5 and 3. The last couple must have both answered 4. One of those people must be Martin, since everyone except Martin gave a different answer to his question.

Therefore, Martin shook hands with four people.

This puzzle was solved by Baumann Eduard and Secret Squirrel together, with one proving possibility, the other proving uniqueness. Hooray for teamwork!