KingGeorge
  • KingGeorge
[SOLVED] Here's a neat little combinatorics/graph theory question. Mr. Smith and his wife invited four other couples for a party. When everyone arrived, some of the people in the room shook hands with some of the others. Of course, nobody shook hands with their spouse and nobody shook hands with the same person twice. After that, Mr. Smith asked everyone how many times they shook someone’s hand. He received different answers from everybody. How many times did Mrs. Smith shake someone’s hand? PS. This took me about 5 minutes to solve when I was presented with it. Can you beat me?
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
ParthKohli
  • ParthKohli
8 people.
ParthKohli
  • ParthKohli
I mean, if four other couples were invited, then 4*2 = 8
KingGeorge
  • KingGeorge
it's a little more complicated than that. Remember that everyone shook hands a different number of times (with Mr. Smith as the exception).

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

ParthKohli
  • ParthKohli
Yes, I excluded Mr. Smith.
KingGeorge
  • KingGeorge
Btw, the answer isn't 8.
KingGeorge
  • KingGeorge
Barely legible hint in white LaTeX below.\[ \color{white}{\text{what is the maximum/minimum number of times} \text{someone could shake hands?} }\]
anonymous
  • anonymous
0? Hmm Total of 10 people and Mr. Smith shook hand with everyone right? 8 is the maximum number of handshakes? and you're asking Nine people. So, 0 for Mrs. Smith?
KingGeorge
  • KingGeorge
It isn't 0 either. Perhaps draw a picture, and start drawing handshakes with some random person. Also, remember that he asked 9 people how many handshakes they did. What is the maximum number of handshakes a single person could have?
dumbcow
  • dumbcow
isn't it 0 and 8 as max/min you can't shake your own hand nor your spouse, which leaves 8 people
dumbcow
  • dumbcow
he received a different answer from everyone...0 thru 8 gives 9 different answers right
KingGeorge
  • KingGeorge
That's exactly the conclusion to make. Good work so far.
KingGeorge
  • KingGeorge
Perhaps another leading question. How many people shook hands 8 times? How many 0 times?
dumbcow
  • dumbcow
i believe its impossible for 2 people to have shook hands 0 or 8 times thus mr. smith shook hands somewhere between 1 and 7 following that logic, i will say 4 times is answer
KingGeorge
  • KingGeorge
Correct. Basically, he didn't shake hands with himself or his wife. So that leaves a maximum of 8. One person shook hands 0 times, so max of 7. One person shook hands 1 time, but it had to have been with the person who shook hands 8 times. So we have a max of 6. Continue this way, and you get a max of 4. At this point, if you draw it out, 5 people have shaken hands 0, 1, 2, 3, 4 times, and 4 people have shaken hands 4, 5, 6, 7 times. To fix this, Mr. Smith has to shake hands with the last 4 people. So 4 shakes.
KingGeorge
  • KingGeorge
Can you figure out how many times his wife shook hands?
dumbcow
  • dumbcow
well its not 0 for sure...kinda stuck, i think its possible she could be the one to have shaken 8 times ?
KingGeorge
  • KingGeorge
Suppose she did shake 8 times. Who would have shaken 0 times?
dumbcow
  • dumbcow
oh duh, haha ok so not 8
dumbcow
  • dumbcow
wait i see the pattern for this to work each couple must complement each other so their sum will be 8 handshakes 0,8 1,7 2,6 3,5 4,4 Mrs. smith shook 4 times as well
KingGeorge
  • KingGeorge
Correct again!
KingGeorge
  • KingGeorge
I was actually going to ask "How many times did each couple shake hands next" :P Looks like you already solved that.
dumbcow
  • dumbcow
haha :P these are fun...takes me awhile to visualize the problem
KingGeorge
  • KingGeorge
The way I see it for these problems, is to draw it, and to see what happens at extremes. I.e. seeing what would happen if Mr. Smith shook hands 8 times/0 times. Then try to extrapolate.

Looking for something else?

Not the answer you are looking for? Search for more explanations.