Problem 4. (20 points) A guest at a party is a celebrity if this person is known

Question

Problem 4. (20 points) 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. Your task 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 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 uwhether that person is actually a celebrity.

Explanation / Answer

Base Case - When there are 2 people at the party, the number of questions we need would be 2.

Let q,be the questions and n be the number of people

for n=2, q=2

i.e q=2<=3(2-1)  

Hence, base case is satisfied.

Induction steps

Assume that f(k) is true, so for every k people, you can find a celebrity with less than 3(k-1) questions.

Therefore, f(k) <= 3(k-1)

Now, to prove f(k+1) is true.

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, 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
n+1 persons. So, total no of questions which are asked
is

1+3n-3=3n-2

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 n+1
persons. So total questions which were asked to find
this out are

1+3n-3+1=3n-1

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 n+1 persons. So total questions which were
needed to find if there is a celebrity are

1+3n-3+1+1=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, 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
n+1 persons. So, total no of questions which are asked
is

1+3n-3=3n-2
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 n+1
persons. So total questions which were asked to find
this out are

1+3n-3+1=3n-1

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 n+1 persons. So total questions which were
needed to find if there is a celebrity are

q= 1+3n-3+1+1=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 3n=3((n+1)-1). Hence f(n+1)
is true.

THerefore, atmost 3(n-1) questions are needed

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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