• C++ Programming for Financial Engineering
    Highly recommended by thousands of MFE students. Covers essential C++ topics with applications to financial engineering. Learn more Join!
    Python for Finance with Intro to Data Science
    Gain practical understanding of Python to read, understand, and write professional Python code for your first day on the job. Learn more Join!
    An Intuition-Based Options Primer for FE
    Ideal for entry level positions interviews and graduate studies, specializing in options trading arbitrage and options valuation models. Learn more Join!

Handshakes

pruse

pruse

Joined
5/25/10
Messages
417
Points
53
A cute one:

Mr. and Mrs. Jones invite four other couples over for a party. At the end of the party, Mr. Jones asks everyone else how many people they shook hands with, and finds that everyone gives a different answer. Of course, no one shook hands with his or her spouse and no one shook the same person's hand twice. What was Mrs. Jones' answer?
 
Everybody had a different answer. The maximum of handshakes is 8 and the minimum is 0. Mr Jones asked to 9 other people, so the answer must be between 0 and 8 et all different. (Let's say that the names of the invited 4 couples are A, B, C, D, E, F, G, H)

Suppose that Mrs Jones shook 8 hands. It means that she shook hands to A, B, C, D, E, F, G, H. It also means that none of A, B, C, D, E, F, G, H shook 0 hand. So it's impossible : let's call A the person who shook 8 hands.
A shook hand to everybody except his partner. So everybody except his partner shook at least 1 hand. So his partner is the only one who can answer 0. Let's call her B.

Suppose that Mrs Jones shook 7 hands. It means that she shook hand to everybody except Mr Jones and B. A,C,D,E,F,G,H shook hand to A et Mrs Jones. So nobody between these 9 people shook just 1 hand. So it's impossible : let's call C the person who shook 7 hands.
C shook hand to everybody except (his partner and B). So everybody except (his partner and B) shook at least 2 hands. So his partner is the only one who can answer 1. Let's call her D.

Suppose that Mrs Jones shook 6 hands, 5 hands.... same reasoning
She can only answer 4 and there is a solution to this problem : (A8 B0 C7 D1 E6 F2 G5 H3 Mrs Jones4 and the couples are AB,CD,EF,GH)

I'm sure that somebody got a more elegant solution. :)
 
I was trying for different other cases and it turns out that in general if they invite n people then if among the guest couples someone has done x handshakes then the partner has done (2n-x) hand shakes. Since Mr and Mrs Jones are the only people who can have same number of handshakes so 2n-x=x which gives x=n. I am trying to prove the general case and will post it if I have any luck.
 
sukadeb said:
I was trying for different other cases and it turns out that in general if they invite n people then if among the guest couples someone has done x handshakes then the partner has done (2n-x) hand shakes. Since Mr and Mrs Jones are the only people who can have same number of handshakes so 2n-x=x which gives x=n. I am trying to prove the general case and will post it if I have any luck.
Click to expand...

I think the general case goes something like this:

Assume there are n other couples (n+1 total), so 2n+2 individuals. Since nobody shakes hands with themselves or their partner, the maximum possible number of handshakes by any individual is 2n. Mr Jones gets 2n+1 different answers so the only possibility is that every number of handshakes from 0 to 2n occurs exactly once as an answer.

There is an individual who has shaken 2n hands, that is, every hand except their partner's. Everybody but their partner has then shaken 1 hand and therefore their partner must be the person who shook 0. Let's call them couple number 1.

At this point, we know that every individual shakes hands with couple number 1 exactly once. The problem now reduces to distributing every number between 0 and 2n-2 hand shakes between the remaining n couples. By the same argument as above, there must be a couple number 2 who shake hands 2n-2 and 0 times with everybody but couple 1 (so 2n-1 and 1 times including couple 1 back in)

Inductively, there has to be a couple who shake hands 2n - n = n and n times. Since every individual gave Mr Jones a different answer, the only possibility is that this couple is none other than the Jones themselves.
 
bigband said:
I think the general case goes something like this:

Assume there are n other couples (n+1 total), so 2n+2 individuals. Since nobody shakes hands with themselves or their partner, the maximum possible number of handshakes by any individual is 2n. Mr Jones gets 2n+1 different answers so the only possibility is that every number of handshakes from 0 to 2n occurs exactly once as an answer.

There is an individual who has shaken 2n hands, that is, every hand except their partner's. Everybody but their partner has then shaken 1 hand and therefore their partner must be the person who shook 0. Let's call them couple number 1.

At this point, we know that every individual shakes hands with couple number 1 exactly once. The problem now reduces to distributing every number between 0 and 2n-2 hand shakes between the remaining n couples. By the same argument as above, there must be a couple number 2 who shake hands 2n-2 and 0 times with everybody but couple 1 (so 2n-1 and 1 times including couple 1 back in)

Inductively, there has to be a couple who shake hands 2n - n = n and n times. Since every individual gave Mr Jones a different answer, the only possibility is that this couple is none other than the Jones themselves.
Click to expand...
Yeah Induction seems to be the right way to generalize it. I was trying to find a logical proof for (n,n-x) thing but was not succesful. Induction slept out of my mind.
 
Wait ... there is Mr and Mrs Jones then 4 other couples, so this means there are 10 people in total. Since everyone gives different answers then the only possible range of answers is 0 to 9, each different. But 9 is not possible since a person can't shake hands with themselves, with their spouse, or twice with the same person. The maximum possible is 8. Logically this question doesn't make sense. But it can be assumed that Mr Jones is not included here. So this question may make sense but it is vague at best, or just bad english.
 
I believe it is not correct to start naming the number which Mrs Jones said since we don't know whether she was the last person Mr Jones asked the question. If we had the 9 people and Mrs Jones was asked last then it changes the picture since she was left with only possible number of answers(provided that others have named different figures). If not then suppose she was asked first, then what prevented her to give an arbitrary answer between 0 and 9? In this case others would be left with only limited number of choices to answer. So I think the condition here must be that Mrs Jones was asked after all others had answered the question.

So the only solution which is immediately justified is: Honey, I...I...I just shook hands. That was all.(blush):rolleyes:
 
Back
Top