A guest at a party is a celebrity if this person is known by every other guest,

Question

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 knowns 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, it there is one, with 3(n-1) questions. [hint: First ask a question to eliminate one person as a celebrity. Then use the inductive hypothesis to identify a potential celebrity. Finally, ask two more questions to determine whether that person is actually a celebrity.]

Explanation / Answer

Let's consider the basic step.If there are two persons Alice and Bob at the party,we'll just ask them if they know each other. Of one of them answer yes and other as no,then the person who answered no is a celebrity.If both of them answer yes,then there is no celebrity.So, in this case, we need only two questions which is less than 3(2-1)=3

According to induction,assume that the statement is true for n people i.e we need 3(n-1) questions.
Lets' prove it for n+1 people.
Let Alice and Bob be two persons at the party among n+1 people. There are two possibilities,either alice knows bob or she doesnt.If alice knows Bob,then Alice can't be a celebrity,so lets find if there is a celebrity among the n people using 3(n-1) questions. So,here we asked a total of 3(n-1) +1 questions so far.
Now lets consider remaning k people at the party and use induction to find a celebrity among them.If there is no celebrity in the party,then we are done. But if there is a celebrity,C then we need to ask two more questions.We should ask the C if she know the excluded person and ask the excluded person of she knows C. If both of them answer no,then C is a celebrity.
So, here we are asking 3(n-1)+1+2=3((n+1)-1) questions.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.