Here is the question:

Give a simple lowerbound for the number of quesitons asked for the Celebrity Problem.

A celebrity among a group of n people is a person who knows no one but is known by everyone else. Identify a celebrity by only asking questions to people of the following form: Do you know this person?. The goal is to design an efficient algorithm to identify a celebrity or determine that a group has no such person. By efficient we mean asking as few questions as possible. Solution This problem can be solved by reducing the problem size by one a strategy called decrease and conquer, a recursive technique that is useful in solving many problems. In the decrease and conquer strategy, we reduce the problem size by one (or sometimes by more than one) and then recursively apply the same strategy to the reduced problem until the problem size becomes sufficiently small (e.g., 1). Let us illustrate this by solving the celebrity problem. We start with n people. Choose 2 people, say A and B, and ask whether A knows B. If yes, then A cannot be a celebrity and can be eliminated. If no, then B cannot be a celebrity and can be eliminated. This reduces the problem size by one. We repeat the same strategy among the remaining n - 1 people. After n - 1 questions, one person (say X) will remain. If there is a celebrity then it must be this person (Can you see why?). To check whether this person is a celebrity, we ask whether X knows everyone else and whether everyone else knows X. The total number of questions is n-1+n-1+n-1 = 3n - 3. (Actually, we can improve this to 3n 4. See Exercise 2.2.) An even better algorithm can be given! It can be shown that it can be done using 3n [log n] 3 questions and this is the best possible (see Worked Exercise 2.3)! That is, in general, one cannot solve this problem using a lesser number of questions. Note that the performance or complexity in the above problem is naturally deter- mined by the number of questions. The complexity of an algorithm is typically determined by the costliest operation this operation typically dominates the overall cost of the algorithm. A celebrity among a group of n people is a person who knows no one but is known by everyone else. Identify a celebrity by only asking questions to people of the following form: Do you know this person?. The goal is to design an efficient algorithm to identify a celebrity or determine that a group has no such person. By efficient we mean asking as few questions as possible. Solution This problem can be solved by reducing the problem size by one a strategy called decrease and conquer, a recursive technique that is useful in solving many problems. In the decrease and conquer strategy, we reduce the problem size by one (or sometimes by more than one) and then recursively apply the same strategy to the reduced problem until the problem size becomes sufficiently small (e.g., 1). Let us illustrate this by solving the celebrity problem. We start with n people. Choose 2 people, say A and B, and ask whether A knows B. If yes, then A cannot be a celebrity and can be eliminated. If no, then B cannot be a celebrity and can be eliminated. This reduces the problem size by one. We repeat the same strategy among the remaining n - 1 people. After n - 1 questions, one person (say X) will remain. If there is a celebrity then it must be this person (Can you see why?). To check whether this person is a celebrity, we ask whether X knows everyone else and whether everyone else knows X. The total number of questions is n-1+n-1+n-1 = 3n - 3. (Actually, we can improve this to 3n 4. See Exercise 2.2.) An even better algorithm can be given! It can be shown that it can be done using 3n [log n] 3 questions and this is the best possible (see Worked Exercise 2.3)! That is, in general, one cannot solve this problem using a lesser number of questions. Note that the performance or complexity in the above problem is naturally deter- mined by the number of questions. The complexity of an algorithm is typically determined by the costliest operation this operation typically dominates the overall cost of the algorithm