Author |
Topic: party handshakes (Read 5300 times) |
|
mook
Newbie
Gender: 
Posts: 15
|
 |
party handshakes
« on: Aug 4th, 2002, 10:45am » |
 Quote  Modify
|
The master of a college and his wife has decided to throw a party and invited N guest and their spouses. On the night of the party, all guests turned up with their spouse, and they all had a great time. When the party was concluding, the master requested all his guests (including his wife, but not himself) to write down the number of persons they shook hands with, and to put the numbers in a box. When the box was opened, he was surprised to find all integers from 0 to 2N inclusive.
Assuming that a person never shake hands with their own spouse and that no one lied, how many hands did the master shake?
I tried this out with two guests.
one person shook 4 hands, not counting their spouse's. It couldn't be the host's spouse, because one of the four others shook zero hands, and she can't count shaking her husband's hand. So let's say guest1(g1) shook 4 people's hands:
g1 shook g2, g2's spouse(s2), the host(h), and the host's spouse's(hs) hands:
g1-g2,s2,h,hs
s1-?
g2-g1
s2-g1
h-g1
hs-g1
since everyone else has shaken at least one hand, s1 must not have shaken anyone's hand:
g1-g2,s2,h,hs(4)
s1-(0)
g2-g1
s2-g1
h-g1
hs-g1
now, who shook 1,2, and 3 hands?
possibilities for 3 hands-
hs-g1,g2,s2(3)
g2-g1,hs(2)
s2-g1,hs(2)
the host's spouse couldn't have shaken three hands because someone only shook one hand
g2-g1,h,hs(3)
s2-g1(1)
hs-g1,g2(2)
h-g1,g2 =2
s2-g1,h,hs(3)
g2-g1(1)
hs-g1,s2(2)
h-g1,s2 =2
either one of these two scenarios work, and i don't think it matters which one you use, so let's say guest two shook 3 hands, that means:
g1-g2,s2,h,hs(4)
s1-(0)
g2-g1,h,hs(3)
s2-g1(1)
hs-g1,g2(2)
h-g1,g2(2)
I do logic, not math so, does the host shake two hands, a number of hands equal to the number of guests, or always the same number of hands as his wife?
for one guest it's:
guest-host, host's spouse(2)
spouse-(0)
Host's spouse-guest(1)
Host-guest(1)
with any amount of guests it's the same, the host shakes an amount equal to the number guests, or N. and I believe also the same number as his wife
right?
|
| « Last Edit: Aug 4th, 2002, 11:01am by mook » |
 IP Logged |
|
|
|
oliver
Newbie
Posts: 25
|
|
Re: party handshakes
« Reply #1 on: Aug 5th, 2002, 12:49am » |
Quote Modify
|
Mook,
this is one of the cases where staring too much on examples hurts the problem solving - at least for me.
Start looking at the corner cases, i.e. the guest who shook 2N hands. How many possibilites does he have altogether to shake hands? So, what do we know now about his wife? Whats then with the guy who shook 2N-1 hands? And his wife?
|
| « Last Edit: Aug 5th, 2002, 12:50am by oliver » |
IP Logged |
|
|
|
HammerSandwich
Newbie
Posts: 8
|
|
Re: party handshakes
« Reply #2 on: Aug 6th, 2002, 5:10pm » |
Quote Modify
|
Thanks for the hints, Oliver, but I'm definitely missing something here. The way I read it, no one's actually required to shake hands with anybody, so the riddle may not actually be solvable...
Now, I do have an answer, but it strikes me as far too obvious. So I've got a question that could help clear it up. Am I right that nobody could have had a bad time?
TIA.
|
|
IP Logged |
|
|
|
Paul Bishop
Guest
|
Here's what I know. The problem is written correctly and there are no semantic twists in it. Everyone is assumed to have answered correctly. The master DOES NOT need to know how many hands he's shaken and if he didn't, he can figure it out. The answer is N.
There are 2N+2 people. 2N+1 people each gave a unique ansswer, so 2N+1 unique answers, which is everyone's answer except the master's. No person can shake hands with more than 2N people, since spouses don't shake, and one doesn't shake himself or herself. The possible answers are 0 to 2N.
Elimination Proof:
Let's say the people who shook *2N* hands and *1* hand are a couple, A & B respectively. That means that A shook everyone else's hand, and B duplicated one of those. So, counting from here, all 2N+2 people would have at least 1 handshake (one person had 2N, one had 2 and the rest had one shake each). That leaves no person having ZERO shakes, which violates the rules. So A's spouse must have given less than one shake (anything else greater than 1 shake would have a similar duplicating result). A's spouse B gave zero shakes.
Now that A & B have been decided, no more handshakes are atrributed to them or it will violate the zero rule or the 2N rule. Similar logic is applied to spouses C & D: if C shakes 2N-1 and D shakes 2, and no more are given to A & B, there is now no-one with only one handshake. So C & D give 2N-1 and 1. Etc.
You wind up with the couples' handshakes paired like this - 2N:0, 2N-1:1, 2N-2:2, 2N-3:3, 2N-4:4 ... N:N. There are exactly N+1 different pairings, which accounts for all 2N+2 people, and only one pair has a duplicate number.
Because the master got all possible 2N+1 distinct answers, by elimination, his own handshakes must be the other possible N. Based on the associations above, that pairs him with the other N, which his wife received.
If the master gave any other number than N shakes, he would have taken one of the unique answers and the answers to his question would have included two 4's, violating the rules of the puzzle.
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Tidier explanation
« Reply #4 on: Aug 28th, 2002, 10:41pm » |
Quote Modify
|
Here's a somewhat more direct explanation.
Let Fred be the person who shook 2N hands. Fred didn't shake his own hand or his spouse's hand, and there are only 2N other people at the party, so Fred shook everyone else's hand. Now let Wilma be the person who shook 0 hands. Everyone other than Fred's spouse shook hands with at least one person, so Wilma must be Fred's spouse.
Now imagine what the party would have been like if Fred and Wilma had stayed home. Each remaining partygoer (including the master) would have shaken exactly one less hand (namely Fred's). So the people who in reality had 1, 2, ..., 2N-1 handshakes would have ended up having only 0, 1, ..., 2N-2 instead. Thus the slips in the hat at the end of this new party have the same property as those at the old one -- they are all distinct and range from 0 up to twice the number of guest couples -- but the master shakes exactly 1 less hand than at the old party.
Because the new party has the same structure as the old one, we can repeat the same procedure again and again until we run out of guests. With each repetition, the master shakes 1 less hand. If we do the procedure a total of N times, we get down to the case where no guests came to the party, there is exactly one slip of paper in the hat (which has a 0 on it and belongs to the master's wife), the master shook 0 hands (as there was no one there to shake with), *and* the master shook exactly N less hands than at the actual party.
Therefore the master shook 0 + N = N hands at the actual party.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
rugga
Newbie
Gender:
Posts: 21
|
|
Spouse assumption not needed?
« Reply #5 on: Sep 2nd, 2002, 3:22am » |
Quote Modify
|
TimMann, great explanation. I think it can even be slightly tweaked
to make no mention of spouses and still get the same answer
(see below). In other words, the question itself could be simplified
to just be about a party with any 2N+1 guests plus the master.
The whole bit about the spouses is unnecessary.
On the other hand, the symmetry between husbands and wives
in the solutions presented here is interesting. Perhaps the original
question could get at this by asking something like "how many
hands did the master shake, and how many hands did his wife
shake?"
Anyway, the spouseless solution would look like this:
Let Fred be the guest who shook 2N hands and let Wilma
be the guest who shook 0 hands. So Fred shook hands with
every person except Wilma. The rest of your proof
follows from the 2nd paragraph on. The only other use
of spouses comes near the end of the proof, when there
is only one guest left and the only slip of paper has a 0:
Quote:| the master shook 0 hands (as there was no one there to shake with) |
|
This can be changed to:
the master shook 0 hands since the only guest shook 0 hands.
This is so close to your original proof that you probably realized
spouses weren't important. But I just wanted to make it
explicit.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Spouse assumption not needed?
« Reply #6 on: Oct 17th, 2002, 9:26pm » |
Quote Modify
|
on Sep 2nd, 2002, 3:22am, rugga wrote:| The whole bit about the spouses is unnecessary. |
|
In the original version of this problem, the master was suprised to discover only that all the answers were different. It was left to the puzzle solver to figure out from this and the spouse rule that every number of handshakes from 0 to 2N must of occured. Apparently by the time William Wu found it, someone had included this first level of deduction into the problem statement itself, without noticing it made the spouse rule irrelevant.
Lars Bertil Owe of Lund, Sweden submitted this puzzle to Martin Gardner, who published it in his Scientific American column some time in the 1970s (the book of collected columns I'm getting this out of does not say when the column was published). Whether Lars invented the puzzle, or merely repeated it, I don't know.
Question: What happens if the master also puts a number in the box. Clearly, we need to drop the spouse rule just to provide enough numbers for every one to be different. Do we still get an answer?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: party handshakes
« Reply #7 on: Oct 18th, 2002, 12:13am » |
Quote Modify
|
Quote:Question: What happens if the master also puts a number in the box. Clearly, we need to drop the spouse rule just to provide enough numbers for every one to be different. Do we still get an answer?
|
|
No. In this variant, there is nothing to distinguish the master from anyone else at the party, so obviously we can't say how many hands the master shook. Any argument that shows the master shook K hands would equally well show that anyone else there shook K hands, so no such argument can be valid unless everyone shook K hands. But we know everyone shook a different number. Therefore we have no idea how many the master shook.
|
| « Last Edit: Oct 18th, 2002, 12:20am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: party handshakes
« Reply #8 on: Oct 18th, 2002, 12:19am » |
Quote Modify
|
Heh. Moreover, the situation in the variant isn't even possible. 2N partygoers each shook a different number of hands? No one shakes his own hand, so the 2N different numbers must range from 0 to 2N-1. So now we've claimed that Mr. Outgoing 2N-1 shook everyone else's hand, while at the same time Ms. Shy 0 didn't shake anyone's hand. Did Ms. Shy shake Mr. Outgoing's hand or not? Either way it's a contradiction.
|
| « Last Edit: Oct 18th, 2002, 12:21am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: party handshakes
« Reply #9 on: Oct 19th, 2002, 11:59am » |
Quote Modify
|
Hmm... I never thought about the master becoming indistinguishable from the guests! My intended answer was that it would be impossible for exactly the second reason you gave. I brought it up because it a basic result in graph theory: Every graph without loops (an edge with same vertex on both ends) or multiple edges (two or more edges between the same pair of vertices) must have at least two vertices with the same number of edges.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: party handshakes
« Reply #10 on: Jan 25th, 2005, 6:49am » |
Quote Modify
|
on Oct 19th, 2002, 11:59am, Icarus wrote:| Hmm... I never thought about the master becoming indistinguishable from the guests! My intended answer was that it would be impossible for exactly the second reason you gave. I brought it up because it a basic result in graph theory: Every graph without loops (an edge with same vertex on both ends) or multiple edges (two or more edges between the same pair of vertices) must have at least two vertices with the same number of edges. |
|
... Unless it has fewer than 2 vertices...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove