Celebrity problem, discrete math

Question

so for my problem I have

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 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.]

Skipping some steps for the sake of space, I've gotten this far

Basis step - With 2 people at the party, we would need to find out how many questions at most we would need to find a celebrity.

n = 2

2 ≤ 3(2-1)

2 ≤ 3(1)

2 ≤ 3 True. Only 2 questions are needed

Assuming f(k) is true, so for every k people, you can find a celebrity with >less than 3(k-1) questions, assuming one exists.

Prove f(k+1) for k > 1

f(k) ≤ 3(k-1)

f(k+1) ≤ 3((k+1)-1) replace k with k+1 to both sides

f(k+1) ≤ 3(k)

f(k+1) ≤ 3k

Given our hypothesis, this is always true for integers k>1, because 3k >is always a higher degree than our given 3(k-1). Furthermore, 3k is always a >higher degree than k+1.

First off, Am I even doing this right? I find myself lost here so I'm guessing probably not. Where should I be going from here?

Answer 1

Here is how I would prove this. The base case is obviously true as you pointed out, so let us assume that for $n$ people, the number of questions we have to ask is at most $3(n-1)$.

There are $n+1$ people in a room. Ask one person, call him Al, if he knows a second person, call him Bob. Now there are two possibilities, either Al knows Bob or he doesn't.

If Al knows Bob, then Al cannot be a celebrity so examine if there is a celebrity out of the other $n$ people, using the $3(n-1)$ questions. This gives a total of $3(n-1)+1$ questions so far. If there is no celebrity in this group then there are no celebrities in the room. If there is a celebrity in the group, call him Carl. Now ask Carl if he knows Al, and ask Al if he knows Carl. These two questions will reveal if Carl is truly a celebrity. This gives a total of $3(n-1)+1+2 =3((n+1)-1)$ questions the desired result.

If Al does not know Bob, then follow the same procedure as above but exclude Bob instead of Al from the $n$ people, and ask Carl if he knows Bob and ask Bob if he knows Carl if there is a celebrity in that group of $n$ people. This again gives a total of $3((n+1)-1$ questions.

Along with the base case, this proves that for any finite number of people in a room, you can determine if there is a celebrity in the room with at most $3(n-1)$ questions.

Answer 2

In your base case you missed the hint. If you have two people, you can find the celebrity if there is one in only one question-ask A if he knows B. If A says yes, only B can be a celebrity. If A says no, only A can be a celebrity. You don't know yet if that person is a celebrity. Now you need one more question to determine if the candidate is a celebrity.

Now C comes to the party. Let us assume that A said yes, so A is a non-celebrity. I don't ask the second question yet. I ask B if he knows C. Again, I can eliminate one person as a celebrity. For $k$ people, I can ask $k-1$ questions and have only one potential celebrity. That person has $2k-2$ links to other people, at least one of which I have already asked. So with $2k-3$ more questions I know if my candidate is a celebrity, for a total $3k-4$

This is not a classic induction, as if I want the answer for $k+1$ I don't start by finding the answer for $k$. In the classic case, you would say that you find the answer for $k$, then when person $k+1$ arrives you can ask only three more questions and know for $k+1$ In this case, if you don't have a celebrity in the first $k$, it takes a bunch of questions to prove that the next person is a celebrity. I was able to save those, but it presumes I know how many people are coming to the party.

Answer 3

The hint is actually really good. Ask a person (Alice) if she knows bob, if whe knows Bob then Alice can't be a celebrity since celebrities don't know other people, if she doesn't know Bob then there Bob can't be a celebrity, Know we ask the person who we know is not a celebrity to leave the party for a while to get a beer or something.

Now there are $k-1$ people in the party, so by the inductive hypothesis we can figure out who the celebrity is if there is one asking $3(k-2)$ questions. If there is no celebrity then there won't be a celebrity either when we come back, if there is a celebrity in the party at the moment all that is left to check is that he is still a celebrity when Bob rejoins the party, to check this we need only ask the possible celebrity if he knows Bob or not, and ask Bob wether he knows the possible celebrity or not.

All in all we used $3(k-1)$ questions and figured out if there was a celebrity or not, and in the case there was a celebrity we managed to identify the celebrity.