Sum of differences of circular permutation
$begingroup$
The numbers $1,2,ldots,n$ are arranged into a circle. What is the maximum sum of the differences $|x_1-x_2|+|x_2-x_3|+ldots+|x_{n-1}-x_n|+|x_n-x_1|$?
I think the maximum should occur when the numbers are arranged $n,1,n-1,2,n-2,3,ldots$, but how to prove it formally?
The sum for this arrangement is $(n-1)+(n-2)+ldots+1+lfloor n/2rfloor = dfrac{n(n-1)}{2}+lfloor n/2rfloor$.
combinatorics permutations
edited Dec 8 '18 at 18:35
Jam
4,97921431
asked Nov 8 '14 at 23:09
DexterDexter
886417
$endgroup$
add a comment |
$begingroup$
The numbers $1,2,ldots,n$ are arranged into a circle. What is the maximum sum of the differences $|x_1-x_2|+|x_2-x_3|+ldots+|x_{n-1}-x_n|+|x_n-x_1|$?
I think the maximum should occur when the numbers are arranged $n,1,n-1,2,n-2,3,ldots$, but how to prove it formally?
The sum for this arrangement is $(n-1)+(n-2)+ldots+1+lfloor n/2rfloor = dfrac{n(n-1)}{2}+lfloor n/2rfloor$.
combinatorics permutations
edited Dec 8 '18 at 18:35
Jam
4,97921431
asked Nov 8 '14 at 23:09
DexterDexter
886417
$endgroup$
$begingroup$
What did you try so far? Do you have any ideas? What sum do you get for your conjectured maximal arrangement?
$endgroup$
– flawr
Nov 8 '14 at 23:30
$begingroup$
So you get a mean difference of $(n-1)/2+lfloor n/2 rfloor/n$, I think too that this is the maximum, and I think we might perhaps be able to prove this by finding a contradiction if we assume that the mean difference is greater. (Separating the cases where n is even or odd.) But it really is a nice problem.
$endgroup$
– flawr
Nov 8 '14 at 23:42
$begingroup$
Intuitively, your first equation is never greater than the sum of $x_1+x_2+...+x_n$. Your second equation is almost equivalent to $frac{n^2}{2}$, and the sum of the first $n$ integers is $frac{n^2+n}{2}$. If the conjecture is true and you can show a minimal "loss" of approximately $frac{n}{2}$ (perhaps from $x_n-x_1$) you have found the maximum.
$endgroup$
– Ari
Nov 8 '14 at 23:47
$begingroup$
This problem is often discussed in terms of arranging numbers on a dartboard (to maximise the penalty for poor aim) so searching for "optimal dartboard" or similar may help. I think, though I may be misremembering, that all arrangements that alternate between numbers from the top half of the range and numbers from the bottom half (as yours does) are equally good and as good as possible.
$endgroup$
– aPaulT
Nov 8 '14 at 23:50
add a comment |
$begingroup$
The numbers $1,2,ldots,n$ are arranged into a circle. What is the maximum sum of the differences $|x_1-x_2|+|x_2-x_3|+ldots+|x_{n-1}-x_n|+|x_n-x_1|$?
I think the maximum should occur when the numbers are arranged $n,1,n-1,2,n-2,3,ldots$, but how to prove it formally?
The sum for this arrangement is $(n-1)+(n-2)+ldots+1+lfloor n/2rfloor = dfrac{n(n-1)}{2}+lfloor n/2rfloor$.
combinatorics permutations
edited Dec 8 '18 at 18:35
Jam
4,97921431
asked Nov 8 '14 at 23:09
DexterDexter
886417
$endgroup$
The numbers $1,2,ldots,n$ are arranged into a circle. What is the maximum sum of the differences $|x_1-x_2|+|x_2-x_3|+ldots+|x_{n-1}-x_n|+|x_n-x_1|$?
I think the maximum should occur when the numbers are arranged $n,1,n-1,2,n-2,3,ldots$, but how to prove it formally?
The sum for this arrangement is $(n-1)+(n-2)+ldots+1+lfloor n/2rfloor = dfrac{n(n-1)}{2}+lfloor n/2rfloor$.
combinatorics permutations
combinatorics permutations
edited Dec 8 '18 at 18:35
Jam
4,97921431
asked Nov 8 '14 at 23:09
DexterDexter
886417
edited Dec 8 '18 at 18:35
Jam
4,97921431
asked Nov 8 '14 at 23:09
DexterDexter
886417
edited Dec 8 '18 at 18:35
Jam
4,97921431
edited Dec 8 '18 at 18:35
Jam
4,97921431
edited Dec 8 '18 at 18:35
Jam
4,97921431
4,97921431
asked Nov 8 '14 at 23:09
DexterDexter
886417
asked Nov 8 '14 at 23:09
DexterDexter
886417
asked Nov 8 '14 at 23:09
DexterDexter
886417
886417
$begingroup$
What did you try so far? Do you have any ideas? What sum do you get for your conjectured maximal arrangement?
$endgroup$
– flawr
Nov 8 '14 at 23:30
$begingroup$
So you get a mean difference of $(n-1)/2+lfloor n/2 rfloor/n$, I think too that this is the maximum, and I think we might perhaps be able to prove this by finding a contradiction if we assume that the mean difference is greater. (Separating the cases where n is even or odd.) But it really is a nice problem.
$endgroup$
– flawr
Nov 8 '14 at 23:42
$begingroup$
Intuitively, your first equation is never greater than the sum of $x_1+x_2+...+x_n$. Your second equation is almost equivalent to $frac{n^2}{2}$, and the sum of the first $n$ integers is $frac{n^2+n}{2}$. If the conjecture is true and you can show a minimal "loss" of approximately $frac{n}{2}$ (perhaps from $x_n-x_1$) you have found the maximum.
$endgroup$
– Ari
Nov 8 '14 at 23:47
$begingroup$
This problem is often discussed in terms of arranging numbers on a dartboard (to maximise the penalty for poor aim) so searching for "optimal dartboard" or similar may help. I think, though I may be misremembering, that all arrangements that alternate between numbers from the top half of the range and numbers from the bottom half (as yours does) are equally good and as good as possible.
$endgroup$
– aPaulT
Nov 8 '14 at 23:50
add a comment |
$begingroup$
What did you try so far? Do you have any ideas? What sum do you get for your conjectured maximal arrangement?
$endgroup$
– flawr
Nov 8 '14 at 23:30
$begingroup$
So you get a mean difference of $(n-1)/2+lfloor n/2 rfloor/n$, I think too that this is the maximum, and I think we might perhaps be able to prove this by finding a contradiction if we assume that the mean difference is greater. (Separating the cases where n is even or odd.) But it really is a nice problem.
$endgroup$
– flawr
Nov 8 '14 at 23:42
$begingroup$
Intuitively, your first equation is never greater than the sum of $x_1+x_2+...+x_n$. Your second equation is almost equivalent to $frac{n^2}{2}$, and the sum of the first $n$ integers is $frac{n^2+n}{2}$. If the conjecture is true and you can show a minimal "loss" of approximately $frac{n}{2}$ (perhaps from $x_n-x_1$) you have found the maximum.
$endgroup$
– Ari
Nov 8 '14 at 23:47
$begingroup$
This problem is often discussed in terms of arranging numbers on a dartboard (to maximise the penalty for poor aim) so searching for "optimal dartboard" or similar may help. I think, though I may be misremembering, that all arrangements that alternate between numbers from the top half of the range and numbers from the bottom half (as yours does) are equally good and as good as possible.
$endgroup$
– aPaulT
Nov 8 '14 at 23:50
$begingroup$
What did you try so far? Do you have any ideas? What sum do you get for your conjectured maximal arrangement?
$endgroup$
– flawr
Nov 8 '14 at 23:30
$begingroup$
What did you try so far? Do you have any ideas? What sum do you get for your conjectured maximal arrangement?
$endgroup$
– flawr
Nov 8 '14 at 23:30
$begingroup$
So you get a mean difference of $(n-1)/2+lfloor n/2 rfloor/n$, I think too that this is the maximum, and I think we might perhaps be able to prove this by finding a contradiction if we assume that the mean difference is greater. (Separating the cases where n is even or odd.) But it really is a nice problem.
$endgroup$
– flawr
Nov 8 '14 at 23:42
$begingroup$
So you get a mean difference of $(n-1)/2+lfloor n/2 rfloor/n$, I think too that this is the maximum, and I think we might perhaps be able to prove this by finding a contradiction if we assume that the mean difference is greater. (Separating the cases where n is even or odd.) But it really is a nice problem.
$endgroup$
– flawr
Nov 8 '14 at 23:42
$begingroup$
Intuitively, your first equation is never greater than the sum of $x_1+x_2+...+x_n$. Your second equation is almost equivalent to $frac{n^2}{2}$, and the sum of the first $n$ integers is $frac{n^2+n}{2}$. If the conjecture is true and you can show a minimal "loss" of approximately $frac{n}{2}$ (perhaps from $x_n-x_1$) you have found the maximum.
$endgroup$
– Ari
Nov 8 '14 at 23:47
$begingroup$
Intuitively, your first equation is never greater than the sum of $x_1+x_2+...+x_n$. Your second equation is almost equivalent to $frac{n^2}{2}$, and the sum of the first $n$ integers is $frac{n^2+n}{2}$. If the conjecture is true and you can show a minimal "loss" of approximately $frac{n}{2}$ (perhaps from $x_n-x_1$) you have found the maximum.
$endgroup$
– Ari
Nov 8 '14 at 23:47
$begingroup$
This problem is often discussed in terms of arranging numbers on a dartboard (to maximise the penalty for poor aim) so searching for "optimal dartboard" or similar may help. I think, though I may be misremembering, that all arrangements that alternate between numbers from the top half of the range and numbers from the bottom half (as yours does) are equally good and as good as possible.
$endgroup$
– aPaulT
Nov 8 '14 at 23:50
$begingroup$
This problem is often discussed in terms of arranging numbers on a dartboard (to maximise the penalty for poor aim) so searching for "optimal dartboard" or similar may help. I think, though I may be misremembering, that all arrangements that alternate between numbers from the top half of the range and numbers from the bottom half (as yours does) are equally good and as good as possible.
$endgroup$
– aPaulT
Nov 8 '14 at 23:50
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The key idea is that $|x - y|$ is basically either $x - y$ or $y - x$. Either way, one term (either $x$ or $y$) inside the absolute will be positive, and the other term will be negative.
This means, if you have $n$ absolutes, you will have $n$ positive terms and $n$ negative terms. Now, each $x_i$ appears twice in all of these absolutes, so in total we have $2n$ terms. So, since we must have $n$ positive terms and $n$ negative terms, in order to maximize the sum, we want to make the larger $x_i$s positive and the smaller $x_i$s negative.
I will demonstrate the case where $n$ is even (odd is similar, but need some little more work). By the argument in the previous paragraph, the sum cannot exceed:
$$2( (n/2+1) + (n/2+2) + cdots + n) - 2 (1 + 2 + cdots + n/2) = 2 frac{n}{4} (frac{n}{2} + 1 + n) - 2 frac{n}{4} (1 + frac{n}{2}) = n^2 / 2$$
Which matches your bound.
answered Nov 9 '14 at 4:25
IrvanIrvan
1,673822
$endgroup$
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%2f1012617%2fsum-of-differences-of-circular-permutation%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 key idea is that $|x - y|$ is basically either $x - y$ or $y - x$. Either way, one term (either $x$ or $y$) inside the absolute will be positive, and the other term will be negative.
This means, if you have $n$ absolutes, you will have $n$ positive terms and $n$ negative terms. Now, each $x_i$ appears twice in all of these absolutes, so in total we have $2n$ terms. So, since we must have $n$ positive terms and $n$ negative terms, in order to maximize the sum, we want to make the larger $x_i$s positive and the smaller $x_i$s negative.
I will demonstrate the case where $n$ is even (odd is similar, but need some little more work). By the argument in the previous paragraph, the sum cannot exceed:
$$2( (n/2+1) + (n/2+2) + cdots + n) - 2 (1 + 2 + cdots + n/2) = 2 frac{n}{4} (frac{n}{2} + 1 + n) - 2 frac{n}{4} (1 + frac{n}{2}) = n^2 / 2$$
Which matches your bound.
answered Nov 9 '14 at 4:25
IrvanIrvan
1,673822
$endgroup$
add a comment |
$begingroup$
The key idea is that $|x - y|$ is basically either $x - y$ or $y - x$. Either way, one term (either $x$ or $y$) inside the absolute will be positive, and the other term will be negative.
This means, if you have $n$ absolutes, you will have $n$ positive terms and $n$ negative terms. Now, each $x_i$ appears twice in all of these absolutes, so in total we have $2n$ terms. So, since we must have $n$ positive terms and $n$ negative terms, in order to maximize the sum, we want to make the larger $x_i$s positive and the smaller $x_i$s negative.
I will demonstrate the case where $n$ is even (odd is similar, but need some little more work). By the argument in the previous paragraph, the sum cannot exceed:
$$2( (n/2+1) + (n/2+2) + cdots + n) - 2 (1 + 2 + cdots + n/2) = 2 frac{n}{4} (frac{n}{2} + 1 + n) - 2 frac{n}{4} (1 + frac{n}{2}) = n^2 / 2$$
Which matches your bound.
answered Nov 9 '14 at 4:25
IrvanIrvan
1,673822
$endgroup$
add a comment |
$begingroup$
The key idea is that $|x - y|$ is basically either $x - y$ or $y - x$. Either way, one term (either $x$ or $y$) inside the absolute will be positive, and the other term will be negative.
This means, if you have $n$ absolutes, you will have $n$ positive terms and $n$ negative terms. Now, each $x_i$ appears twice in all of these absolutes, so in total we have $2n$ terms. So, since we must have $n$ positive terms and $n$ negative terms, in order to maximize the sum, we want to make the larger $x_i$s positive and the smaller $x_i$s negative.
I will demonstrate the case where $n$ is even (odd is similar, but need some little more work). By the argument in the previous paragraph, the sum cannot exceed:
$$2( (n/2+1) + (n/2+2) + cdots + n) - 2 (1 + 2 + cdots + n/2) = 2 frac{n}{4} (frac{n}{2} + 1 + n) - 2 frac{n}{4} (1 + frac{n}{2}) = n^2 / 2$$
Which matches your bound.
answered Nov 9 '14 at 4:25
IrvanIrvan
1,673822
$endgroup$
The key idea is that $|x - y|$ is basically either $x - y$ or $y - x$. Either way, one term (either $x$ or $y$) inside the absolute will be positive, and the other term will be negative.
This means, if you have $n$ absolutes, you will have $n$ positive terms and $n$ negative terms. Now, each $x_i$ appears twice in all of these absolutes, so in total we have $2n$ terms. So, since we must have $n$ positive terms and $n$ negative terms, in order to maximize the sum, we want to make the larger $x_i$s positive and the smaller $x_i$s negative.
I will demonstrate the case where $n$ is even (odd is similar, but need some little more work). By the argument in the previous paragraph, the sum cannot exceed:
$$2( (n/2+1) + (n/2+2) + cdots + n) - 2 (1 + 2 + cdots + n/2) = 2 frac{n}{4} (frac{n}{2} + 1 + n) - 2 frac{n}{4} (1 + frac{n}{2}) = n^2 / 2$$
Which matches your bound.
answered Nov 9 '14 at 4:25
IrvanIrvan
1,673822
answered Nov 9 '14 at 4:25
IrvanIrvan
1,673822
answered Nov 9 '14 at 4:25
IrvanIrvan
1,673822
answered Nov 9 '14 at 4:25
IrvanIrvan
1,673822
1,673822
add a comment |
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%2f1012617%2fsum-of-differences-of-circular-permutation%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$
What did you try so far? Do you have any ideas? What sum do you get for your conjectured maximal arrangement?
$endgroup$
– flawr
Nov 8 '14 at 23:30
$begingroup$
So you get a mean difference of $(n-1)/2+lfloor n/2 rfloor/n$, I think too that this is the maximum, and I think we might perhaps be able to prove this by finding a contradiction if we assume that the mean difference is greater. (Separating the cases where n is even or odd.) But it really is a nice problem.
$endgroup$
– flawr
Nov 8 '14 at 23:42
$begingroup$
Intuitively, your first equation is never greater than the sum of $x_1+x_2+...+x_n$. Your second equation is almost equivalent to $frac{n^2}{2}$, and the sum of the first $n$ integers is $frac{n^2+n}{2}$. If the conjecture is true and you can show a minimal "loss" of approximately $frac{n}{2}$ (perhaps from $x_n-x_1$) you have found the maximum.
$endgroup$
– Ari
Nov 8 '14 at 23:47
$begingroup$
This problem is often discussed in terms of arranging numbers on a dartboard (to maximise the penalty for poor aim) so searching for "optimal dartboard" or similar may help. I think, though I may be misremembering, that all arrangements that alternate between numbers from the top half of the range and numbers from the bottom half (as yours does) are equally good and as good as possible.
$endgroup$
– aPaulT
Nov 8 '14 at 23:50