My wife and i recently attended a party at which there were four other married couples. various handshakes took place. no one shook hands with oneself, nor with one's spouse, and no one shook hands with the same person more than once. after all the handshakes were over, i asked each person, including my wife, how many hands he (or she) had shaken. to my surprise each gave a different answer. how many hands did my wife shake?
Answers
suppose,
You have n 'other' couples; then you are considering n+1 couples all told?
The problem usually is stated as having n couples, no spouses shake hands, and the 2n-1 people other than the host shakes hands with a different number of people. The question is how many handshakes did the hostess have? Let me start you on this version of the problem and you can think if your problem is the same.
If you look at a graph of this situation where people are represented by vertices and handshakes by edges the first few cases, n = 2,3,4 might lead you to conjecture (correctly) that the hostess shakes exactly n-1 hands. In the diagrams below each oval surrounds a couple, each vertex (red dot) is an individual, the edges (green lines) represent handshakes, and the blue number beside an individual indicates how many times that person shook hands.
n=2
n=3
n=4
Try induction; it works but you have to be careful. Assume we've checked things out at the beginning and as an induction hypothesis have that it works for n couples, for some n ≥ 1. When looking at n+1 couples it must be that the people other than the host each shake hands exactly one of 0,1,2,3,...,2n times. (Why?) This means that there's a couple whose number of handshakes is 0 & 2n. (Why?) This can't be the host and hostess. (Why?) Remove this couple form the n+1 couples and the induction hypothesis (with all the correct assumptions on the number of handshakes) applies to the rest. The hostess is among these n pairs and by our hypothesis shakes n-1 hands but she must also shake the hand of the person who shakes 2n hands.Thus in the n+1 couple problem she shakes hands n times as required; thus the result holds for all n ≥ 1.