10 passengers in a boat

There are 10 passengers in a boat and among them there is a famous pop star who everybody knows, while he doesn’t know any of the other passengers. The other passengers either know some of the others or they do not. There is an 11th person though, who doesn’t know the singer. In order to determine who he (she) is, he asks one particular passenger, say, Aaron, if he knows some other passenger, say Jenny and Aaron must reply by yes or no.

What is the maximum number of such questions the 11th person must ask so as to determine the singer?

Let’s assume that the 11th person does not know whether the singer is male or female and that the relationships are not mutual (i.e. if Aaron knows Jenny, this doesn’t necessarily mean that Jenny knows Aaron).

If we consider all the pairs (which are not mutual) we have 90 such pairs (each person with each other). Assuming the singer is the $ith$ person, of those, we must deduct all pairs with this person, that is, 9 more pairs. Therefore we have 81 pairs. Let's say the 11th person picks one of the others at random, say the 5th, and asks him if he knows person 1, 2, 3, ... 10. If we are lucky and he doesn't know anyone, then he is the pop star. Otherwise, let's assume he doesn't know persons 2, 3 and 6. He must then ask person 2 if he knows 5, then person 3 if he knows 5 and person 6 if he knows 5 and so on. But this is a never ending story... I am a bit confused! Plus that about 55 years have passed since I finished high school :)

Any ideas??

Solution 1:

Method for 9 questions.

Let $S$ be the set of people who are possibly the pop star.

Asking person $a$ the question "Do you know $b$?" eliminates either $a$ or $b$ from $S$:

• If yes, then $a\not\in S$.
• If no, then $b\not\in S$.

Choose any two people $a,b\in S$ and ask $a$ if he/she knows $b$. Do this 9 times, and you're left with the one pop star.