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

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 $\displaystyle 3(n-1)$ when there are $\displaystyle 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 $\displaystyle 3(2-1)=3$.

I finally have understood the meaning of the hint. So consider the

induction case. Let $\displaystyle n\geqslant 2$ be arbitrary and suppose

$\displaystyle P(n)$. To prove $\displaystyle P(n+1)$ suppose there are

$\displaystyle 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, $\displaystyle 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

$\displaystyle n+1$ persons. So, total no of questions which are asked

is

$\displaystyle 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 $\displaystyle n+1$

persons. So total questions which were asked to find

this out are

$\displaystyle 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 $\displaystyle n+1$ persons. So total questions which were

needed to find if there is a celebrity are

$\displaystyle 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, $\displaystyle 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

$\displaystyle n+1$ persons. So, total no of questions which are asked

is

$\displaystyle 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 $\displaystyle n+1$

persons. So total questions which were asked to find

this out are

$\displaystyle 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 $\displaystyle n+1$ persons. So total questions which were

needed to find if there is a celebrity are

$\displaystyle 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 $\displaystyle 3n=3((n+1)-1)$. Hence $\displaystyle P(n+1)$

is true.

Is the reasoning correct ?

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.