Question:
A couple invites
n - 1other couples to dinner.
Once everyone arrives, each person shakes hands with everyone he doesn’t know.
Then, the host asks everyone how many hands they shook, and each person replies with a different number. Assuming that everyone knows his or her own spouse, how many hands did the hostess shake?
Solution: n-1
The possible numbers of handshakes range from 0 to 2N-2. (2N-1 would require that a person shook hands with every other person at the party, but nobody shook hands with his/her spouse.)
This is 2N-1 different numbers, and the host got 2N-1 different answers, so every number is represented.One person (0) shook no hands, and another (2N-2) shook hands with everybody from all the other couples. This is only possible if these two are a married couple, because otherwise 2N-2 would have had to have shaken 0’s hand.One person (1) shook only 2N-2’s hand, and another (2N-3) shook hands with everybody from all the other couples except 0. Again, these two must be married, or else 2N-3 would have had to have shaken 1’s hand, a contradiction..
.
.Continuing this logic, eventually you pair up all the couples besides the hosts, each one pairing a shook-no-hands-not-already-mentioned person with a shook-all-hands-not-already-mentioned person, the last having shaken N-2 and N hands respectively.
This tells us that the hostess must have shaken N-1 hands, by process of elimination, though we don’t have to use the elimination – since we have N-1 shook-no-other-hands people and N-1 shook-all-other-hands people, we know that both the host and hostess shook hands with exactly one member of each couple – the same ones – and thus each shook N-1 people’s hands
