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 knows Bob; she must answer correctly. Use mathematical induction to show that if there are n people at the party (n is an integer greater than or equal to 2), then you can find the celebrity, if there is one, with (at most) 3(n1) 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 us 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(n1) questions.

Here it is given that

A person is a celebrity if:

Now

Let P(n) be the statement that for n people at a party, then you can find the celebrity(if there is one) with 3(n1) questions

lets try for n= 1,

if there is a single person at the party. Lets call this person Alice.

There are no other people at the party. Therefore, Alice does not know Bob at the party (condition 2).

Likewise,

every other guest knows Alice since there are no other guests (condition 1).

This means that, without asking any questions, we know Alice is a celebrity. Therefore

P(1) = 3(11) = 3(0) = 0 is true.

let us assume that p(k) is true for k

i.e.., meaning that for k people at a party, you can find the celebrity (if there is one) with 3(k1) questions

if it is true for k then it must also true for k+1

then

P(k+ 1) is true, meaning that for k+ 1 people at a party, you can find the celebrity (if there is one) with

3((k+ 1)1) = 3k questions

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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