My April diary included the following brainteaser — an exceptionally nifty one, in my opinion.
Handshakes at a Party
Nicholas and Alexandra went to a reception with ten other couples; each person there shook hands with everyone he or she didn't know. (Obviously, this took place before the COVID-19 epidemic.) Later, Alexandra asked each of the other 21 partygoers with how many people they shook hands, and got a different answer every time.
With how many people did Nicholas shake hands?
I shall assume that every partygoer knows his/her partner, and so does not shake her/his hand. (From here on I'll just use the male pronoun, on the old principle that "the male embraces the female.")
Since no-one shook hands with less than zero other partygoers, or with more than twenty, the answers given by the 21 partygoers Alexandra interrogated must have been the twenty-one numbers 0, 1, 2, 3, …, 18, 19, and 20, in some order.
Let's identify each of the twenty-one by his answer, using "P" for "partygoer," as P0, P1, P2, P3, …, P18, P19, P20. For the sake of completeness, I'll include Alexandra herself in the list as PA.
Consider P20. Did the twenty partygoers he reports having shaken hands with include P0? Obviously not: P0 didn't shake hands with anybody. If none of the twenty partygoers who were strangers to P20 is P0, then P0 must be P20's partner.
Now consider P19. Did the nineteen partygoers P19 shook hands with include P1? No: P1 only shook hands with P20, who shook hands with everybody except his partner P0.
How about the one person (other than his partner) P19 didn't shake hands with? Might that have been P1? No, it was P0, who didn't shake hands with anyone, and who is not P19's partner — he's P20's partner.
So P1 is not one of those P19 shook hands with; and he is also not one of those (other than his partner) that P19 didn't shake hands with. It must therefore be the case that P1 is P19's partner.
Let's try P18. Did he shake hands with P2? No, because P2 only shook hands with
- P20 (because everybody except his partner P0 did), and
- P19 (because everybody except P0 and P19's partner P1 did).
How about the two people (other than his partner) P18 didn't shake hands with? Might one of them have been P2? No, they were P0, who didn't shake hands with anybody, and P1, who only shook hands with P20.
So P2 is not one of those P18 shook hands with; and he is also not one of those (other than his partner) that P18 didn't shake hands with. It must therefore be the case that P2 is P18's partner.
Proceeding like this I can show that on the facts as stated, it must be the case that each Pn arrived at the party partnered with P20−n. Here is the complete guest list.
P20 arrived with P0
P19 arrived with P1
P18 arrived with P2
P17 arrived with P3
P16 arrived with P4
P15 arrived with P5
P14 arrived with P6
P13 arrived with P7
P12 arrived with P8
P11 arrived with P9
P10 arrived with P10
Wait, what? Plainly that last line should read:
P10 arrived with PA
Otherwise, when Alexandra interrogated that couple, she would have got two identical answers, contradicting the facts as stated.
Answer: Nicholas shook hands with ten people.