Finding the Celebrity at a Party: A Mathematical Induction Approach?

[issacnewton]

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

 

[verty]

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.

This is confusing English, it means you must show that 3(n-1) questions are sufficient to find the celebrity.

 

[issacnewton]

I think 3(n-1) are the minimum no of questions which I need to ask.
So can you see if the problem is wrong or I am wrong ?