another logic puzzle

[desh]

This came up today. I'm not 100% sure the answer I have in mind is unique, but I think it is.

You and your spouse invite 4 other couples over for a dinner party. During the course of the party, many people shake hands with other people, except that no one shakes hands with their partner or themselves. At the end of the party, you realize that each of the other 9 people (that is, everyone but you) shook a different number of hands from each other. How many different hands did you shake?

Again, the answer doesn't involve tricks, like some people shaking with both their left and right hands or shaking the hand of someone not at the party. All comments screened for now, like before. Questions and bad guesses will be unscreened sooner; good guesses and right answers will be unscreened later. No googling allowed! Comments now contain spoilers.

Comments

[sen-ichi-rei.livejournal.com]

confirmed by desh in IM, perhaps I cheat, but I don't.

there are 9 people with 9 possibilities running from 0-8. the only way 0 and 8 can both exist is if they are partners.

i don't know for a fact, but i guessed that the other partners matched up as follows
1&7 2&6 3&5 4&4. So therefore you shook 4 and your spouse/significant other/loverboy shook 4 as well.

[erin.livejournal.com]

I'm going to go with 8 because as the host, I'd imagine you would be greeting people in this manner. Other than your spouse - eight people were present.

[desh]

Nope, that can't work. (Sure, socially you'd probably shake 8 hands, but then you can't end up with the condition that all 9 other people have different handshake numbers.)

[intangiblehugs.livejournal.com]

so each of the 9 other people shook a different number of hands from you and from each other? or just from each other?

rephrased: did you shake the same number of hands as anyone else?

[desh]

Just from each other.

[erin.livejournal.com]

I'm trying to read my book on clouds and for some reason this puzzle keeps coming up in my head.

You could shake hands with up to 8 people.

So that's a 0-8 range - a total of 9 different "numbers"

There are 10 people at the party. 10 is greater than 9. So it's not even possible for everyone to shake a different number of hands, is it?

The only other possibility is that for some reason you shook Bob's hand twice. I don't know, maybe you liked Bob.


Like this:

Couple A1 - 8
Couple A2 - 7
Couple B1 - 6
Couple B2 - 5
Couple C1 - 4
Couple C2 - 3
Couple D1 - 2
Couple D2 - 1

(that's 4 of the 5 couples)
Couple E1 - 0

And Couple E2 is an impossibility because there aren't any "different" numbers left.

So say Couple E2 is me, the host. I can shake anywhere from 0-8 hands and the other 9 will still be different from each other (not from me, but from each other).

I googled this - just now - and it appears the answer is 4. Which doesn't make sense because in all the solutions the assumption is that each couple shook a total of 8. The original problem doesn't state this nor does it state that the host's spouse absolutely shook someone's hand.

So what am I missing? :P

[desh]

See ag5j's answer below (his middle paragraph).

The reason your answer doesn't work: Who are the 8 people that A1 shook hands with? Not A2 and not A1 and not E1...so there aren't even 8 people left. The zero has to be A1's partner.

The "each couple shakes a total of 8" thing ends up being a consequence of the rules of the problem, not something you have to assume going in. And if you don't see this right away (as I didn't and you didn't, but some other commenters did), then it's a really hard problem.

[erin.livejournal.com]

ohhh. That make sense now. Thank you :)

[ag5j.livejournal.com]

assuming a person can have 0 handshakes, and the number of handshakes you have will match the number of handshakes one other person has, then one answer is 4 handshakes.

The long way to reach this is to assuming that everyone except for you will have a unique number of handshakes. This means that one person will have 0 handshakes, 1 person will 1 handshake, 1 person will have 2 handshakes, ...., 1 person will have 8 handshakes. Lets take the person who shook 8 hands first. The only person he did not shake hands with is his wife; because everyone must have a unique handshake number (i.e. there can be only one person with 0 handshakes), she must be the person with 0 handshakes. Now lets pick one of the people who shook hands with mr 8 hand shakes, and designate them as the person who shakes hands with 7 other people. There are only 2 people left who this person who has not shaked hands with, and one of them is ms 0 handshakes. So the remaining person is the wife. Now we take one of the people mr 7 handshakes shook with, and designate them as mr 6 handshakes.....we just keep repeating the process until we reach a point where two people have the same handshake count - this is your answer.

The short way : we can assume that the number of people at the party will always be even (since we are always dealing with couples). The number of handshakes you make will be half the number of you and your spouse's guests (i.e. if there are 10 people at the party, 2 people are you and your spouse, so you have 8 guests, and thus you make 4 handshakes). It should be trivial to prove this as a correct answer, although the proof that this is the only answer would be interesting.

[desh]

Yeah, your last paragraph one was about my thought process when I first heard the problem. It seems to be right, but proving anything about it is tough.

Your other answer is right, of course.

[burr86.livejournal.com]

Four. Solved by brute force. ;)

[desh]

Weirdo.

[desh]

By which I mean, good job.

[burr86.livejournal.com]

I was bored during class. :(

[groovin-reuven.livejournal.com]

If people can't shake their partner's hand or their own, that leaves a maximum of 8 shakes to a person. Given the number of people, we'll number them 8-0.

8 shakes 1-7 and you; (0 is 8's spouse). 7 shakes 8, 2-6, and you. 6 shakes 8,7,5,4,3 and you. 5 shakes 8,7,6,4 and you. 4 shakes 8,7,6,5, 3 shakes 8,7,6. 2 shakes 8,7 and 1 shakes 8, and 0 shakes nobody. That leaves you with shaking the hands of 8,7,6, and 5, so you end up shaking 4 hands. I think that all works out.

While various incarnations of this puzzle have been passed around my office, this is the first time I've heard this exact one.

[desh]

Right, of course, but showing that that's unique is a bit tougher.

[conana.livejournal.com]

Since no one shakes hands with eir spouse, the counts represented will be the integers between 0 and 8, with one number appearing twice. I filled out a binary matrix, which obviously must be symmetric (A equals A-transpose), by filling the lower-right triangle, with the result that 4 appears twice. I would like to have a proof of uniqueness, but do not. Any single handshake added either removes two numbers from the counts leaving three duplicate pairs (or three 4s and a pair), or removes the 4 pair, leaving three 5s, but I have not gone further. Thanks to deled for catching me in several appalling errors.

[desh]

Nice method! Not one I would've thought of.

[bloomable.livejournal.com]

I miss you.

me

[desh]

Aw, I miss you too!

[pato.livejournal.com]

4.

You shake the hand of the guy who shakes everyone's hand, thus eliminating him. He also eliminates the guy who shakes one hand.

So what's left is 7, 6, 5, 4, 3, 2 and yourself.

You shake the guy who shakes 7 hands. 2 gets eliminated by shaking the guy who shakes 8 hands and 7 hands.7 shakes 8, 6, 5, 4, 3, 2 and you.

So what's left is 6, 5, 4, and 3. You've shaken 2 hands.

You shake the guy who shakes 6 hands. He shakes 8, 7, 3, 4, 5, and you. That's 6 handshakes and he's out. 3 has shaken 8, 7, and 6, so he's out.

So what's left is 5 and 4. You've shaken 3 hands.

You shake the guy who shakes 5 hands. He shakes 8, 7, 6, 4, and you. This eliminates 4, who's shaken 8, 7, 6, and 5.

There are no more hands to shake and you've shaken 4 hands.

[desh]

That's basically right. You sort of ignored the whole partner rule, but ended up in the right place anyway.