Gaby, a good mathematician, thinks of a whole number between 1 and 100 inclusive. What is the least number of questions Jack needs to ask her, and what questions should those be, if he is to work out with absolute certainty Gaby's number. Gaby will answer Jack's questions truthfully, honestly, and to the best of her knowledge, and is only allowed to respond "Yes", "No", or "I don't know".

There is a difference with the apparent duplicate: Gaby has the option to honestly answer "I don't know". It makes a big difference! Puzzle inspired in another elsewhere in this site.

  • 2
    @GordonK: There is a difference: Gaby's option to truthfully answer "I don't know". Makes a big difference! Puzzle inspired in another elsewhere in this site. – Bernardo Recamán Santos Dec 6 at 13:53
  • Ok, then I'm keen to see the intended answer and how a good mathematician's ignorance (and by implication the ignorance of mathematicians in general) can be used to faster reduce the search space! – Gordon K Dec 6 at 13:57
  • I am assuming that what you are asking for is the least amount of questions in order to guarrantee a solution no matter what number Gaby is thinking of? Because if the question is what the least amount of questions that could lead to the correct answer, then clearly 1 is the solution. "Is your number 42?" is a solution if Gaby's number indeed is 42. – Phil Dec 7 at 15:05
  • @Phil: Indeed, least number to guarantee Jack working out the number, the worst come to the worst. I have clarified the issue. – Bernardo Recamán Santos Dec 7 at 15:24
up vote 15 down vote accepted

If

the numbers are between $1$ to $3$

then

use this answer.

If

the numbers are between $1$ to $9$

then

ask "I'm thinking a number between $4$ to $7$, is your number strictly less than my number?"

because

if she says "Yes" that means her number is between $1$ to $3$,
else if she says "I don't know" that means her number is between $4$ to $6$,
else if she says "No" that means her number is between $7$ to $9$,

then

use previous strategy to guess the number between the group of $3$ numbers.

Hence,

We may use this iteratively to split the numbers into $3$ same-size groups, by asking similar questions. We need around $log_3(100) = 5$ questions in total.

  • 1
    A somewhat more intuitive way to think about this is to ask: if $f_1(x)=\begin{cases}\textrm{Yes} & x \leq 33 \\ \text{No} & x \geq 67 \\ \text{I don't know} & \text{otherwise}\end{cases}$, what is $f_1(\text{your number})$? etc. – ace Dec 7 at 14:11
  • 1
    You seem to be an ace in stackexchange formatting...how did you even fit a multi-part function in the comments! – George Menoutis Dec 7 at 14:18
  • @GeorgeMenoutis It's just standard LaTeX, $\begin{cases} value1 & condition1 \\ value2 & condition2 \end{cases}$ – ace Dec 7 at 14:32

This is a partial answer.

The trick is to

Devise a way to map the three options yes/no/I don't know in a way to split a number range to 3 parts. Eg: Find a question about the target number such that the answer would be "no" For 1-33, "yes" for 34-66, and "I don't know" for 67-100

After we establish this, it's just a matter of

Splitting the possible number set to one-third each time

which will take a maximum of

ceil(log3(100))=ceil(4.19...)=5 questions

  • Indeed, and to work out a number between 1 and 1000 would require only 7 such questions (as opposed to 11 "yes or no" questions)! What then are the questions that allow this? – Bernardo Recamán Santos Dec 7 at 12:52
  • Athin's answer covers this, I think, by using a sum between target number and another which is unknow but within known range. – George Menoutis Dec 7 at 13:04

Other answers, especially @athin's, argue convincingly that the target number can be identified with as few as

5

questions, but it remains to show that that is the minimum.

It is. We can see that by observing

in order to distinguish each of 100 possibilities from the others via N questions, we need at least 100 distinct patterns of N answers.

With three possible answers to each of N questions,

there are 3N distinct patterns of answers. 34 = 81 is not enough for our purposes, but 35 = 273 yields nearly three times as many answer patterns as we need.

The minimum number of questions needed is therefore certainly

5

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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