Monday, April 27, 2009

Handshakes puzzle

There is a party with five couples. There is much handshaking at the beginning of the party. No one shakes hand with their own partner, and no one shakes hands twice with the same person.

Later, the host, Martin, asks everyone how many times they shook hands. All of the other nine people remembered exactly how many times, and answered him. Each of the nine answers was a different number!

How many handshakes did Martin himself have at the party?

solution posted

2 comments:

Baumann Eduard said...

Martin shakes hands 4 times.

A possible shaking matrix is:

x t p 1 2 3 4 5 6 7 8
t 0 0 0 1 0 1 0 1 0 1 4
p 0 0 0 1 0 1 0 1 0 1 4
1 0 0 0 0 0 1 0 1 0 1 3
2 1 1 0 0 0 1 0 1 0 1 5
3 0 0 0 0 0 0 0 1 0 1 2
4 1 1 1 1 0 0 0 1 0 1 6
5 0 0 0 0 0 0 0 0 0 1 1
6 1 1 1 1 1 1 0 0 0 1 7
7 0 0 0 0 0 0 0 0 0 0 0
8 1 1 1 1 1 1 1 1 0 0 8

t is Martin, p is his partner
12, 34, 56, 78 are the other couples

Secret Squïrrel said...

I concur with Ed although I think his matrix is the only sol'n rather than simply a possible one.

To explain further; since nobody shook hands with their partner (nor themselves, presumably) the maximum possible handshakes that any one person could have made is 8. Nine different answers means that each of the possible number of handshakes from 0 to 8 is represented (and that Martin must have shaken hands the same number of times as someone else).

Since the person who shook hands with 8 people shook hands with everyone else except their partner, their partner must be the person who shook hands with no-one. This gives the first pairing of 8:0.

Similar reasoning will show that the partner of the person who shook hands 7 times, is the one who shook hands only once (since the others must have shaken hands at least twice - once with person "8" and once with person "7"). This gives the second pairing of 7:1.

Following this same process gives the other pairings - 6:2, 5:3, and 4:4.