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 neededAssuming 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?
Best Answer
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.