15
$\begingroup$

James Bond is invited to a party with altogether $128$ participants (including Bond himself, the host, and the hostess). At the beginning of the party the host takes James Bond aside and asks him to identify the mysterious Doctor No. It is known that Doctor No knows all the other people at the party, but none of the others does know Doctor No.

James Bond starts asking questions of the following type: he asks some person A, whether A knows some other person B.

What is the minimal number of questions which James Bond needs to ask (in the worst case) to identify the mysterious Doctor No?

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ Shouldn't the puzzle state that all answers are given truthfully by everybody asked? $\endgroup$
    – BmyGuest
    Commented Jan 25, 2015 at 7:30
  • $\begingroup$ @BmyGuest: No, this does not seem to be necessary in this case. One moment's thought shows that in the case of lies, there is no solution at all. $\endgroup$
    – Gamow
    Commented Jan 26, 2015 at 10:33
  • $\begingroup$ Wrong. If only Dr. No lies, you could still find him by asking everybody (else) if he knows everybody. Only one person will be known by nobody.Dr.No. $\endgroup$
    – BmyGuest
    Commented Jan 26, 2015 at 11:26

6 Answers 6

Reset to default
9
$\begingroup$

When James Bond asks A if he knows B:

  • If the answer is yes, this eliminates B as a candidate, since no one is supposed to know Doctor No.

  • If the answer is no, this eliminates A as a candidate, since Doctor No is supposed to know everyone.

James Bond just keeps asking an arbitrary non-eliminated person about another arbitrary non-eliminated person. Every question eliminates one person. At the beginning there are 125 candidates: 128 participants minus James Bond (whom the host knows), minus the host (whom James Bond knows), minus the hostess (whom the host knows).

So the answer is...

...124 questions in the worst case.

Improve this answer
$\endgroup$
1
  • 7
    $\begingroup$ Couldn't this have been posted as a comment to @EFrog's answer? It uses the exact same wording and methodology, with the only differences being the presence of the host/hostess. $\endgroup$
    – mdc32
    Commented Jan 24, 2015 at 21:45
19
$\begingroup$

When you ask A if he knows B:

  • If the answer is yes, this eliminates B as a candidate, since no one is supposed to know No.

  • If the answer is no, this eliminates A as a candidate, since No is supposed to know everyone.

So...

...if you pair everyone up, within 64 questions, you can eliminate 64 people.

And...

...If you group the remaining candidates and pair them up, 32 questions eliminates 32 more people.

Then

16 questions for 16 more;

8 for 8 more;

4 for 4 more;

2 for 2 more; and

1 final question will identify Dr. No.

So...

...if you add them all up, he has to ask 127 questions. Of course, by the time that he has asked that many questions, Dr. No will probably catch on to his scheme and slip out, so that might not be the best way to go about it.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ It might be clearer to note that he clearly has to ask at least $127$ questions, given that he can only eliminate one person per question. Then, your strategy shows that he does not need more than $127$ questions. - That is, this post establishes that there can be no doubt that he could do it in fewer questions. $\endgroup$
    – Milo Brandt
    Commented Jan 24, 2015 at 18:59
  • 3
    $\begingroup$ Assuming, of course, that no one lies at a party :) $\endgroup$
    – Shokhet
    Commented Jan 25, 2015 at 2:34
  • 1
    $\begingroup$ Maybe there's a way to shave this number down a bit; if you consider Bond himself is one of the 128, this essentially makes the participant pool 127. $\endgroup$
    – CodeMoose
    Commented Jan 25, 2015 at 13:56
  • 3
    $\begingroup$ That is, unless we're not ruling out that Bond is Doctor No. What a twist! $\endgroup$
    – CodeMoose
    Commented Jan 25, 2015 at 13:56
7
$\begingroup$

Here's a proof that 127 is optimal, assuming the host and hostess can also be Dr. No:

Imagine a party where nobody knows anyone except for Dr. No, who knows everyone. Querying anyone by Dr. No results in a "No". In the worst case, Dr. No will be the last person you query.

For each person you know a-priori not to be Dr. No, the required number of questions decreases by 1.

Improve this answer
$\endgroup$
3
$\begingroup$

The answer can also be:

One question. James asks the host whether he knows the hostess or not. If he does, he is Dr.No. If he doesn't, she is.

Why do I think this is a valid answer?

The OP could either be a strictly mathematical puzzle, or a brainteaser with a somewhat more loose attitude towards conditions. To be of the first kind, it doesn't seem to be rigorous enough in all statements. In particular: Are all queried persons tell the truth? (Assume yes.). What does knowing somebody mean exactly?

for this reason I think the puzzle can be looked upon in a little more relaxed way, allowing 'common sense' assumptions to be made.

The following 'common sense' assumptions are needed:

- By knowing a person, one means that the name of the person is known to you.
- All people have been invited by the host or the hostess of the party.
- You invite people only if you know them. (I.e you know their name for the invitation.)

Under those assumptions:

Either host or hostess know all and are therefore Dr. No. (But either host or hostess do not know their counterpart!)

And the question then reveals:

If the host knows the hostess, she can't be Dr. No - therefore he is! Otherwise, she has to be Dr. Know.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ There's always the chance that the invitations for the party were for Guest + 1, and while the host may know the guest, they may not know the guest's +1. Also, some of the guests may have been invited by the host while the others were invited by the hostess. Although if we follow your reasoning, James knows either the host or the hostess (since one of them had to have invited him; most likely the host since the host pulls him aside), and since no one at the party knows the Dr, the Dr has to be the one who didn't invite James (probably the hostess). So... zero questions? $\endgroup$
    – EFrog
    Commented Jan 25, 2015 at 15:03
  • $\begingroup$ @EFrog Yeah I was thinking the hostess too... why would Doctor No pull James Bond aside and reveal to him that he, his nemesis was present, and ask him to find him? $\endgroup$
    – Michael
    Commented Jan 25, 2015 at 15:06
  • 1
    $\begingroup$ I usually don't like answers that try to work around the rules of the puzzle, but for this one I think this is an acceptable answer. another argument in favor of your solution is that the host would not ask Bond a question to which he doesn't know the answer himself. if he didn't knew who doctor No is, how could he tell wether or not Bond's answer is correct? $\endgroup$
    – user3453281
    Commented Mar 6, 2015 at 20:28
1
$\begingroup$

I'd go with

zero

given that

this is James Bond and he is trying to find Doctor No. Ideally, just stand and listen for a few minutes and the megalomaniac will probably just identify themselves by their behaviour.

However...

...in practice, the typical procedure would be to seduce the most attractive female in the room, get captured and then Doctor No will identify himself (with a number of complications, gunshots, explosions and at least one car/boat/aircraft/space shuttle chase along the way).

Source:

http://en.wikipedia.org/wiki/Dr.No%28film%29#Plot (and most other Bond films/books)

Improve this answer
$\endgroup$
0
$\begingroup$

Isn't the answer depending on how many people James knows? (The subtraction of host and hostess are an example of that!)

Jame only has to ask people if they know somebody he doesn't know, as otherwise it can't be Dr. No.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The question specifies "worst case", so choose accordingly. $\endgroup$
    – Callidus
    Commented Jan 25, 2015 at 1:29
  • 1
    $\begingroup$ This is the dilemma I have: What is meant by knowing somebody, and does the fact that James was invited and taken aside by the host imply he knows him? In my opinion no, which is why I would second Xnor's answer. $\endgroup$
    – BmyGuest
    Commented Jan 25, 2015 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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