wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> party handshakes
        
(Message started by: mook on Aug 4^th, 2002, 10:45am)

Title: party handshakes
Post by mook on Aug 4^th, 2002, 10:45am

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?

Title: Re: party handshakes
Post by oliver on Aug 5^th, 2002, 12:49am

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?

Title: Re: party handshakes
Post by HammerSandwich on Aug 6^th, 2002, 5:10pm

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.

Title: Re: party handshakes
Post by Paul Bishop on Aug 9^th, 2002, 11:54am

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.

Title: Tidier explanation
Post by TimMann on Aug 28^th, 2002, 10:41pm

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.

Title: Spouse assumption not needed?
Post by rugga on Sep 2^nd, 2002, 3:22am

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.

Title: Re: Spouse assumption not needed?
Post by Icarus on Oct 17^th, 2002, 9:26pm

on 09/02/02 at 03:22:35, 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?

Title: Re: party handshakes
Post by TimMann on Oct 18^th, 2002, 12:13am

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.

Title: Re: party handshakes
Post by TimMann on Oct 18^th, 2002, 12:19am

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.

Title: Re: party handshakes
Post by Icarus on Oct 19^th, 2002, 11:59am

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.

Title: Re: party handshakes
Post by rmsgrey on Jan 25^th, 2005, 6:49am

on 10/19/02 at 11:59:24, Icarus wrote:

... Unless it has fewer than 2 vertices...