Mixing
Interesting sequences question Olympiad style
$begingroup$
Let a sequence of n numbers be called good if there exists 2p consecutive numbers somewhere in the sequence such that, of these 2p numbers, each pair of numbers with distance p from each other are equal. (e.g. 1,3,2,4,3,2,4,6,7 - here, p=3 for the numbers 3,2,4,3,2,4)
Note that p is arbitrary. (By consecutive, I mean consecutive placings in the sequence.)
What is the least n such that the sequence of n numbers from the set 1,2,3,...,k(allow repeats and exclusion of numbers) is not good, but its extension with an extra n+1 th number is good for any n+1 th number from the set 1,2,3,...k.
I have an idea like this:
...,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1. If you add 1 to the end, the last two numbers 1,1 make the sequence trivially good. If you add 2, then 1,2,1,2 makes the sequence good. If you carry on in this way, you get (2^k)-1. (This is probably not the least n, but it is an idea.)
sequences-and-series combinatorics induction contest-math
asked Sep 26 '16 at 6:38
user365682user365682
334
$endgroup$
add a comment |
$begingroup$
Let a sequence of n numbers be called good if there exists 2p consecutive numbers somewhere in the sequence such that, of these 2p numbers, each pair of numbers with distance p from each other are equal. (e.g. 1,3,2,4,3,2,4,6,7 - here, p=3 for the numbers 3,2,4,3,2,4)
Note that p is arbitrary. (By consecutive, I mean consecutive placings in the sequence.)
What is the least n such that the sequence of n numbers from the set 1,2,3,...,k(allow repeats and exclusion of numbers) is not good, but its extension with an extra n+1 th number is good for any n+1 th number from the set 1,2,3,...k.
I have an idea like this:
...,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1. If you add 1 to the end, the last two numbers 1,1 make the sequence trivially good. If you add 2, then 1,2,1,2 makes the sequence good. If you carry on in this way, you get (2^k)-1. (This is probably not the least n, but it is an idea.)
sequences-and-series combinatorics induction contest-math
asked Sep 26 '16 at 6:38
user365682user365682
334
$endgroup$
$begingroup$
Is a sequence good if there exists a $p$ such that...? Or is it $p$-good if...? And $p$ is not restricted to primes?
$endgroup$
– Arthur
Sep 26 '16 at 6:42
$begingroup$
if there exists some or a p, and not restriced to primes
$endgroup$
– user365682
Sep 26 '16 at 6:43
1
$begingroup$
Does extension mean we add the last number at the end?
$endgroup$
– ghosts_in_the_code
Sep 26 '16 at 16:12
$begingroup$
Yes, we add any of 1,2,...,k to the end.
$endgroup$
– user365682
Sep 27 '16 at 7:26
add a comment |
$begingroup$
Let a sequence of n numbers be called good if there exists 2p consecutive numbers somewhere in the sequence such that, of these 2p numbers, each pair of numbers with distance p from each other are equal. (e.g. 1,3,2,4,3,2,4,6,7 - here, p=3 for the numbers 3,2,4,3,2,4)
Note that p is arbitrary. (By consecutive, I mean consecutive placings in the sequence.)
What is the least n such that the sequence of n numbers from the set 1,2,3,...,k(allow repeats and exclusion of numbers) is not good, but its extension with an extra n+1 th number is good for any n+1 th number from the set 1,2,3,...k.
I have an idea like this:
...,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1. If you add 1 to the end, the last two numbers 1,1 make the sequence trivially good. If you add 2, then 1,2,1,2 makes the sequence good. If you carry on in this way, you get (2^k)-1. (This is probably not the least n, but it is an idea.)
sequences-and-series combinatorics induction contest-math
asked Sep 26 '16 at 6:38
user365682user365682
334
$endgroup$
Let a sequence of n numbers be called good if there exists 2p consecutive numbers somewhere in the sequence such that, of these 2p numbers, each pair of numbers with distance p from each other are equal. (e.g. 1,3,2,4,3,2,4,6,7 - here, p=3 for the numbers 3,2,4,3,2,4)
Note that p is arbitrary. (By consecutive, I mean consecutive placings in the sequence.)
What is the least n such that the sequence of n numbers from the set 1,2,3,...,k(allow repeats and exclusion of numbers) is not good, but its extension with an extra n+1 th number is good for any n+1 th number from the set 1,2,3,...k.
I have an idea like this:
...,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1. If you add 1 to the end, the last two numbers 1,1 make the sequence trivially good. If you add 2, then 1,2,1,2 makes the sequence good. If you carry on in this way, you get (2^k)-1. (This is probably not the least n, but it is an idea.)
sequences-and-series combinatorics induction contest-math
sequences-and-series combinatorics induction contest-math
asked Sep 26 '16 at 6:38
user365682user365682
334
asked Sep 26 '16 at 6:38
user365682user365682
334
edited Sep 26 '16 at 9:00
user365682
asked Sep 26 '16 at 6:38
user365682user365682
334
asked Sep 26 '16 at 6:38
user365682user365682
334
asked Sep 26 '16 at 6:38
user365682user365682
334
334
$begingroup$
Is a sequence good if there exists a $p$ such that...? Or is it $p$-good if...? And $p$ is not restricted to primes?
$endgroup$
– Arthur
Sep 26 '16 at 6:42
$begingroup$
if there exists some or a p, and not restriced to primes
$endgroup$
– user365682
Sep 26 '16 at 6:43
1
$begingroup$
Does extension mean we add the last number at the end?
$endgroup$
– ghosts_in_the_code
Sep 26 '16 at 16:12
$begingroup$
Yes, we add any of 1,2,...,k to the end.
$endgroup$
– user365682
Sep 27 '16 at 7:26
add a comment |
$begingroup$
Is a sequence good if there exists a $p$ such that...? Or is it $p$-good if...? And $p$ is not restricted to primes?
$endgroup$
– Arthur
Sep 26 '16 at 6:42
$begingroup$
if there exists some or a p, and not restriced to primes
$endgroup$
– user365682
Sep 26 '16 at 6:43
1
$begingroup$
Does extension mean we add the last number at the end?
$endgroup$
– ghosts_in_the_code
Sep 26 '16 at 16:12
$begingroup$
Yes, we add any of 1,2,...,k to the end.
$endgroup$
– user365682
Sep 27 '16 at 7:26
$begingroup$
Is a sequence good if there exists a $p$ such that...? Or is it $p$-good if...? And $p$ is not restricted to primes?
$endgroup$
– Arthur
Sep 26 '16 at 6:42
$begingroup$
Is a sequence good if there exists a $p$ such that...? Or is it $p$-good if...? And $p$ is not restricted to primes?
$endgroup$
– Arthur
Sep 26 '16 at 6:42
$begingroup$
if there exists some or a p, and not restriced to primes
$endgroup$
– user365682
Sep 26 '16 at 6:43
$begingroup$
if there exists some or a p, and not restriced to primes
$endgroup$
– user365682
Sep 26 '16 at 6:43
1
1
$begingroup$
Does extension mean we add the last number at the end?
$endgroup$
– ghosts_in_the_code
Sep 26 '16 at 16:12
$begingroup$
Does extension mean we add the last number at the end?
$endgroup$
– ghosts_in_the_code
Sep 26 '16 at 16:12
$begingroup$
Yes, we add any of 1,2,...,k to the end.
$endgroup$
– user365682
Sep 27 '16 at 7:26
$begingroup$
Yes, we add any of 1,2,...,k to the end.
$endgroup$
– user365682
Sep 27 '16 at 7:26
add a comment |
0
active
oldest
votes
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: "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
});
}
});
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%2f1941835%2finteresting-sequences-question-olympiad-style%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
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%2f1941835%2finteresting-sequences-question-olympiad-style%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
$begingroup$
Is a sequence good if there exists a $p$ such that...? Or is it $p$-good if...? And $p$ is not restricted to primes?
$endgroup$
– Arthur
Sep 26 '16 at 6:42
$begingroup$
if there exists some or a p, and not restriced to primes
$endgroup$
– user365682
Sep 26 '16 at 6:43
1
$begingroup$
Does extension mean we add the last number at the end?
$endgroup$
– ghosts_in_the_code
Sep 26 '16 at 16:12
$begingroup$
Yes, we add any of 1,2,...,k to the end.
$endgroup$
– user365682
Sep 27 '16 at 7:26