What is the most efficient way of determining a date of birth using yes/no questions?
1
$begingroup$
First question here on StackExchange! Sorry if this question is not quite of the correct style - please let me know if so.
Anyway, here's the context. I'm trying to write a program to determine a date of birth (not the year, just the day/month) in as few yes/no questions as possible. Now, the best I can do is a maximum of 13 questions for 31st of December, and 6 questions for 1st of January.
I'm not too great at maths, so I'd be alarmed if 13 is in fact the lowest maximum possible. Is there anyone out there who knows the answer (and if not, could explain how they tackle the problem of finding out)?
PS, sorry for the tags.. I have no idea what this question would be tagged as!
optimization
asked Oct 22 '14 at 21:41
CathalCathal
83
$endgroup$
add a comment |
1
$begingroup$
First question here on StackExchange! Sorry if this question is not quite of the correct style - please let me know if so.
Anyway, here's the context. I'm trying to write a program to determine a date of birth (not the year, just the day/month) in as few yes/no questions as possible. Now, the best I can do is a maximum of 13 questions for 31st of December, and 6 questions for 1st of January.
I'm not too great at maths, so I'd be alarmed if 13 is in fact the lowest maximum possible. Is there anyone out there who knows the answer (and if not, could explain how they tackle the problem of finding out)?
PS, sorry for the tags.. I have no idea what this question would be tagged as!
optimization
asked Oct 22 '14 at 21:41
CathalCathal
83
$endgroup$
add a comment |
1
1
1
$begingroup$
First question here on StackExchange! Sorry if this question is not quite of the correct style - please let me know if so.
Anyway, here's the context. I'm trying to write a program to determine a date of birth (not the year, just the day/month) in as few yes/no questions as possible. Now, the best I can do is a maximum of 13 questions for 31st of December, and 6 questions for 1st of January.
I'm not too great at maths, so I'd be alarmed if 13 is in fact the lowest maximum possible. Is there anyone out there who knows the answer (and if not, could explain how they tackle the problem of finding out)?
PS, sorry for the tags.. I have no idea what this question would be tagged as!
optimization
asked Oct 22 '14 at 21:41
CathalCathal
83
$endgroup$
First question here on StackExchange! Sorry if this question is not quite of the correct style - please let me know if so.
Anyway, here's the context. I'm trying to write a program to determine a date of birth (not the year, just the day/month) in as few yes/no questions as possible. Now, the best I can do is a maximum of 13 questions for 31st of December, and 6 questions for 1st of January.
I'm not too great at maths, so I'd be alarmed if 13 is in fact the lowest maximum possible. Is there anyone out there who knows the answer (and if not, could explain how they tackle the problem of finding out)?
PS, sorry for the tags.. I have no idea what this question would be tagged as!
optimization
optimization
asked Oct 22 '14 at 21:41
CathalCathal
83
asked Oct 22 '14 at 21:41
CathalCathal
83
asked Oct 22 '14 at 21:41
CathalCathal
83
asked Oct 22 '14 at 21:41
CathalCathal
83
asked Oct 22 '14 at 21:41
CathalCathal
83
83
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
4
$begingroup$
Note that $256 lt 366 le 512$. You can distinguish between $512=2^9$ possibilities with nine questions.
edited Jan 2 at 0:55
PyRulez
5,00722471
answered Oct 22 '14 at 21:44
Mark BennetMark Bennet
82k984182
$endgroup$
$begingroup$
Thanks! Could you explain where you got that inequality from?
$endgroup$
– Cathal
Oct 22 '14 at 21:59
$begingroup$
The most obvious arrangement for nine questions would entail a sequence conditioned upon the answers to earlier questions, in a well-known high/low arrangement. With some ingenuity the month could be found with four fixed questions (asked all at once) and the day of month with five fixed questions (also asked at the same time).
$endgroup$
– hardmath
Oct 22 '14 at 22:00
1
$begingroup$
@Cathal If you have yes/no questions, each question can at best reduce the search space by a half - so with a binary search you naturally turn to powers of two. Certain weighing problems on balances have three options (either side heavier, or both sides equal) - for these a power of three is indicated. Here you can attain $2^9$ by indexing the options with integers and asking about the digits in the binary expansion - is the first digit a zero etc.
$endgroup$
– Mark Bennet
Oct 22 '14 at 22:05
$begingroup$
Thank you both very much. I have accepted Mark's answer. Now.. to go about asking the right questions!
$endgroup$
– Cathal
Oct 23 '14 at 14:29
$begingroup$
@Cathal You need each question to divide the search space by as near to half as possible (there is a little flexibility if you are away from a power of two), and particularly to avoid a division in which the size of one part falls just below a power of $2$ while the size of the other part falls just above it (the part which goes over will then need an extra question). With 366 possible dates you have a bit of leeway.
$endgroup$
– Mark Bennet
Oct 23 '14 at 15:57
|
show 2 more comments
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
});
}
});
draft saved
draft discarded
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%2fmath.stackexchange.com%2fquestions%2f986555%2fwhat-is-the-most-efficient-way-of-determining-a-date-of-birth-using-yes-no-quest%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
4
$begingroup$
Note that $256 lt 366 le 512$. You can distinguish between $512=2^9$ possibilities with nine questions.
edited Jan 2 at 0:55
PyRulez
5,00722471
answered Oct 22 '14 at 21:44
Mark BennetMark Bennet
82k984182
$endgroup$
$begingroup$
Thanks! Could you explain where you got that inequality from?
$endgroup$
– Cathal
Oct 22 '14 at 21:59
$begingroup$
The most obvious arrangement for nine questions would entail a sequence conditioned upon the answers to earlier questions, in a well-known high/low arrangement. With some ingenuity the month could be found with four fixed questions (asked all at once) and the day of month with five fixed questions (also asked at the same time).
$endgroup$
– hardmath
Oct 22 '14 at 22:00
1
$begingroup$
@Cathal If you have yes/no questions, each question can at best reduce the search space by a half - so with a binary search you naturally turn to powers of two. Certain weighing problems on balances have three options (either side heavier, or both sides equal) - for these a power of three is indicated. Here you can attain $2^9$ by indexing the options with integers and asking about the digits in the binary expansion - is the first digit a zero etc.
$endgroup$
– Mark Bennet
Oct 22 '14 at 22:05
$begingroup$
Thank you both very much. I have accepted Mark's answer. Now.. to go about asking the right questions!
$endgroup$
– Cathal
Oct 23 '14 at 14:29
$begingroup$
@Cathal You need each question to divide the search space by as near to half as possible (there is a little flexibility if you are away from a power of two), and particularly to avoid a division in which the size of one part falls just below a power of $2$ while the size of the other part falls just above it (the part which goes over will then need an extra question). With 366 possible dates you have a bit of leeway.
$endgroup$
– Mark Bennet
Oct 23 '14 at 15:57
|
show 2 more comments
4
$begingroup$
Note that $256 lt 366 le 512$. You can distinguish between $512=2^9$ possibilities with nine questions.
edited Jan 2 at 0:55
PyRulez
5,00722471
answered Oct 22 '14 at 21:44
Mark BennetMark Bennet
82k984182
$endgroup$
$begingroup$
Thanks! Could you explain where you got that inequality from?
$endgroup$
– Cathal
Oct 22 '14 at 21:59
$begingroup$
The most obvious arrangement for nine questions would entail a sequence conditioned upon the answers to earlier questions, in a well-known high/low arrangement. With some ingenuity the month could be found with four fixed questions (asked all at once) and the day of month with five fixed questions (also asked at the same time).
$endgroup$
– hardmath
Oct 22 '14 at 22:00
1
$begingroup$
@Cathal If you have yes/no questions, each question can at best reduce the search space by a half - so with a binary search you naturally turn to powers of two. Certain weighing problems on balances have three options (either side heavier, or both sides equal) - for these a power of three is indicated. Here you can attain $2^9$ by indexing the options with integers and asking about the digits in the binary expansion - is the first digit a zero etc.
$endgroup$
– Mark Bennet
Oct 22 '14 at 22:05
$begingroup$
Thank you both very much. I have accepted Mark's answer. Now.. to go about asking the right questions!
$endgroup$
– Cathal
Oct 23 '14 at 14:29
$begingroup$
@Cathal You need each question to divide the search space by as near to half as possible (there is a little flexibility if you are away from a power of two), and particularly to avoid a division in which the size of one part falls just below a power of $2$ while the size of the other part falls just above it (the part which goes over will then need an extra question). With 366 possible dates you have a bit of leeway.
$endgroup$
– Mark Bennet
Oct 23 '14 at 15:57
|
show 2 more comments
4
4
4
$begingroup$
Note that $256 lt 366 le 512$. You can distinguish between $512=2^9$ possibilities with nine questions.
edited Jan 2 at 0:55
PyRulez
5,00722471
answered Oct 22 '14 at 21:44
Mark BennetMark Bennet
82k984182
$endgroup$
Note that $256 lt 366 le 512$. You can distinguish between $512=2^9$ possibilities with nine questions.
edited Jan 2 at 0:55
PyRulez
5,00722471
answered Oct 22 '14 at 21:44
Mark BennetMark Bennet
82k984182
edited Jan 2 at 0:55
PyRulez
5,00722471
edited Jan 2 at 0:55
PyRulez
5,00722471
edited Jan 2 at 0:55
PyRulez
5,00722471
5,00722471
answered Oct 22 '14 at 21:44
Mark BennetMark Bennet
82k984182
answered Oct 22 '14 at 21:44
Mark BennetMark Bennet
82k984182
answered Oct 22 '14 at 21:44
Mark BennetMark Bennet
82k984182
82k984182
$begingroup$
Thanks! Could you explain where you got that inequality from?
$endgroup$
– Cathal
Oct 22 '14 at 21:59
$begingroup$
The most obvious arrangement for nine questions would entail a sequence conditioned upon the answers to earlier questions, in a well-known high/low arrangement. With some ingenuity the month could be found with four fixed questions (asked all at once) and the day of month with five fixed questions (also asked at the same time).
$endgroup$
– hardmath
Oct 22 '14 at 22:00
1
$begingroup$
@Cathal If you have yes/no questions, each question can at best reduce the search space by a half - so with a binary search you naturally turn to powers of two. Certain weighing problems on balances have three options (either side heavier, or both sides equal) - for these a power of three is indicated. Here you can attain $2^9$ by indexing the options with integers and asking about the digits in the binary expansion - is the first digit a zero etc.
$endgroup$
– Mark Bennet
Oct 22 '14 at 22:05
$begingroup$
Thank you both very much. I have accepted Mark's answer. Now.. to go about asking the right questions!
$endgroup$
– Cathal
Oct 23 '14 at 14:29
$begingroup$
@Cathal You need each question to divide the search space by as near to half as possible (there is a little flexibility if you are away from a power of two), and particularly to avoid a division in which the size of one part falls just below a power of $2$ while the size of the other part falls just above it (the part which goes over will then need an extra question). With 366 possible dates you have a bit of leeway.
$endgroup$
– Mark Bennet
Oct 23 '14 at 15:57
|
show 2 more comments
$begingroup$
Thanks! Could you explain where you got that inequality from?
$endgroup$
– Cathal
Oct 22 '14 at 21:59
$begingroup$
The most obvious arrangement for nine questions would entail a sequence conditioned upon the answers to earlier questions, in a well-known high/low arrangement. With some ingenuity the month could be found with four fixed questions (asked all at once) and the day of month with five fixed questions (also asked at the same time).
$endgroup$
– hardmath
Oct 22 '14 at 22:00
1
$begingroup$
@Cathal If you have yes/no questions, each question can at best reduce the search space by a half - so with a binary search you naturally turn to powers of two. Certain weighing problems on balances have three options (either side heavier, or both sides equal) - for these a power of three is indicated. Here you can attain $2^9$ by indexing the options with integers and asking about the digits in the binary expansion - is the first digit a zero etc.
$endgroup$
– Mark Bennet
Oct 22 '14 at 22:05
$begingroup$
Thank you both very much. I have accepted Mark's answer. Now.. to go about asking the right questions!
$endgroup$
– Cathal
Oct 23 '14 at 14:29
$begingroup$
@Cathal You need each question to divide the search space by as near to half as possible (there is a little flexibility if you are away from a power of two), and particularly to avoid a division in which the size of one part falls just below a power of $2$ while the size of the other part falls just above it (the part which goes over will then need an extra question). With 366 possible dates you have a bit of leeway.
$endgroup$
– Mark Bennet
Oct 23 '14 at 15:57
$begingroup$
Thanks! Could you explain where you got that inequality from?
$endgroup$
– Cathal
Oct 22 '14 at 21:59
$begingroup$
Thanks! Could you explain where you got that inequality from?
$endgroup$
– Cathal
Oct 22 '14 at 21:59
$begingroup$
The most obvious arrangement for nine questions would entail a sequence conditioned upon the answers to earlier questions, in a well-known high/low arrangement. With some ingenuity the month could be found with four fixed questions (asked all at once) and the day of month with five fixed questions (also asked at the same time).
$endgroup$
– hardmath
Oct 22 '14 at 22:00
$begingroup$
The most obvious arrangement for nine questions would entail a sequence conditioned upon the answers to earlier questions, in a well-known high/low arrangement. With some ingenuity the month could be found with four fixed questions (asked all at once) and the day of month with five fixed questions (also asked at the same time).
$endgroup$
– hardmath
Oct 22 '14 at 22:00
1
1
$begingroup$
@Cathal If you have yes/no questions, each question can at best reduce the search space by a half - so with a binary search you naturally turn to powers of two. Certain weighing problems on balances have three options (either side heavier, or both sides equal) - for these a power of three is indicated. Here you can attain $2^9$ by indexing the options with integers and asking about the digits in the binary expansion - is the first digit a zero etc.
$endgroup$
– Mark Bennet
Oct 22 '14 at 22:05
$begingroup$
@Cathal If you have yes/no questions, each question can at best reduce the search space by a half - so with a binary search you naturally turn to powers of two. Certain weighing problems on balances have three options (either side heavier, or both sides equal) - for these a power of three is indicated. Here you can attain $2^9$ by indexing the options with integers and asking about the digits in the binary expansion - is the first digit a zero etc.
$endgroup$
– Mark Bennet
Oct 22 '14 at 22:05
$begingroup$
Thank you both very much. I have accepted Mark's answer. Now.. to go about asking the right questions!
$endgroup$
– Cathal
Oct 23 '14 at 14:29
$begingroup$
Thank you both very much. I have accepted Mark's answer. Now.. to go about asking the right questions!
$endgroup$
– Cathal
Oct 23 '14 at 14:29
$begingroup$
@Cathal You need each question to divide the search space by as near to half as possible (there is a little flexibility if you are away from a power of two), and particularly to avoid a division in which the size of one part falls just below a power of $2$ while the size of the other part falls just above it (the part which goes over will then need an extra question). With 366 possible dates you have a bit of leeway.
$endgroup$
– Mark Bennet
Oct 23 '14 at 15:57
$begingroup$
@Cathal You need each question to divide the search space by as near to half as possible (there is a little flexibility if you are away from a power of two), and particularly to avoid a division in which the size of one part falls just below a power of $2$ while the size of the other part falls just above it (the part which goes over will then need an extra question). With 366 possible dates you have a bit of leeway.
$endgroup$
– Mark Bennet
Oct 23 '14 at 15:57
|
show 2 more comments
draft saved
draft discarded
Thanks for contributing an answer to Mathematics 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.
draft saved
draft discarded
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%2fmath.stackexchange.com%2fquestions%2f986555%2fwhat-is-the-most-efficient-way-of-determining-a-date-of-birth-using-yes-no-quest%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
