Results 1 to 3 of 3

Math Help - finding celebrity at a party

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    finding celebrity at a party

    Here is a problem

    A guest at a party is a celebrity if this person is known
    by every other guest, but knows none of them. There is at
    most one celebrity at a party, for if there were two, they
    would know each other. A particular party may have no
    celebrity. Your assignment is to find the celebrity, if one
    exists, at a party, by asking only one type of question-
    asking a guest whether they know a second guest. Everyone must
    answer your questions truthfully. That is, if Alice
    and Bob are two people at the party, you can ask
    Alice whether she knows Bob; she must answer correctly.
    Use mathematical induction to show that if there are n
    people at the party, then you can find the celebrity, if there
    is one, with 3(n - 1) questions. [Hint: First ask a ques-
    tion to eliminate one person as a celebrity. Then use the
    inductive hypothesis to identify a potential celebrity. Fi-
    nally, ask two more questions to determine whether that
    person is actually a celebrity.]

    Now, for the base case I took n=2. Suppose I ask Alice
    if she knows Bob and then I ask Bob if he knows Alice.
    There are four possible combinations of answers. Let Y be
    'yes' and N be 'no'. So possibilities are YY,YN,NY,NN.
    In the first case, both know each other , so nobody is
    celebrity. In the second case, Bob is celebrity.In the
    third case, Alice is celebrity. In the last case,
    again nobody is celebrity. So to determine the celebrity
    at this party, I had to ask only two questions. But according
    to the problem, for the n=2 case, 3 questions need to be
    asked. Is there something wrong with the problem. Also
    I am assuming that when I am the one who is asking all
    these questions at the party, I am not included among
    these n persons. Is that a fair assumption ?

    Also I could not understand the hint..

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: finding celebrity at a party

    Hi

    I think the problem is saying that no of questions asked should be
    less than or equal to 3(n-1) when there are n
    people at the party. In that case my base case is correct as only
    2 questions need to be asked , which is less than 3(2-1)=3.
    I finally have understood the meaning of the hint. So consider the
    induction case. Let n\geqslant 2 be arbitrary and suppose
    P(n). To prove P(n+1) suppose there are
    n+1 persons at the party. Lets choose any two persons
    at random and lets call them A and B. Lets ask A if he knows B.
    If A says yes, then A is not celebrity. If A says no, then B is
    not celebrity. This is what the hint means when it says ask
    question to eliminate a celebrity. So we have two cases here
    after the A gives answer.

    Case 1: A says yes, when I ask him if he knows B. So A is not
    a celebrity as per the rules. Consider the n persons other than
    A. Using inductive hypothesis, 3n-3 questions will need
    to be asked to determine if there is a celebrity among these
    n persons. Again two cases arise here.

    Subcase 1: No celebrity is found among these n persons. We already
    know that A is not a celebrity. So there is no celebrity among
    n+1 persons. So, total no of questions which are asked
    is

    1+3n-3=3n-2 \leqslant 3n

    Subcase 2: A celebrity is found among these n persons. Now we still
    don't know if this is indeed the celebrity since we don't know
    if A knows this person. So we ask A if he knows this celebrity.
    Two cases arise here...

    Subsubcase 1: A says no to the question "If he knows this
    supposed celebrity ?"

    That means that person is not celebrity. Since at most
    one celebrity is there, and since A is not a celebrity,
    there is no celebrity at the party of n+1
    persons. So total questions which were asked to find
    this out are

    1+3n-3+1=3n-1\leqslant 3n

    Subsubcase 2:A says yes to the question "If he knows this
    supposed celebrity ?"

    We still don't know if the supposed celebrity knows A. So
    we ask the supposed celebrity if he knows A. If he says 'yes'
    then that supposed celebrity is not a celebrity and then there
    is no celebrity at the party. If he says 'no', then the supposed
    celebrity is indeed a celebrity and there is a celebrity at the
    party of n+1 persons. So total questions which were
    needed to find if there is a celebrity are

    1+3n-3+1+1=3n\leqslant 3n


    Case 2:A says no, when I ask him if he knows B. So B is not a celebrity
    as per the rules. Consider the n persons other than
    B. Using inductive hypothesis, 3n-3 questions will need
    to be asked to determine if there is a celebrity among these
    n persons. Again two cases arise here.

    Subcase 1: No celebrity is found among these n persons. We already
    know that B is not a celebrity. So there is no celebrity among
    n+1 persons. So, total no of questions which are asked
    is

    1+3n-3=3n-2 \leqslant 3n

    Subcase 2:A celebrity is found among these n persons. Now we still
    don't know if this is indeed the celebrity since we don't know
    if B knows this person. So we ask B if he knows this celebrity.
    Two cases arise here...

    Subsubcase 1: B says no to the question "If he knows this
    supposed celebrity ?"

    That means that person is not celebrity. Since at most
    one celebrity is there, and since B is not a celebrity,
    there is no celebrity at the party of n+1
    persons. So total questions which were asked to find
    this out are

    1+3n-3+1=3n-1\leqslant 3n

    Subsubcase 2:B says yes to the question "If he knows this
    supposed celebrity ?"

    We still don't know if the supposed celebrity knows B. So
    we ask the supposed celebrity if he knows B. If he says 'yes'
    then that supposed celebrity is not a celebrity and then there
    is no celebrity at the party. If he says 'no', then the supposed
    celebrity is indeed a celebrity and there is a celebrity at the
    party of n+1 persons. So total questions which were
    needed to find if there is a celebrity are

    1+3n-3+1+1=3n\leqslant 3n



    As all the cases are exhausted, total no of questions which are
    needed to establish if there is a celebrity are always less than
    or equal to 3n=3((n+1)-1). Hence P(n+1)
    is true.


    Is the reasoning correct ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: finding celebrity at a party

    Is the reasoning correct ?
    Yes. After excluding either A or B to apply the inductive hypothesis, the proof proceeds in the same way, so, after excluding a non-celebrity, case 1 and case 2 could be merged to make the proof shorter.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. at the party
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 12th 2010, 10:54 AM
  2. A party was held..
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 20th 2010, 05:43 PM
  3. Represent a party using graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 30th 2009, 03:48 AM
  4. Party Question
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 30th 2008, 05:03 AM
  5. Students At the Party
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: January 17th 2007, 07:08 PM

/mathhelpforum @mathhelpforum