7
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ @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. $\endgroup$
    – Bernardo Recamán Santos
    Dec 6, 2018 at 13:53
  • $\begingroup$ 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! $\endgroup$
    – Gordon K
    Dec 6, 2018 at 13:57
  • $\begingroup$ 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. $\endgroup$
    – Phil
    Dec 7, 2018 at 15:05
  • $\begingroup$ @Phil: Indeed, least number to guarantee Jack working out the number, the worst come to the worst. I have clarified the issue. $\endgroup$
    – Bernardo Recamán Santos
    Dec 7, 2018 at 15:24

3 Answers 3

Reset to default
15
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – user12205
    Dec 7, 2018 at 14:11
  • 3
    $\begingroup$ You seem to be an ace in stackexchange formatting...how did you even fit a multi-part function in the comments! $\endgroup$
    – George Menoutis
    Dec 7, 2018 at 14:18
  • $\begingroup$ @GeorgeMenoutis It's just standard LaTeX, $\begin{cases} value1 & condition1 \\ value2 & condition2 \end{cases}$ $\endgroup$
    – user12205
    Dec 7, 2018 at 14:32
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Bernardo Recamán Santos
    Dec 7, 2018 at 12:52
  • $\begingroup$ Athin's answer covers this, I think, by using a sum between target number and another which is unknow but within known range. $\endgroup$
    – George Menoutis
    Dec 7, 2018 at 13:04
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

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

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