# finding celebrity at a party

• October 15th 2011, 02:23 AM
issacnewton
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
• October 18th 2011, 10:56 PM
issacnewton
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 ?
• December 13th 2011, 11:45 AM
emakarov
Re: finding celebrity at a party
Quote:

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.