Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

KingGeorge Group Title

[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?

  • 2 years ago
  • 2 years ago

  • This Question is Closed
  1. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    8 people.

    • 2 years ago
  2. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    I mean, if four other couples were invited, then 4*2 = 8

    • 2 years ago
  3. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    it's a little more complicated than that. Remember that everyone shook hands a different number of times (with Mr. Smith as the exception).

    • 2 years ago
  4. ParthKohli Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Yes, I excluded Mr. Smith.

    • 2 years ago
  5. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Btw, the answer isn't 8.

    • 2 years ago
  6. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Barely legible hint in white LaTeX below.\[ \color{white}{\text{what is the maximum/minimum number of times} \text{someone could shake hands?} }\]

    • 2 years ago
  7. Ishaan94 Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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?

    • 2 years ago
  8. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    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?

    • 2 years ago
  9. dumbcow Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    isn't it 0 and 8 as max/min you can't shake your own hand nor your spouse, which leaves 8 people

    • 2 years ago
  10. dumbcow Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    he received a different answer from everyone...0 thru 8 gives 9 different answers right

    • 2 years ago
  11. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    That's exactly the conclusion to make. Good work so far.

    • 2 years ago
  12. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Perhaps another leading question. How many people shook hands 8 times? How many 0 times?

    • 2 years ago
  13. dumbcow Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    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

    • 2 years ago
  14. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    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.

    • 2 years ago
  15. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Can you figure out how many times his wife shook hands?

    • 2 years ago
  16. dumbcow Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    well its not 0 for sure...kinda stuck, i think its possible she could be the one to have shaken 8 times ?

    • 2 years ago
  17. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Suppose she did shake 8 times. Who would have shaken 0 times?

    • 2 years ago
  18. dumbcow Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    oh duh, haha ok so not 8

    • 2 years ago
  19. dumbcow Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    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

    • 2 years ago
  20. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    Correct again!

    • 2 years ago
  21. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I was actually going to ask "How many times did each couple shake hands next" :P Looks like you already solved that.

    • 2 years ago
  22. dumbcow Group Title
    Best Response
    You've already chosen the best response.
    Medals 2

    haha :P these are fun...takes me awhile to visualize the problem

    • 2 years ago
  23. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    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.

    • 2 years ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.