1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number of handshakes in a room

  1. Jul 9, 2014 #1
    1. The problem statement, all variables and given/known data

    as each new person arrives to a meeting, they shake hands of all who are present.

    prove the number [by induction] of occurred handshakes are [tex]\frac{n(n-1)}{2}[/tex]




    3. The attempt at a solution

    if no one shows up then clearly no handshakes are exchanged

    [tex]\frac{0(0-1)}{2} = 0[/tex]

    assuming k people show up, there will be [tex]\frac{k(k-1)}{2}[/tex] handshakes

    now if one more person shows up, that will make a total of k+1 people and because one does not shake their own hand there will be k +1 -1 more shakes than when there where k people .

    there will be

    [tex]\frac{(k+1)(k+1-1)}{2}[/tex] handshakes in total

    [tex]=\frac{k^2+k-k+k+1-1}{2}[/tex]
    [tex]=\frac{k^2-K}{2} + \frac{k+k+1-1}{2}[/tex]
    [tex]=\frac{k(k-1)}{2} + k[/tex]


    is this explained properly?
     
  2. jcsd
  3. Jul 9, 2014 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I don't follow that step. Aren't you assuming what you are trying to prove?

     
  4. Jul 9, 2014 #3
    I felt like I was assuming but wasn't for sure.

    I feel like theres a point where I need to state the new number of handshakes with each incoming person is the new total of people minus 1, so I don't know if I said that at the right time.
     
  5. Jul 9, 2014 #4

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    If there are ##k## people in the room your induction hypotheses says there have been ##\frac{(k-1)(k)}{2}## handshakes. If you now walk into the room, how many handshakes will you add (easy question)?
     
  6. Jul 9, 2014 #5
    I'll add k handshakes

    so start here

    [tex]\frac{k(k-1)}{2} + k[/tex]
     
  7. Jul 9, 2014 #6

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes. Simplify that and see if you get the right formula for ##k+1##. You worked it backwards originally.
     
  8. Jul 9, 2014 #7
    In addition to above, I'm concerned about the basis case, ##n = 0##. In the context of the problem, I'm wondering why you did not chose ##n = 1## or ##n = 2##.
     
  9. Jul 9, 2014 #8
    More explicitly: make certain that the inductive step works when ##k = 0## in the steps LCKurtz mentioned
     
  10. Jul 9, 2014 #9

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    I would have stated this a little differently. If one more person arrives he must shake hands witheach of the k people who were already there so the number of handshakes is increased by k:
    [tex]\frac{k(k-1)}{2}+ k[/tex]

     
  11. Jul 9, 2014 #10

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Apparently you didn't read posts 4, 5, and 6?
     
  12. Jul 9, 2014 #11
    I didn't notice them, rereading all now

    nvm, not to me.

    so many long days, haha
     
    Last edited: Jul 9, 2014
  13. Jul 10, 2014 #12

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Of course this can be done more simply without induction. Each of the n people must shake hands with each of the n-1 others which would give n(n-1) people shaking hands. But each hand shake involves 2 people so that is n(n-1)/2 hand shakes.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Number of handshakes in a room
Loading...