14
$\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?

$\endgroup$
  • 5
    $\begingroup$ Shouldn't the puzzle state that all answers are given truthfully by everybody asked? $\endgroup$ – BmyGuest Jan 25 '15 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 Jan 26 '15 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 Jan 26 '15 at 11:26
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.

$\endgroup$
  • 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 Jan 24 '15 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.

$\endgroup$
  • 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 Jan 24 '15 at 18:59
  • 3
    $\begingroup$ Assuming, of course, that no one lies at a party :) $\endgroup$ – Shokhet Jan 25 '15 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 Jan 25 '15 at 13:56
  • 3
    $\begingroup$ That is, unless we're not ruling out that Bond is Doctor No. What a twist! $\endgroup$ – CodeMoose Jan 25 '15 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.

$\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.

$\endgroup$
  • 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 Jan 25 '15 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 Jan 25 '15 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 Mar 6 '15 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)

$\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.

$\endgroup$
  • 1
    $\begingroup$ The question specifies "worst case", so choose accordingly. $\endgroup$ – Callidus Jan 25 '15 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 Jan 25 '15 at 7:28

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.