Results 1 to 3 of 3

Math Help - number of handshakes in a party

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    37

    number of handshakes in a party

    A collection of n couples attend a party at which a number
    of people shake hands. Suppose that no pair shake hands more than once,
    and no one shakes hands with her partner. At the end of the evening, the
    host asks each of the  2n-1 other people how many hands they shook. She
    receives 2n - 1 di fferent answers. How many hands did the host shake?

    How many did her partner shake?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by sbankica View Post
    A collection of n couples attend a party at which a number
    of people shake hands. Suppose that no pair shake hands more than once,
    and no one shakes hands with her partner. At the end of the evening, the
    host asks each of the  2n-1 other people how many hands they shook. She
    receives 2n - 1 different answers. How many hands did the host shake?

    How many did her partner shake?

    Without even trying to hard the answer is use the pigeon hole principle! -- edit sorry this should say injectivity.

    The answer is n-1. The logic used to it is rather tedious. Here is a quick overview.

    There are 2n people. First, we must use injectivity. 2n-1 people reported 2n-1 different number of handshakes. Since the maximum number of handshakes is 2n-1-1 = 2n-2 a person can make, that means each persons number of handshakes is between 0 and 2n-2. Since there are 2n-1 values between 0 and 2n-2 we must have by injectivity that each person other than the hostess must have a unique number of handshakes between 0 and 2n-2. Label each person (other than the hostess) by their number of handshakes.

    Consider person 2n-2, this person must have handshook everyone except 0, including the hostess. This is because there are 2n-1 possible people other than 2n-2 himself, but 0 is not available. Then consider person 2n-3 this person can not handshake 0 or 1 (1 has reached his maximum allowed handshakes) thus he must have handshook everyone except those 2. Continue this process until you reach person n this person must handshake everyone except people 0, ..., n-2. Now consider person n-1. This person has reached their exact allowed quota of handshakes already. This is true of all people n-1 to 0. Now consider the hostess. She can not be allowed to handshake any additional people for every person has reached their quota of handshakes. Thus she has handshook everyone from 2n-2 to n that is 2n-2 -n + 1 = n -1 people.
    Last edited by gmatt; March 30th 2010 at 11:58 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2009
    Posts
    95
    added the answer to my post above. Is should note by necessity her partner is person n-1. Thus both her and her partner shook n-1 hands.
    Last edited by gmatt; March 31st 2010 at 09:44 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Handshakes
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 16th 2011, 03:46 AM
  2. at the party
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 12th 2010, 09:54 AM
  3. counting handshakes
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 8th 2010, 07:34 AM
  4. Handshakes
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: February 15th 2007, 09:58 PM
  5. Students At the Party
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: January 17th 2007, 06:08 PM

Search Tags


/mathhelpforum @mathhelpforum