Hand shakes at a party

Printable View

February 27th 2013, 04:24 PM
PBateman

Hand shakes at a party

My roommate and I are having a house party. We invite 15 couples. At the party, everyone must shake hands with everyone whom they do not already know. At the end of the party, I can't remember the number of people I have met, so I go ask all other people at the party how many hands they have shaken, and they each tell me a different number. You do not shake hands with yourself or your 'partner' (the person with whom you came). How many hands did my roommate shake?

Please explain how you got the answer.

Thanks.
February 28th 2013, 02:20 AM
MINOANMAN

Re: Hand shakes at a party

bateman

Think : it is very simple. you have invited 15 couples and you and your roommate you are total 32 persons.

Now you alone you must shake hands with all your invitees who are 31 total therefore the total hand shake you will do will be 31.
Now what you did everyone has to do...and since there are 32 invitees including you the total shake hands apeared to be 32x31= 992
But you must take into consideration that you and the person x ( anyone from the guests) you have shaked hands twice.
therefore you must divide 992 by 2 to find the exact number 496 shakes.
in this shakes is included the shake with your roomate as well.
MINOAS

MINOAS
February 28th 2013, 02:55 AM
Mick

Re: Hand shakes at a party

There are 32 people, so the 31 people asked must've shaken hands between 0 and 30 tîed. Everybody gave a different answer.

The person who didn't shake any hands must've come with the person who shook 31 hands.
The person who shook one hand must've come with the person who shook 29
Likewise 2 and 28
3 and 27, 4 and 26, 5 and 25, 6 and 24, 7 and 23, 8 and 22, 9 and 21, 10 and 20, 11 and 19, 12 and 18, 13 and 17, 14 and 16. That leaves the person who shook 15 hands as your room mate.
February 28th 2013, 03:51 AM
pspss

Re: Hand shakes at a party

Total number of shake hands = n(n – 1)/2
where n is total number of persons
n = 15 × 2 + 2 = 32
shake hands = 32 × 31/2 = 496
----
February 28th 2013, 01:26 PM
PBateman

Re: Hand shakes at a party

Quote:

Originally Posted by Mick

There are 32 people, so the 31 people asked must've shaken hands between 0 and 30 tîed. Everybody gave a different answer.

The person who didn't shake any hands must've come with the person who shook 31 hands.
The person who shook one hand must've come with the person who shook 29
Likewise 2 and 28
3 and 27, 4 and 26, 5 and 25, 6 and 24, 7 and 23, 8 and 22, 9 and 21, 10 and 20, 11 and 19, 12 and 18, 13 and 17, 14 and 16. That leaves the person who shook 15 hands as your room mate.

Thanks for helping, but can you explain how you deduced the fact that, "The person who didn't shake any hands must've come with the person who shook 31 hands."? And how does this imply that my room mate is the person who shook 15 hands?

Sorry for being obtuse.
February 28th 2013, 01:27 PM
PBateman

Re: Hand shakes at a party

Quote:

Originally Posted by MINOANMAN

bateman

Think : it is very simple. you have invited 15 couples and you and your roommate you are total 32 persons.

Now you alone you must shake hands with all your invitees who are 31 total therefore the total hand shake you will do will be 31.
Now what you did everyone has to do...and since there are 32 invitees including you the total shake hands apeared to be 32x31= 992
But you must take into consideration that you and the person x ( anyone from the guests) you have shaked hands twice.
therefore you must divide 992 by 2 to find the exact number 496 shakes.
in this shakes is included the shake with your roomate as well.
MINOAS

MINOAS

I want to know how many hands my room mate shook, not how many hand shakes happened in total (which is, as you said, is very simple). Thanks for giving it a try though.
February 28th 2013, 02:57 PM
Plato

Re: Hand shakes at a party

Quote:

Originally Posted by PBateman

explain how you deduced the fact that, "The person who didn't shake any hands must've come with the person who shook 31 hands."? And how does this imply that my room mate is the person who shook 15 hands?

This is a famous graph theory question.
Here are the rules of handshakes: one does not shake hands with oneself nor with one's partner.
Therefore, the person with 30 handshakes must be partnered with the one having no handshakes.
So the pairs are $(30,0),~(29,1),\cdots,~(16,14)$ leaving your partner to shake 15 hands.
Do you see that you were not one the 31 who reported a number of handshakes.
February 28th 2013, 03:31 PM
PBateman

Re: Hand shakes at a party

Quote:

Originally Posted by Plato

This is a famous graph theory question.
Here are the rules of handshakes: one does not shake hands with oneself nor with one's partner.
Therefore, the person with 30 handshakes must be partnered with the one having no handshakes.
So the pairs are $(30,0),~(29,1),\cdots,~(16,14)$ leaving your partner to shake 15 hands.
Do you see that you were not one the 31 who reported a number of handshakes.

Why is it impossible for someone and his partner to shake 28 and 29 hands respectively? I understand why two people can't both say 29, since the question says everyone tells me a different number, but I still don't understand why the fact that someone can't shake his partners hand implies that the total number of hands a couple shakes adds to thirty. For example, why can't the 30 people I ask each say they shook 0-29 hands inclusive, leaving my roommate as the one who shook 30 hands?
February 28th 2013, 04:45 PM
Plato

Re: Hand shakes at a party

Quote:

Originally Posted by PBateman

Why is it impossible for someone and his partner to shake 28 and 29 hands respectively? I understand why two people can't both say 29, since the question says everyone tells me a different number, but I still don't understand why the fact that someone can't shake his partners hand implies that the total number of hands a couple shakes adds to thirty. For example, why can't the 30 people I ask each say they shook 0-29 hands inclusive, leaving my roommate as the one who shook 30 hands?

Well I did say that this is a well worn graph theory question,
I suggest that you consider a scaled down problem.
Say you and your mate have two other couples in.
That is six people and you find the others have exchanged $\{0,~1,~2,~3,~4\}$ handshakes.
Draw that graph. Pick the one with four handshakes (draw it out).
There is no edge from that vertex to one of the other five vertices. He/she must be partners with the zero vertex.
Move to another vertex of degree three, Draw those edges. Which one is this a partner?
Which vertex are you? Which is your roommate?
February 28th 2013, 04:49 PM
PBateman

Re: Hand shakes at a party

Quote:

Originally Posted by Plato

Well I did say that this is a well worn graph theory question,
I suggest that you consider a scaled down problem.
Say you and your mate have two other couples in.
That is six people and you find the others have exchanged $\{0,~1,~2,~3,~4\}$ handshakes.
Draw that graph. Pick the one with four handshakes (draw it out).
There is no edge from that vertex to one of the other five vertices. He/she must be partners with the zero vertex.
Move to another vertex of degree three, Draw those edges. Which one is this a partner?
Which vertex are you? Which is your roommate?

Thanks for all of your help... I guess I just need to learn more maths before I can understand the solution.

Can you recommend the best way to learn graph theory? I'm still in high school but have taught myself a lot of math before.
February 28th 2013, 06:04 PM
Plato

Re: Hand shakes at a party

Quote:

Originally Posted by PBateman

Thanks for all of your help... I guess I just need to learn more maths before I can understand the solution. Can you recommend the best way to learn graph theory? I'm still in high school but have taught myself a lot of math before.

Look into the textbook Discrete Mathematics with Graph Theory Goodaire & Parmenter.
They are both at Memorial University of Newfoundland.