# Finding the number of combinations.

I have been struggling with this problem for a while. I'd be glad if anyone could help me with this.

My wife and I recently attended a party at which there were three 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?

I understand that the maximum and minimum number of handshakes that can take place are 6 and 0 and that these people must be married. Similarly I get that other pairs should be (5,1) (4,2) and (3,3). What has really been bothering me is that how do I know which pair is me and my wife?

• First, let's remember that there is no statement about the number of people you shook hands with. So, if you think you have concluded that there must be a couple with (3,3) handshakes, who could that be? – Ingix Jan 30 '17 at 11:32
• It was so simple. – theraven Jan 30 '17 at 13:52

Let the handshake count of a person be the number of handshakes that that person has had.

We notice that from the author's point of view, the rest have different handshake counts and that these must range from $0$ to $6$. Since there are $7$ others, their handshake counts must be $0,1,\cdots,5,6$.

Now we consider the author. By Pigeonhole Principle, 8 people having handshake counts ranging from $0$ to $6$, at least 2 must have the same handshake count. But all of the other's have distinct handshake counts, thus the author must have one of the repeated handshake counts.

Since you have concluded that the pairs of handshake counts must be $(6,0)$, $(5,1)$, $(4,2)$ and $(3,3)$, the author must have a handshake count of $3$, and so does his wife.

Since there are total 8 peoples, there will be maximum 6 handshakes and the author will get 7 possibles answers. 0, 1, 2, 3, 4, 5, 6, including author's wife. Now the person who answered 6 mush have shaken hand with persons whose answers are 1,2,3,4,5 including author's wife also.

Now 6 has not shaken hand with 0 that mean 0 is his/her spouse. So they are couple. Here note that author's wife has shaken hands with this person 6. Now since this is a thought experiment we can exclude this couple from our consideration and recount the handshakes as 1-1,2-1,3-1,4-1,5-1 (because 6 had shaken hands with all other persons once). i.e now the handshakes are 0,1,2,3,4 and total there are total 6 peoples including the author and author's wife.

Now repeating the above argument the person 4(who has shaken hand 4 times) must have shaken hand with the author's wife also and the no. of hands shaken by his/her spouse is 0. Now exclude this couple from our consideration and recount the no. of handshakes: it will be 1-1,2-1,3-1 i.e 0,1,2.

Now the person 2 and 0 form a couple and 2 must have shaken hands with the author and the author's wife, the other couple is the author and author's wife. So the author's wife must have shaken hands 3 times.

• You gave me a unique way of thinking about this problem. Go recursive! Thanks man. – theraven Jan 30 '17 at 13:53
• you're welcome!! – Arun Jan 30 '17 at 14:41