5. You are at a party attended by n people (not including yourself), and you sus

Question

5. You are at a party attended by n people (not including yourself), and you suspect that there might be a celebrity present. A celebrity is someone known by everyone, but does not know anyone except herself/himself. (Of course everyone knows herself/himself). Your task is to work out if there is a celebrity present, and if so, which of the n people present is a celebrity. To do so, you can ask a person X if they know another person Y (where you choose X and Y when asking the question). (a) [10 marks] Show that your task can always be accomplished by asking no more than 3n 3 such questions, even in the worst case. Hint: Assume you ask A if he knous B. If the answer is yes what can you conclude about A? If the answer is no uhat can you conclude about B? (b) [5 marks] Show that your task can always be accomplished by asking no more than 3n- log2 nJ-2 such questions, even in the worst case.

Explanation / Answer

1. It is proved by mathematical induction

Base Step:

If only one A attended the party. So will not know about others and every others except A knows that A is the celebrity.Without asking any question we came to know that A is the celebrity.

P(1) = 3(1) 3 = 0

Inductive Step:

We assume that P(k) is true

P(k) = 3(k) - 3 is true

Now we have to show P(k + 1) is true using P(k)

There are n+1 persons in the party. Consider two people A and B.There is only 2 possibilities either A knows B or he dose not. If A knows B then A is not the celebrity. => We have to find the celebrity in among other 'n' people attending the party. So totally 3(n -1 ) + 1 question will be asked. If there is a celebrity C the B will ask C and C will ask B. This will reveal C's identity

=> total questions asked so far will be = 3(n-1) + 1 + 2

=3((n+1) - 1)

With the base case, we can find who is the celebrity by asking 3n - 3 questions.

----------------------------------------------------------------------------------------------------------------

Algorithm contains 2 phase - Elimination and verification phase. Initially everyone is suspected to be a celebrity. When a person knows about others then he/she will be ruled out from the suspect list. If n people are there then it is enough for us to find the celebrity by asking n-1 question as every question reduce the suspect list size by 1. A queue is used to implement this. It will contain all n people at start and every time two of them will be taken out for elimination purpose. the person who answer Yes will be eliminated and one who answers No will be pushed back to the queue. => the whole process will take O(n) time.

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

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