One beer too many
$begingroup$
You're standing outside your apartment building after a late night out, with perhaps one beer too many, and you realize you have completely forgotten the code to get in. Luckily, you're a mathematical genius, and somehow that part of the brain is completely unaffected by the alcohol, so you decide to find the optimal strategy to get in.
The code is entered on a standard 0-9 keypad, and you know that it is a four digit code. Entering the correct sequence of digits will open the door. When entering a sequence, every four digit sub sequence will be evaluated by the security system. I.e. entering 195638 will evaluate the following three sequences: 1956, 9563, and 5638, so it is a waste of time to try each four digit sequence one by one.
Question: What is the smallest number of keypresses needed to try every sequence between 0000 and 9999?
mathematics calculation-puzzle combinatorics
edited Oct 8 '15 at 18:18
Gamow
33.9k9123364
asked Oct 3 '15 at 10:41
PetterPetter
596510
$endgroup$
add a comment |
$begingroup$
You're standing outside your apartment building after a late night out, with perhaps one beer too many, and you realize you have completely forgotten the code to get in. Luckily, you're a mathematical genius, and somehow that part of the brain is completely unaffected by the alcohol, so you decide to find the optimal strategy to get in.
The code is entered on a standard 0-9 keypad, and you know that it is a four digit code. Entering the correct sequence of digits will open the door. When entering a sequence, every four digit sub sequence will be evaluated by the security system. I.e. entering 195638 will evaluate the following three sequences: 1956, 9563, and 5638, so it is a waste of time to try each four digit sequence one by one.
Question: What is the smallest number of keypresses needed to try every sequence between 0000 and 9999?
mathematics calculation-puzzle combinatorics
edited Oct 8 '15 at 18:18
Gamow
33.9k9123364
asked Oct 3 '15 at 10:41
PetterPetter
596510
$endgroup$
add a comment |
$begingroup$
You're standing outside your apartment building after a late night out, with perhaps one beer too many, and you realize you have completely forgotten the code to get in. Luckily, you're a mathematical genius, and somehow that part of the brain is completely unaffected by the alcohol, so you decide to find the optimal strategy to get in.
The code is entered on a standard 0-9 keypad, and you know that it is a four digit code. Entering the correct sequence of digits will open the door. When entering a sequence, every four digit sub sequence will be evaluated by the security system. I.e. entering 195638 will evaluate the following three sequences: 1956, 9563, and 5638, so it is a waste of time to try each four digit sequence one by one.
Question: What is the smallest number of keypresses needed to try every sequence between 0000 and 9999?
mathematics calculation-puzzle combinatorics
edited Oct 8 '15 at 18:18
Gamow
33.9k9123364
asked Oct 3 '15 at 10:41
PetterPetter
596510
$endgroup$
You're standing outside your apartment building after a late night out, with perhaps one beer too many, and you realize you have completely forgotten the code to get in. Luckily, you're a mathematical genius, and somehow that part of the brain is completely unaffected by the alcohol, so you decide to find the optimal strategy to get in.
The code is entered on a standard 0-9 keypad, and you know that it is a four digit code. Entering the correct sequence of digits will open the door. When entering a sequence, every four digit sub sequence will be evaluated by the security system. I.e. entering 195638 will evaluate the following three sequences: 1956, 9563, and 5638, so it is a waste of time to try each four digit sequence one by one.
Question: What is the smallest number of keypresses needed to try every sequence between 0000 and 9999?
mathematics calculation-puzzle combinatorics
mathematics calculation-puzzle combinatorics
edited Oct 8 '15 at 18:18
Gamow
33.9k9123364
asked Oct 3 '15 at 10:41
PetterPetter
596510
edited Oct 8 '15 at 18:18
Gamow
33.9k9123364
asked Oct 3 '15 at 10:41
PetterPetter
596510
edited Oct 8 '15 at 18:18
Gamow
33.9k9123364
edited Oct 8 '15 at 18:18
Gamow
33.9k9123364
edited Oct 8 '15 at 18:18
Gamow
33.9k9123364
33.9k9123364
asked Oct 3 '15 at 10:41
PetterPetter
596510
asked Oct 3 '15 at 10:41
PetterPetter
596510
asked Oct 3 '15 at 10:41
PetterPetter
596510
596510
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The De Bruijn sequence $B(k,n)$ is a cyclic sequence over an alphabet of size $k$ that contains every possible word of length $n$ exactly once;
see the wikipedia for more information.
The length of such a De Bruijn sequence $B(k,n)$ is $k^n$, that is, it equals the number of words of length $n$ over an alphabet of size $k$.
The De Bruijn sequence $B(10,4)$ is over an alphabet of size 10 (that is, the ten digits 0,1,2,$ldots$,9), and it contains every possible word of length 4 (that is, every 4-digit number). The length of $B(10,4)$ is $10^4$.
The puzzle now does not ask about a cyclic sequence, but about an ordinary linear sequence. If we follow the cyclic De Bruijn sequence $B(10,4)$ around the cycle, we will encounter every 4-digit number exactly once. This takes $10^4$ digits plus an additional 3 digits at the end (where the cycle closes, while the linear sequence remains open).
Hence the answer is $10^4+3=10003$ keypresses.
answered Oct 3 '15 at 11:07
GamowGamow
33.9k9123364
$endgroup$
$begingroup$
That was quick! :)
$endgroup$
– Petter
Oct 3 '15 at 13:55
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%2f22842%2fone-beer-too-many%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
$begingroup$
The De Bruijn sequence $B(k,n)$ is a cyclic sequence over an alphabet of size $k$ that contains every possible word of length $n$ exactly once;
see the wikipedia for more information.
The length of such a De Bruijn sequence $B(k,n)$ is $k^n$, that is, it equals the number of words of length $n$ over an alphabet of size $k$.
The De Bruijn sequence $B(10,4)$ is over an alphabet of size 10 (that is, the ten digits 0,1,2,$ldots$,9), and it contains every possible word of length 4 (that is, every 4-digit number). The length of $B(10,4)$ is $10^4$.
The puzzle now does not ask about a cyclic sequence, but about an ordinary linear sequence. If we follow the cyclic De Bruijn sequence $B(10,4)$ around the cycle, we will encounter every 4-digit number exactly once. This takes $10^4$ digits plus an additional 3 digits at the end (where the cycle closes, while the linear sequence remains open).
Hence the answer is $10^4+3=10003$ keypresses.
answered Oct 3 '15 at 11:07
GamowGamow
33.9k9123364
$endgroup$
$begingroup$
That was quick! :)
$endgroup$
– Petter
Oct 3 '15 at 13:55
add a comment |
$begingroup$
The De Bruijn sequence $B(k,n)$ is a cyclic sequence over an alphabet of size $k$ that contains every possible word of length $n$ exactly once;
see the wikipedia for more information.
The length of such a De Bruijn sequence $B(k,n)$ is $k^n$, that is, it equals the number of words of length $n$ over an alphabet of size $k$.
The De Bruijn sequence $B(10,4)$ is over an alphabet of size 10 (that is, the ten digits 0,1,2,$ldots$,9), and it contains every possible word of length 4 (that is, every 4-digit number). The length of $B(10,4)$ is $10^4$.
The puzzle now does not ask about a cyclic sequence, but about an ordinary linear sequence. If we follow the cyclic De Bruijn sequence $B(10,4)$ around the cycle, we will encounter every 4-digit number exactly once. This takes $10^4$ digits plus an additional 3 digits at the end (where the cycle closes, while the linear sequence remains open).
Hence the answer is $10^4+3=10003$ keypresses.
answered Oct 3 '15 at 11:07
GamowGamow
33.9k9123364
$endgroup$
$begingroup$
That was quick! :)
$endgroup$
– Petter
Oct 3 '15 at 13:55
add a comment |
$begingroup$
The De Bruijn sequence $B(k,n)$ is a cyclic sequence over an alphabet of size $k$ that contains every possible word of length $n$ exactly once;
see the wikipedia for more information.
The length of such a De Bruijn sequence $B(k,n)$ is $k^n$, that is, it equals the number of words of length $n$ over an alphabet of size $k$.
The De Bruijn sequence $B(10,4)$ is over an alphabet of size 10 (that is, the ten digits 0,1,2,$ldots$,9), and it contains every possible word of length 4 (that is, every 4-digit number). The length of $B(10,4)$ is $10^4$.
The puzzle now does not ask about a cyclic sequence, but about an ordinary linear sequence. If we follow the cyclic De Bruijn sequence $B(10,4)$ around the cycle, we will encounter every 4-digit number exactly once. This takes $10^4$ digits plus an additional 3 digits at the end (where the cycle closes, while the linear sequence remains open).
Hence the answer is $10^4+3=10003$ keypresses.
answered Oct 3 '15 at 11:07
GamowGamow
33.9k9123364
$endgroup$
The De Bruijn sequence $B(k,n)$ is a cyclic sequence over an alphabet of size $k$ that contains every possible word of length $n$ exactly once;
see the wikipedia for more information.
The length of such a De Bruijn sequence $B(k,n)$ is $k^n$, that is, it equals the number of words of length $n$ over an alphabet of size $k$.
The De Bruijn sequence $B(10,4)$ is over an alphabet of size 10 (that is, the ten digits 0,1,2,$ldots$,9), and it contains every possible word of length 4 (that is, every 4-digit number). The length of $B(10,4)$ is $10^4$.
The puzzle now does not ask about a cyclic sequence, but about an ordinary linear sequence. If we follow the cyclic De Bruijn sequence $B(10,4)$ around the cycle, we will encounter every 4-digit number exactly once. This takes $10^4$ digits plus an additional 3 digits at the end (where the cycle closes, while the linear sequence remains open).
Hence the answer is $10^4+3=10003$ keypresses.
answered Oct 3 '15 at 11:07
GamowGamow
33.9k9123364
answered Oct 3 '15 at 11:07
GamowGamow
33.9k9123364
answered Oct 3 '15 at 11:07
GamowGamow
33.9k9123364
answered Oct 3 '15 at 11:07
GamowGamow
33.9k9123364
33.9k9123364
$begingroup$
That was quick! :)
$endgroup$
– Petter
Oct 3 '15 at 13:55
add a comment |
$begingroup$
That was quick! :)
$endgroup$
– Petter
Oct 3 '15 at 13:55
$begingroup$
That was quick! :)
$endgroup$
– Petter
Oct 3 '15 at 13:55
$begingroup$
That was quick! :)
$endgroup$
– Petter
Oct 3 '15 at 13:55
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.
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%2f22842%2fone-beer-too-many%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
