Mixing
10 passengers in a boat
Clash Royale CLAN TAG#URR8PPP
up vote
10
down vote
favorite
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??
combinatorics
asked 4 hours ago
Salem Ohio
513
New contributor
Salem Ohio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
10
down vote
favorite
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??
combinatorics
asked 4 hours ago
Salem Ohio
513
New contributor
Salem Ohio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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.
– InterstellarProbe
4 hours ago
@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
– Salem Ohio
4 hours ago
add a comment |Â
up vote
10
down vote
favorite
up vote
10
down vote
favorite
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??
combinatorics
asked 4 hours ago
Salem Ohio
513
New contributor
Salem Ohio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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??
combinatorics
combinatorics
asked 4 hours ago
Salem Ohio
513
New contributor
Salem Ohio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
Salem Ohio
513
New contributor
Salem Ohio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 4 hours ago
asked 4 hours ago
Salem Ohio
513
New contributor
Salem Ohio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
Salem Ohio
513
asked 4 hours ago
Salem Ohio
513
513
New contributor
Salem Ohio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Salem Ohio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Salem Ohio is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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.
– InterstellarProbe
4 hours ago
@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
– Salem Ohio
4 hours ago
add a comment |Â
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.
– InterstellarProbe
4 hours ago
@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
– Salem Ohio
4 hours ago
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.
– InterstellarProbe
4 hours ago
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.
– InterstellarProbe
4 hours ago
@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
– Salem Ohio
4 hours ago
@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
– Salem Ohio
4 hours ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
4
down vote
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 $anotin S$.
- If no, then $bnotin S$.
Choose any two people $a,bin S$ and ask $a$ if he/she knows $b$. Do this 9 times, and you're left with the one pop star.
answered 3 hours ago
Matt
522412
add a comment |Â
up vote
0
down vote
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$.
answered 3 hours ago
farruhota
15.2k2734
In the $n=4$ case, if $A$ does not know $B$ then $B$ is not the singer.
– saulspatz
3 hours ago
@saulpatz, good catch, I hope I fixed it.
– farruhota
3 hours ago
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
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 $anotin S$.
- If no, then $bnotin S$.
Choose any two people $a,bin S$ and ask $a$ if he/she knows $b$. Do this 9 times, and you're left with the one pop star.
answered 3 hours ago
Matt
522412
add a comment |Â
up vote
4
down vote
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 $anotin S$.
- If no, then $bnotin S$.
Choose any two people $a,bin S$ and ask $a$ if he/she knows $b$. Do this 9 times, and you're left with the one pop star.
answered 3 hours ago
Matt
522412
add a comment |Â
up vote
4
down vote
up vote
4
down vote
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 $anotin S$.
- If no, then $bnotin S$.
Choose any two people $a,bin S$ and ask $a$ if he/she knows $b$. Do this 9 times, and you're left with the one pop star.
answered 3 hours ago
Matt
522412
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 $anotin S$.
- If no, then $bnotin S$.
Choose any two people $a,bin S$ and ask $a$ if he/she knows $b$. Do this 9 times, and you're left with the one pop star.
answered 3 hours ago
Matt
522412
answered 3 hours ago
Matt
522412
answered 3 hours ago
Matt
522412
answered 3 hours ago
Matt
522412
522412
add a comment |Â
add a comment |Â
up vote
0
down vote
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$.
answered 3 hours ago
farruhota
15.2k2734
In the $n=4$ case, if $A$ does not know $B$ then $B$ is not the singer.
– saulspatz
3 hours ago
@saulpatz, good catch, I hope I fixed it.
– farruhota
3 hours ago
add a comment |Â
up vote
0
down vote
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$.
answered 3 hours ago
farruhota
15.2k2734
In the $n=4$ case, if $A$ does not know $B$ then $B$ is not the singer.
– saulspatz
3 hours ago
@saulpatz, good catch, I hope I fixed it.
– farruhota
3 hours ago
add a comment |Â
up vote
0
down vote
up vote
0
down vote
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$.
answered 3 hours ago
farruhota
15.2k2734
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$.
answered 3 hours ago
farruhota
15.2k2734
edited 3 hours ago
answered 3 hours ago
farruhota
15.2k2734
answered 3 hours ago
farruhota
15.2k2734
answered 3 hours ago
farruhota
15.2k2734
15.2k2734
In the $n=4$ case, if $A$ does not know $B$ then $B$ is not the singer.
– saulspatz
3 hours ago
@saulpatz, good catch, I hope I fixed it.
– farruhota
3 hours ago
add a comment |Â
In the $n=4$ case, if $A$ does not know $B$ then $B$ is not the singer.
– saulspatz
3 hours ago
@saulpatz, good catch, I hope I fixed it.
– farruhota
3 hours ago
In the $n=4$ case, if $A$ does not know $B$ then $B$ is not the singer.
– saulspatz
3 hours ago
In the $n=4$ case, if $A$ does not know $B$ then $B$ is not the singer.
– saulspatz
3 hours ago
@saulpatz, good catch, I hope I fixed it.
– farruhota
3 hours ago
@saulpatz, good catch, I hope I fixed it.
– farruhota
3 hours ago
add a comment |Â
Salem Ohio is a new contributor. Be nice, and check out our Code of Conduct.
Salem Ohio is a new contributor. Be nice, and check out our Code of Conduct.
Salem Ohio is a new contributor. Be nice, and check out our Code of Conduct.
Salem Ohio is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2915652%2f10-passengers-in-a-boat%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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.
– InterstellarProbe
4 hours ago
@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
– Salem Ohio
4 hours ago