11
$\begingroup$

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??

$\endgroup$
2
  • $\begingroup$ If Jenny is the name of the singer, but the 11th person does not know who Jenny is, but everyone else knows who Jenny is, then the first person asked would know who Jenny is. You can assume that everyone knows who they are. $\endgroup$ – InterstellarProbe Sep 13 '18 at 14:25
  • $\begingroup$ @InterstellarProbe: The 11th person can only ask any of the other persons (one at a time) if he knows another person (a specific one) and he must answer only by yes or no. I will amend the wording accordingly to avoid confusion. Thanks $\endgroup$ – Salem Ohio Sep 13 '18 at 14:44
6
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

For $n=3$ passengers ($A,B,C$), $C$ will ask $A$ about $B$.

  • If $A$ knows $B$, then $B$ is the singer. So, $m_3=1$ question.
  • If $A$ does not know $B$, then $A$ is the singer. So, $m_3=1$ question.

For $n=4$ passengers ($A,B,C,D$), $D$ will ask $A$ about $B$.

  • If $A$ knows $B$, then $D$ can ignore $A$ (because $A$ is not the singer). Then it is a problem for $n=3$ ($B,C,D$), for which $m_3=1$. So, $m_4=2$.
  • If $A$ does not know $B$, then $B$ is not the singer. $D$ asks $A$ again about $C$.
    • If $A$ does not know $C$, then $A$ is the singer. So, $m_4=2$.
    • If $A$ knows $C$, then $C$ is the singer. So, $m_4=2$.

For $n=5$ passengers ($A,B,C,D,E$), $E$ will ask $A$ about $B$.

  • If $A$ knows $B$, then $A$ (not singer). Then it is a problem for $n=4$ ($B,C,D,E$). So, $m_5=3$.
  • If $A$ does not know $B$, then $B$ (not singer). Then, it is a problem for $n=4$ ($A,C,D,E$). So, $m_5=3$.

So: $m_n=n-2$. Hence, $m_{11}=11-2=9$.

$\endgroup$
2
  • $\begingroup$ In the $n=4$ case, if $A$ does not know $B$ then $B$ is not the singer. $\endgroup$ – saulspatz Sep 13 '18 at 15:17
  • $\begingroup$ @saulpatz, good catch, I hope I fixed it. $\endgroup$ – farruhota Sep 13 '18 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.