Leila and Sahar are attending a dinner party with four other couples. Each attendee knows their partner, but they may or may not know anyone else there. Before the five couples sit down to eat, anyone who doesn’t know each other shakes hands. After everyone sits, Leila makes an observation to the table: “I just noticed that no two of you shook hands the same number of times.” How many hands did Leila and Sahar each shake? (Martin Gardner previously included a variation of this puzzle, attributed to mathematician Lars Bertil Owe, in his Mathematical Games column in the May 1973 issue of Scientific American.)
The maximum number of hands anyone could have shaken is eight—they wouldn’t have shaken their own or their partner’s hand. That leaves exactly nine possible numbers of hands for the nine people other than Leila at the table: 0, 1, 2, 3, 4, 5, 6, 7, 8. You can solve the puzzle by assigning each person a number of handshakes and considering who must be partners with whom. (It might be helpful to draw a diagram of all the handshakes.) Person 8 must have shaken hands with everyone but 0 (because 0 didn’t shake any hands), meaning 0 must be 8’s partner. Then 1 has already used up their handshake with 8, so 7 shakes hands with everyone except 0 and 1. Person 0 already has a partner, so 7’s partner must be 1. We can continue like this, finding that 6 is partnered with 2 and that 5 is partnered with 3. Person 4 is the only one left without a partner, so 4 must be Sahar, Leila’s partner, who has shaken hands four times. Leila has shaken hands with 8, 7, 6 and 5, so Leila has also shaken exactly four hands.
We’d love to hear from you! E-mail us at games@sciam.com to share your experience.