Problem set: Handshakes

Problems::
(1) Determine the number of handshakes in a party of n people if every person shakes hands with every other person
(2) Prove that there are atleast two people with the same number of handshakes
(3) Prove that the number of persons with odd handshake count is even
(4) A couple hosts a party for three other couples, so there are a total of eight people at the party. When people arrive, they start shaking hands. Not everybody shakes everyone else's hand. In fact, nobody shakes hands with his or her partner, and nobody shakes his or her own hand. So, the most hands anyone could shake is 6, and, of course, the least might be zero. After all the hand shaking is over, the host asks the seven other people and finds that they have each shaken a different number of hands. How many hands did the host shake?

Solutions::
(1) Determine the number of handshakes in a party of n people if every person shakes hands with every other person
Solution: Two people for a handshake can be selected from n people in nC2 ways. The total number of handshakes is therefore nC2.

(2) Prove that there are atleast two people with the same number of handshakes
Proof: Suppose the handshake count of every person is different. Maximum handshake count possible is (n-1). Therefore, the distinct handshake counts have to be n-1, n-2, ..., 0 for the n persons. However, if (n-1) is the handshake count for a person, then he must have shaken hands with all other people and handshake count 0 cannot exist - a contradiction. Hence, there must be atleast two people with same handshake count.

(3) Prove that the number of persons with odd handshake count is even
Proof: To begin with, when no hands have been shaken, the total odd handshake count is 0 (even).
Case 1: If two people having odd handshake count shake hands, then both their handshake counts become even and the total odd handshake count has decreased by 2.
Case 2: If a person with odd handshake count shakes hands with a person having even handshake count, the former's handshake count becomes even and the latter's becomes odd. Hence, the total odd handshake count stays the same.
Case 3: If two persons having even handshake count shake hands, then the total odd handshake count increases by 2.

Therefore, the total handshake count either stays the same, or changes by 2. Also, it is even (0) to begin with. Hence, by induction, the number of persons with odd handshake count is even.

(4) Host handshakes problem
Solution: Let the other seven people be p0,p1,...,p6 where p0 has shaken 0 hands, p1 has shaken 1 hand and so on. Let x be the number of hands shaken by the host.

Then, we can go back in time according to the following state sequence:

(0,1,2,3,4,5,6) x
0,(0,1,2,3,4),0 x-1 (p0 and p6 are a couple)
0,0,(0,1,2),0,0 x-2 (p1 and p5 are a couple)
0,0,0,(0),0,0,0 x-3 (p2 and p4 are a couple)

p3 and the host are a couple and (x-3) must be equal to 0. Therefore, x=3.
Hence, the host shook 3 hands and so did his wife.