A problem by Atlantic College mathematician Paul Belcher:
Anna and Bert invite n other couples to a dinner party. Before the meal begins, some people shake hands. No one shakes hands with their own partner, no one shakes hands with themselves, and no two people shake hands with each other more than once. Afterward, Anna asks all the other 2n + 1 people how many times they shook hands, and she gets a different answer from each of them. How many times did Anna shake hands?
|
SelectClick for Answer> |
Altogether there are 2n + 2 people at the party. None shakes hands with themselves or their partner, so the maximum number of handshakes that one person could have participated in is 2n, and the minimum is 0. Anna receives a different answer from each of the 2n + 1 people she asks, so the answers she gets must be 0, 1, 2, …, 2n.
Let the person who shook hands 2n times be called Max and the person who shook hands 0 times be called Minie (making no assumptions about gender). Max must have shaken hands with everyone but his or her own partner. Since Max has shaken hands with Anna, Max cannot be Bert and Max’s partner must be Minie.
Now remove Max and Minie and all their handshakes. This decreases by 1 the number of handshakes that each of the others participated in, and leaves us facing essentially the same problem but with n – 1 other couples. If we repeat this process, eventually we’re left with Anna and Bert as the only two people remaining. In that situation, neither of them shakes hands. And since one handshake disappeared as each of the other n couples was removed from the problem, both Anna and Bert have shaken hands n times.
(Paul Belcher, “But What Colour Are Anna’s Eyes?”, Mathematical Gazette 87:509 [July 2003], 322-323.)
|