Gaby and Jack's Number Guessing Game
up vote
6
down vote
favorite
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.
mathematics arithmetic
asked Dec 6 at 13:41
Bernardo Recamán Santos
2,3231141
add a comment |
up vote
6
down vote
favorite
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.
mathematics arithmetic
asked Dec 6 at 13:41
Bernardo Recamán Santos
2,3231141
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
add a comment |
up vote
6
down vote
favorite
up vote
6
down vote
favorite
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.
mathematics arithmetic
asked Dec 6 at 13:41
Bernardo Recamán Santos
2,3231141
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.
mathematics arithmetic
mathematics arithmetic
asked Dec 6 at 13:41
Bernardo Recamán Santos
2,3231141
asked Dec 6 at 13:41
Bernardo Recamán Santos
2,3231141
edited Dec 7 at 15:19
asked Dec 6 at 13:41
Bernardo Recamán Santos
2,3231141
asked Dec 6 at 13:41
Bernardo Recamán Santos
2,3231141
asked Dec 6 at 13:41
Bernardo Recamán Santos
2,3231141
2,3231141
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
add a comment |
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
2
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
@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
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
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
@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
add a comment |
3 Answers
3
active
oldest
votes
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.
answered Dec 6 at 14:28
athin
6,87612365
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
add a comment |
up vote
2
down vote
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
answered Dec 6 at 14:10
George Menoutis
910211
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
add a comment |
up vote
1
down vote
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
answered Dec 6 at 21:04
John Bollinger
1112
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "559"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f76114%2fgaby-and-jacks-number-guessing-game%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
answered Dec 6 at 14:28
athin
6,87612365
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
add a comment |
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.
answered Dec 6 at 14:28
athin
6,87612365
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
add a comment |
up vote
15
down vote
accepted
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.
answered Dec 6 at 14:28
athin
6,87612365
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.
answered Dec 6 at 14:28
athin
6,87612365
answered Dec 6 at 14:28
athin
6,87612365
answered Dec 6 at 14:28
athin
6,87612365
answered Dec 6 at 14:28
athin
6,87612365
6,87612365
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
add a comment |
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
1
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
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
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
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
@GeorgeMenoutis It's just standard LaTeX,
$begin{cases} value1 & condition1 \ value2 & condition2 end{cases}$– ace
Dec 7 at 14:32
add a comment |
up vote
2
down vote
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
answered Dec 6 at 14:10
George Menoutis
910211
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
add a comment |
up vote
2
down vote
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
answered Dec 6 at 14:10
George Menoutis
910211
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
add a comment |
up vote
2
down vote
up vote
2
down vote
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
answered Dec 6 at 14:10
George Menoutis
910211
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
answered Dec 6 at 14:10
George Menoutis
910211
answered Dec 6 at 14:10
George Menoutis
910211
answered Dec 6 at 14:10
George Menoutis
910211
answered Dec 6 at 14:10
George Menoutis
910211
910211
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
add a comment |
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
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
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
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
add a comment |
up vote
1
down vote
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
answered Dec 6 at 21:04
John Bollinger
1112
add a comment |
up vote
1
down vote
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
answered Dec 6 at 21:04
John Bollinger
1112
add a comment |
up vote
1
down vote
up vote
1
down vote
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
answered Dec 6 at 21:04
John Bollinger
1112
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
answered Dec 6 at 21:04
John Bollinger
1112
answered Dec 6 at 21:04
John Bollinger
1112
answered Dec 6 at 21:04
John Bollinger
1112
answered Dec 6 at 21:04
John Bollinger
1112
1112
add a comment |
add a comment |
Thanks for contributing an answer to Puzzling Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f76114%2fgaby-and-jacks-number-guessing-game%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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