Hi

I think the problem is saying that no of questions asked should be

less than or equal to when there are

people at the party. In that case my base case is correct as only

2 questions need to be asked , which is less than .

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

induction case. Let be arbitrary and suppose

. To prove suppose there are

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, 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

persons. So, total no of questions which are asked

is

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

persons. So total questions which were asked to find

this out are

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 persons. So total questions which were

needed to find if there is a celebrity are

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, 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

persons. So, total no of questions which are asked

is

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

persons. So total questions which were asked to find

this out are

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 persons. So total questions which were

needed to find if there is a celebrity are

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 . Hence

is true.

Is the reasoning correct ?