Results 1 to 3 of 3

Math Help - Help

  1. #1
    Junior Member
    Joined
    Mar 2007
    Posts
    40

    Help

    I am trouble trying to figure out why this is possible or not? In a group of 47 people can each person shake hands with exactly nine other people?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,740
    Thanks
    645
    Hello, chadlyter!

    I am trying to figure out why this is possible or not?
    In a group of 47 people, can each person shake hands with exactly 9 other people?

    Let's count the total number of handshakes.

    If each of the 47 people shake hands with exactly 9 other people.
    . . There will be: . 47 \times 9 \:=\:423 handshakes.

    But "X shakes hands with Y" and "Y shakes hands with X" is the same handshake.
    . . Hence, our number is twice as large as it should be.
    . . And, obviously, 423 is not divisible by 2.

    Therefore, it is not possible.

    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,677
    Thanks
    1618
    Awards
    1
    It is really very easy.
    In any graph there must be an even number of odd vertices.
    Try to draw a graph in which an edge is determined by a handshake.
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum