Why is that particular kind of sequence relevant to the question not repeatMath Olympiads: GCD of terms in a sequence equals GCD of terms in other sequenceIf the sum of $n$ cubes is zero, then the sum must be no larger than $frac n3$.Proof check for Putnam practice problemFinding the rank of a particular number in a sequence of the sum of numbers and their highest prime factorDo $p,q$ exist such $|p-q|+|a_p-a_q|=2014$Prove that $fraca_1^2a_1+b_1+cdots+fraca_n^2a_n+b_n geq frac12(a_1+cdots+a_n).$A inequality about $x_1,x_2,ldots, x_n$On a 2017 putnam solution to a problem.Induction Problem from Putnam and BeyondDoubt in a solution provided to IMO Shortlist 2013
Why can't we play rap on piano?
How to move a thin line with the black arrow in Illustrator?
Decision tree nodes overlapping with Tikz
How much RAM could one put in a typical 80386 setup?
Are the number of citations and number of published articles the most important criteria for a tenure promotion?
Why can't I see bouncing of switch on oscilloscope screen?
Convert two switches to a dual stack, and add outlet - possible here?
What's that red-plus icon near a text?
Revoked SSL certificate
Why is 150k or 200k jobs considered good when there's 300k+ births a month?
How can I prevent hyper evolved versions of regular creatures from wiping out their cousins?
Maximum likelihood parameters deviate from posterior distributions
What is the word for reserving something for yourself before others do?
Why is Minecraft giving an OpenGL error?
Two films in a tank, only one comes out with a development error – why?
Horror movie about a virus at the prom; beginning and end are stylized as a cartoon
Arrow those variables!
I'm flying to France today and my passport expires in less than 2 months
What doth I be?
Important Resources for Dark Age Civilizations?
Is it possible to do 50 km distance without any previous training?
Has there ever been an airliner design involving reducing generator load by installing solar panels?
Was any UN Security Council vote triple-vetoed?
"You are your self first supporter", a more proper way to say it
Why is that particular kind of sequence relevant to the question not repeat
Math Olympiads: GCD of terms in a sequence equals GCD of terms in other sequenceIf the sum of $n$ cubes is zero, then the sum must be no larger than $frac n3$.Proof check for Putnam practice problemFinding the rank of a particular number in a sequence of the sum of numbers and their highest prime factorDo $p,q$ exist such $|p-q|+|a_p-a_q|=2014$Prove that $fraca_1^2a_1+b_1+cdots+fraca_n^2a_n+b_n geq frac12(a_1+cdots+a_n).$A inequality about $x_1,x_2,ldots, x_n$On a 2017 putnam solution to a problem.Induction Problem from Putnam and BeyondDoubt in a solution provided to IMO Shortlist 2013
$begingroup$
The following is a question from the IMO 2012 shortlist:
Several positive integers are written in a row. Iteratively, Alice chooses two adjacent
numbers $x$ and $y$ such that $x > y$ and $x$ is to the left of $y$, and replaces the pair $(x, y)$ by either
$(y + 1, x)$ or $(x − 1, x)$. Prove that she can perform only finitely many such iterations.
In a solution to this in page number 19, solution 3 in this document:
https://www.imo-official.org/problems/IMO2012SL.pdf
It is stated that score sequences for the given sequence do not repeat. Why is that so?
Solution 3. Let the current numbers be $a_1, a_2, ldots , a_n$. Define the score $s_i$ of $a_i$ as the number of $a_j$’s that are less than $a_i$. Call the sequence $s_1, s_2,ldots , s_n$ the score sequence of $a_1, a_2, ldots, a_n$.
Let us say that a sequence $x_1,ldots , x_n$ dominates a sequence $y_1,ldots , y_n$ if the first index $i$ with $x_i neq y_i$ is such that $x_i < y_i$. We show that after each operation the new score sequence dominates the old one. Score sequences do not repeat, and there are finitely many possibilities for them, no more than $(n − 1)n$. Hence the process will terminate.
Consider an operation that replaces $(x, y)$ by $(a, x)$, with $a = y + 1$ or $a = x − 1$. Suppose that $x$ was originally at position $i$. For each $j < i$ the score $s_j$ does not increase with the change because $y ≤ a$ and $x ≤ x$. If $s_j$ decreases for some $j < i$ then the new score sequence
dominates the old one. Assume that $s_j$ stays the same for all $j < i$ and consider $s_i$. Since $x > y$ and $y ≤ a ≤ x$, we see that $s_i$ decreases by at least $1$. This concludes the proof.
contest-math
asked Mar 29 at 10:02
saisanjeevsaisanjeev
1,073312
$endgroup$
add a comment |
$begingroup$
The following is a question from the IMO 2012 shortlist:
Several positive integers are written in a row. Iteratively, Alice chooses two adjacent
numbers $x$ and $y$ such that $x > y$ and $x$ is to the left of $y$, and replaces the pair $(x, y)$ by either
$(y + 1, x)$ or $(x − 1, x)$. Prove that she can perform only finitely many such iterations.
In a solution to this in page number 19, solution 3 in this document:
https://www.imo-official.org/problems/IMO2012SL.pdf
It is stated that score sequences for the given sequence do not repeat. Why is that so?
Solution 3. Let the current numbers be $a_1, a_2, ldots , a_n$. Define the score $s_i$ of $a_i$ as the number of $a_j$’s that are less than $a_i$. Call the sequence $s_1, s_2,ldots , s_n$ the score sequence of $a_1, a_2, ldots, a_n$.
Let us say that a sequence $x_1,ldots , x_n$ dominates a sequence $y_1,ldots , y_n$ if the first index $i$ with $x_i neq y_i$ is such that $x_i < y_i$. We show that after each operation the new score sequence dominates the old one. Score sequences do not repeat, and there are finitely many possibilities for them, no more than $(n − 1)n$. Hence the process will terminate.
Consider an operation that replaces $(x, y)$ by $(a, x)$, with $a = y + 1$ or $a = x − 1$. Suppose that $x$ was originally at position $i$. For each $j < i$ the score $s_j$ does not increase with the change because $y ≤ a$ and $x ≤ x$. If $s_j$ decreases for some $j < i$ then the new score sequence
dominates the old one. Assume that $s_j$ stays the same for all $j < i$ and consider $s_i$. Since $x > y$ and $y ≤ a ≤ x$, we see that $s_i$ decreases by at least $1$. This concludes the proof.
contest-math
asked Mar 29 at 10:02
saisanjeevsaisanjeev
1,073312
$endgroup$
add a comment |
$begingroup$
The following is a question from the IMO 2012 shortlist:
Several positive integers are written in a row. Iteratively, Alice chooses two adjacent
numbers $x$ and $y$ such that $x > y$ and $x$ is to the left of $y$, and replaces the pair $(x, y)$ by either
$(y + 1, x)$ or $(x − 1, x)$. Prove that she can perform only finitely many such iterations.
In a solution to this in page number 19, solution 3 in this document:
https://www.imo-official.org/problems/IMO2012SL.pdf
It is stated that score sequences for the given sequence do not repeat. Why is that so?
Solution 3. Let the current numbers be $a_1, a_2, ldots , a_n$. Define the score $s_i$ of $a_i$ as the number of $a_j$’s that are less than $a_i$. Call the sequence $s_1, s_2,ldots , s_n$ the score sequence of $a_1, a_2, ldots, a_n$.
Let us say that a sequence $x_1,ldots , x_n$ dominates a sequence $y_1,ldots , y_n$ if the first index $i$ with $x_i neq y_i$ is such that $x_i < y_i$. We show that after each operation the new score sequence dominates the old one. Score sequences do not repeat, and there are finitely many possibilities for them, no more than $(n − 1)n$. Hence the process will terminate.
Consider an operation that replaces $(x, y)$ by $(a, x)$, with $a = y + 1$ or $a = x − 1$. Suppose that $x$ was originally at position $i$. For each $j < i$ the score $s_j$ does not increase with the change because $y ≤ a$ and $x ≤ x$. If $s_j$ decreases for some $j < i$ then the new score sequence
dominates the old one. Assume that $s_j$ stays the same for all $j < i$ and consider $s_i$. Since $x > y$ and $y ≤ a ≤ x$, we see that $s_i$ decreases by at least $1$. This concludes the proof.
contest-math
asked Mar 29 at 10:02
saisanjeevsaisanjeev
1,073312
$endgroup$
The following is a question from the IMO 2012 shortlist:
Several positive integers are written in a row. Iteratively, Alice chooses two adjacent
numbers $x$ and $y$ such that $x > y$ and $x$ is to the left of $y$, and replaces the pair $(x, y)$ by either
$(y + 1, x)$ or $(x − 1, x)$. Prove that she can perform only finitely many such iterations.
In a solution to this in page number 19, solution 3 in this document:
https://www.imo-official.org/problems/IMO2012SL.pdf
It is stated that score sequences for the given sequence do not repeat. Why is that so?
Solution 3. Let the current numbers be $a_1, a_2, ldots , a_n$. Define the score $s_i$ of $a_i$ as the number of $a_j$’s that are less than $a_i$. Call the sequence $s_1, s_2,ldots , s_n$ the score sequence of $a_1, a_2, ldots, a_n$.
Let us say that a sequence $x_1,ldots , x_n$ dominates a sequence $y_1,ldots , y_n$ if the first index $i$ with $x_i neq y_i$ is such that $x_i < y_i$. We show that after each operation the new score sequence dominates the old one. Score sequences do not repeat, and there are finitely many possibilities for them, no more than $(n − 1)n$. Hence the process will terminate.
Consider an operation that replaces $(x, y)$ by $(a, x)$, with $a = y + 1$ or $a = x − 1$. Suppose that $x$ was originally at position $i$. For each $j < i$ the score $s_j$ does not increase with the change because $y ≤ a$ and $x ≤ x$. If $s_j$ decreases for some $j < i$ then the new score sequence
dominates the old one. Assume that $s_j$ stays the same for all $j < i$ and consider $s_i$. Since $x > y$ and $y ≤ a ≤ x$, we see that $s_i$ decreases by at least $1$. This concludes the proof.
contest-math
contest-math
asked Mar 29 at 10:02
saisanjeevsaisanjeev
1,073312
asked Mar 29 at 10:02
saisanjeevsaisanjeev
1,073312
edited Mar 29 at 11:18
saisanjeev
asked Mar 29 at 10:02
saisanjeevsaisanjeev
1,073312
asked Mar 29 at 10:02
saisanjeevsaisanjeev
1,073312
asked Mar 29 at 10:02
saisanjeevsaisanjeev
1,073312
1,073312
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Domination as described is a transitive, non-reflexive property. Transitive means that if you have a chain $S_1prec S_2prec S_3preccdotsprec S_k$ of sequences $S_i$, each one dominating the one before it (I just decided that $prec$ would be a nice symbol to use for domination), then any sequence dominates all sequences before it in the chain, not just the one immidiately preceeding it. Non-reflexive means that no sequence dominates itself.
Put these two properties together, and you see that no sequence can appear twice in the chain. Of course, the transitive and non-reflexive properties mut be proven (transitive is usually described and proven using only a chain of length 3, and together with some almost trivial induction, that's enough to get what I described above). You also need to prove that whatever Alice does, she will produce such a chain, and that's what the second paragraph of the given solution focuses on.
answered Mar 29 at 10:33
ArthurArthur
122k7122211
$endgroup$
$begingroup$
Can you also please explain how are the bounds obtained? especially for the first solution that is given... the bounds for the other two solutions are quite simple...
$endgroup$
– saisanjeev
Mar 29 at 11:40
1
$begingroup$
@saisanjeev First of all, note that the exact value of any bound is irrelevant. It is the existence of a bound which is important. But that being said, none of the $a_i$ can ever reach a higher value than $M$, which means that this special sum $S$ cannot ever get higher than $(1+2+3+cdots +n)M$.
$endgroup$
– Arthur
Mar 29 at 12:40
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: "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%2f3166966%2fwhy-is-that-particular-kind-of-sequence-relevant-to-the-question-not-repeat%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$
Domination as described is a transitive, non-reflexive property. Transitive means that if you have a chain $S_1prec S_2prec S_3preccdotsprec S_k$ of sequences $S_i$, each one dominating the one before it (I just decided that $prec$ would be a nice symbol to use for domination), then any sequence dominates all sequences before it in the chain, not just the one immidiately preceeding it. Non-reflexive means that no sequence dominates itself.
Put these two properties together, and you see that no sequence can appear twice in the chain. Of course, the transitive and non-reflexive properties mut be proven (transitive is usually described and proven using only a chain of length 3, and together with some almost trivial induction, that's enough to get what I described above). You also need to prove that whatever Alice does, she will produce such a chain, and that's what the second paragraph of the given solution focuses on.
answered Mar 29 at 10:33
ArthurArthur
122k7122211
$endgroup$
$begingroup$
Can you also please explain how are the bounds obtained? especially for the first solution that is given... the bounds for the other two solutions are quite simple...
$endgroup$
– saisanjeev
Mar 29 at 11:40
1
$begingroup$
@saisanjeev First of all, note that the exact value of any bound is irrelevant. It is the existence of a bound which is important. But that being said, none of the $a_i$ can ever reach a higher value than $M$, which means that this special sum $S$ cannot ever get higher than $(1+2+3+cdots +n)M$.
$endgroup$
– Arthur
Mar 29 at 12:40
add a comment |
$begingroup$
Domination as described is a transitive, non-reflexive property. Transitive means that if you have a chain $S_1prec S_2prec S_3preccdotsprec S_k$ of sequences $S_i$, each one dominating the one before it (I just decided that $prec$ would be a nice symbol to use for domination), then any sequence dominates all sequences before it in the chain, not just the one immidiately preceeding it. Non-reflexive means that no sequence dominates itself.
Put these two properties together, and you see that no sequence can appear twice in the chain. Of course, the transitive and non-reflexive properties mut be proven (transitive is usually described and proven using only a chain of length 3, and together with some almost trivial induction, that's enough to get what I described above). You also need to prove that whatever Alice does, she will produce such a chain, and that's what the second paragraph of the given solution focuses on.
answered Mar 29 at 10:33
ArthurArthur
122k7122211
$endgroup$
$begingroup$
Can you also please explain how are the bounds obtained? especially for the first solution that is given... the bounds for the other two solutions are quite simple...
$endgroup$
– saisanjeev
Mar 29 at 11:40
1
$begingroup$
@saisanjeev First of all, note that the exact value of any bound is irrelevant. It is the existence of a bound which is important. But that being said, none of the $a_i$ can ever reach a higher value than $M$, which means that this special sum $S$ cannot ever get higher than $(1+2+3+cdots +n)M$.
$endgroup$
– Arthur
Mar 29 at 12:40
add a comment |
$begingroup$
Domination as described is a transitive, non-reflexive property. Transitive means that if you have a chain $S_1prec S_2prec S_3preccdotsprec S_k$ of sequences $S_i$, each one dominating the one before it (I just decided that $prec$ would be a nice symbol to use for domination), then any sequence dominates all sequences before it in the chain, not just the one immidiately preceeding it. Non-reflexive means that no sequence dominates itself.
Put these two properties together, and you see that no sequence can appear twice in the chain. Of course, the transitive and non-reflexive properties mut be proven (transitive is usually described and proven using only a chain of length 3, and together with some almost trivial induction, that's enough to get what I described above). You also need to prove that whatever Alice does, she will produce such a chain, and that's what the second paragraph of the given solution focuses on.
answered Mar 29 at 10:33
ArthurArthur
122k7122211
$endgroup$
Domination as described is a transitive, non-reflexive property. Transitive means that if you have a chain $S_1prec S_2prec S_3preccdotsprec S_k$ of sequences $S_i$, each one dominating the one before it (I just decided that $prec$ would be a nice symbol to use for domination), then any sequence dominates all sequences before it in the chain, not just the one immidiately preceeding it. Non-reflexive means that no sequence dominates itself.
Put these two properties together, and you see that no sequence can appear twice in the chain. Of course, the transitive and non-reflexive properties mut be proven (transitive is usually described and proven using only a chain of length 3, and together with some almost trivial induction, that's enough to get what I described above). You also need to prove that whatever Alice does, she will produce such a chain, and that's what the second paragraph of the given solution focuses on.
answered Mar 29 at 10:33
ArthurArthur
122k7122211
answered Mar 29 at 10:33
ArthurArthur
122k7122211
answered Mar 29 at 10:33
ArthurArthur
122k7122211
answered Mar 29 at 10:33
ArthurArthur
122k7122211
122k7122211
$begingroup$
Can you also please explain how are the bounds obtained? especially for the first solution that is given... the bounds for the other two solutions are quite simple...
$endgroup$
– saisanjeev
Mar 29 at 11:40
1
$begingroup$
@saisanjeev First of all, note that the exact value of any bound is irrelevant. It is the existence of a bound which is important. But that being said, none of the $a_i$ can ever reach a higher value than $M$, which means that this special sum $S$ cannot ever get higher than $(1+2+3+cdots +n)M$.
$endgroup$
– Arthur
Mar 29 at 12:40
add a comment |
$begingroup$
Can you also please explain how are the bounds obtained? especially for the first solution that is given... the bounds for the other two solutions are quite simple...
$endgroup$
– saisanjeev
Mar 29 at 11:40
1
$begingroup$
@saisanjeev First of all, note that the exact value of any bound is irrelevant. It is the existence of a bound which is important. But that being said, none of the $a_i$ can ever reach a higher value than $M$, which means that this special sum $S$ cannot ever get higher than $(1+2+3+cdots +n)M$.
$endgroup$
– Arthur
Mar 29 at 12:40
$begingroup$
Can you also please explain how are the bounds obtained? especially for the first solution that is given... the bounds for the other two solutions are quite simple...
$endgroup$
– saisanjeev
Mar 29 at 11:40
$begingroup$
Can you also please explain how are the bounds obtained? especially for the first solution that is given... the bounds for the other two solutions are quite simple...
$endgroup$
– saisanjeev
Mar 29 at 11:40
1
1
$begingroup$
@saisanjeev First of all, note that the exact value of any bound is irrelevant. It is the existence of a bound which is important. But that being said, none of the $a_i$ can ever reach a higher value than $M$, which means that this special sum $S$ cannot ever get higher than $(1+2+3+cdots +n)M$.
$endgroup$
– Arthur
Mar 29 at 12:40
$begingroup$
@saisanjeev First of all, note that the exact value of any bound is irrelevant. It is the existence of a bound which is important. But that being said, none of the $a_i$ can ever reach a higher value than $M$, which means that this special sum $S$ cannot ever get higher than $(1+2+3+cdots +n)M$.
$endgroup$
– Arthur
Mar 29 at 12:40
add a comment |
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%2f3166966%2fwhy-is-that-particular-kind-of-sequence-relevant-to-the-question-not-repeat%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
