Here is a problem(adsbygoogle = window.adsbygoogle || []).push({});

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

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Finding celebrity at a party

**Physics Forums | Science Articles, Homework Help, Discussion**