Handshakes Problem?

Question

Paul invites 10 couples to a party at his house. He asks everyone present, including his wife, how many people they shook hands with. It turns out that everyone questioned--he didn't question himself, of course--shook hands with a different number of people. If we assume that no one shook hands with his or her partner, how many people did Paul's wife shake hands with? (Remember, Paul did not ask himself any questions)

Source: AcoPS (Zeitz)

There are 11 couples total (Paul and his wife are 1 and then there are the 10 invited couples). In total, there are 22 people. The answer is not 9.

Answer 1

You don't know the whole story, I'll tell it You.

It was long time ago, Paul, a good friend of mine, invited me and my wife to a party. He asked us and his wife the same question and got different answers. This was the situation:
Paul: 1 handshake . . . Paul's wife: 1 handshake
Me: 2 handshakes . . . My wife: 0 handshakes
I shook hands with him and his wife, my wife didn't, she hates handshakes.

Some time later he invited us again together with my brother's family. The situation with questions and answers repeated, the situation with the handshakes being:
Paul's pair: 2 2 /both with me and my brother/
Our pair: 4 0 /I didn't with my wife, of course/
My brother's: 3 1 /he didn't with my wife, already told You that she hates that, his wife with me/.

Time passed and came the party in the question - Paul and his wife did 10 handshakes each - this is the answer - indeed:
Paul's: 10 10
Pair1: 20 0
Pair2: 19 1
Pair3: 18 2
Pair4: 17 3
Pair5: 16 4
Pair6: 15 5
Pair7: 14 6
Pair8: 13 7
Pair9: 12 8
Pair10: 11 9
Receiving 21 different answers from his wife and 20 guests means that these answers were 0,1,2,...20 /the guest with the greatest number - let this be Husband1 - excludes himself and his wife/. Imagine a graph with 22 nodes. Husband1's node will be connected with links with all others, except Wife1, Husband2's node - with all Wife3 to Wife10 and Paul's wife, Husband3's - with all Wife4 to Wife10 and Paul's wife, etc., Paul's node - with all Husbands', Paul's wife's - with all Husbands' and this will be true for arbitrary number of guests - we can interchange Husbands with Wives of course and use neutral terminology of the Graph Theory - both nodes in the top row must be connected to all nodes down in the left column - this is the only possible configuration to meet the conditions /every other such graph will be isomorphic to this one/.
So the number of people Paul's wife will shake hands with, WILL ALWAYS BE EQUAL TO THE NUMBER OF GUEST PAIRS.

Thanks for the very amusing problem!

Answer 2

Every person could shake from 0 to 20 hands (nobody shakes his own hand and the hand of his wife). So total number of possible number of diferrent answers is 21 and that is how many people Paul asked. So there is a person who shaked hands of everyone (exluding himself and spouse) and there is a person who did not shake any hand. It can be only if one partner shaked 20 hands and second partener shaked 0, because any other person from any other pair shaked hands with the first partner. If we drop this pair from consideration we find ourselves in similar case but with 9 pairs because everyone lost one handshake with the first partner from deleted pair. And again there is a pair with one partner who made 18 handshake and second 0. By removing pairs one after another we can see the pattern that each pair has the same sum of handshakes as any other pair. And in original setting this sum is 20. There is one number that does not have pair different from it. It is 10. And this number corresponds to number of handshakes made by Paul's wife.
Answer: 10

Answer 3

since they are the host and the wife does not shake hands with Paul...

the wife shook hands with 9 people.

§