Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding celebrity at a party

  1. Oct 15, 2011 #1
    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..

  2. jcsd
  3. Oct 15, 2011 #2


    User Avatar
    Homework Helper

    This is confusing English, it means you must show that 3(n-1) questions are sufficient to find the celebrity.
  4. Oct 15, 2011 #3
    I think [tex]3(n-1)[/tex] are the minimum no of questions which I need to ask.
    So can you see if the problem is wrong or I am wrong ?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook