Sum of $2n$ numbers arbitrarily grouped into $2$ groups of $n$ Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Showing $sumlimits^N_n=1left(prodlimits_i=1^n b_i right)^frac1nlesumlimits^N_n=1left(prodlimits_i=1^n a_i right)^frac1n$?Proving the Schwarz Inequality for Complex Numbers using InductionPartition onto subsets at the same sumProve $b-a le sum^n_i=1(b_i-a_i)$ by inductionIf $sum_i = 1^n a_i b_i = sum_i = 1^n a_i^2 = sum_i = 1^n b_i^2$, then $a_i = b_i$ for all $i$.Prove by induction on $n$ that every product of $n$ sums of two squares is a sum of two squaresHow to find the expectation of sorted arrays?If $a_n = sumlimits_r=0^n binomnr b_r$, prove $(-1)^n b_n = sumlimits_s=0^n binomns (-1)^s a_s$Pigeonhole principle in finite sequenceFinding $sum_i=1^100 a_i$ given that $sqrta_1+sqrta_2-1+sqrta_3-2+dots+sqrta_n-(n-1)=frac12(a_1+a_2+dots+a_n)=fracn(n-3)4$
Do wooden building fires get hotter than 600°C?
Why weren't discrete x86 CPUs ever used in game hardware?
What is a fractional matching?
Why is it faster to reheat something than it is to cook it?
Sum letters are not two different
Take 2! Is this homebrew Lady of Pain warlock patron balanced?
Did Deadpool rescue all of the X-Force?
How do I find out the mythology and history of my Fortress?
What order were files/directories outputted in dir?
Why do early math courses focus on the cross sections of a cone and not on other 3D objects?
Why should I vote and accept answers?
Generate an RGB colour grid
Project Euler #1 in C++
SF book about people trapped in a series of worlds they imagine
Why do we need to use the builder design pattern when we can do the same thing with setters?
If Windows 7 doesn't support WSL, then what does Linux subsystem option mean?
How would a mousetrap for use in space work?
Is CEO the "profession" with the most psychopaths?
How come Sam didn't become Lord of Horn Hill?
What are the out-of-universe reasons for the references to Toby Maguire-era Spider-Man in Into the Spider-Verse?
What are the diatonic extended chords of C major?
How much damage would a cupful of neutron star matter do to the Earth?
Central Vacuuming: Is it worth it, and how does it compare to normal vacuuming?
Can a new player join a group only when a new campaign starts?
Sum of $2n$ numbers arbitrarily grouped into $2$ groups of $n$
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Showing $sumlimits^N_n=1left(prodlimits_i=1^n b_i right)^frac1nlesumlimits^N_n=1left(prodlimits_i=1^n a_i right)^frac1n$?Proving the Schwarz Inequality for Complex Numbers using InductionPartition onto subsets at the same sumProve $b-a le sum^n_i=1(b_i-a_i)$ by inductionIf $sum_i = 1^n a_i b_i = sum_i = 1^n a_i^2 = sum_i = 1^n b_i^2$, then $a_i = b_i$ for all $i$.Prove by induction on $n$ that every product of $n$ sums of two squares is a sum of two squaresHow to find the expectation of sorted arrays?If $a_n = sumlimits_r=0^n binomnr b_r$, prove $(-1)^n b_n = sumlimits_s=0^n binomns (-1)^s a_s$Pigeonhole principle in finite sequenceFinding $sum_i=1^100 a_i$ given that $sqrta_1+sqrta_2-1+sqrta_3-2+dots+sqrta_n-(n-1)=frac12(a_1+a_2+dots+a_n)=fracn(n-3)4$
$begingroup$
The first $2n$ natural numbers are arbitrarily divided into $2$ groups of $n$ each. The first group (named $a$) is arranged $a_1<ldots<a_n$. The second group ($b$) is arranged $b_1>ldots>b_n$. Find, with proof, the sum $|a_1-b_1| + ldots + |a_n-b_n|$. Or more compactly $$sum_i=1^n |a_i-b_i|$$
(Guess: Arbitrarily means any possible group of $n$ numbers. The modulus can't be removed because any sum can be a negative number.)
Some pattern
(not sure how to create a table here)
n=1, sum=1,
n=2, sum=4, diff=3
n=3, sum=9, diff=5
n=4, sum=16, diff=7
n=5, sum=25, diff=9
I'm not a mathematician, and am just looking for some help about to start thinking on the problem. Don't solve it (but if it is solved anywhere I appreciate the link).
combinatorics discrete-mathematics summation induction
edited Mar 30 at 21:34
Maria Mazur
50.3k1361126
asked Mar 27 at 17:02
santimirandarpsantimirandarp
213111
$endgroup$
add a comment |
$begingroup$
The first $2n$ natural numbers are arbitrarily divided into $2$ groups of $n$ each. The first group (named $a$) is arranged $a_1<ldots<a_n$. The second group ($b$) is arranged $b_1>ldots>b_n$. Find, with proof, the sum $|a_1-b_1| + ldots + |a_n-b_n|$. Or more compactly $$sum_i=1^n |a_i-b_i|$$
(Guess: Arbitrarily means any possible group of $n$ numbers. The modulus can't be removed because any sum can be a negative number.)
Some pattern
(not sure how to create a table here)
n=1, sum=1,
n=2, sum=4, diff=3
n=3, sum=9, diff=5
n=4, sum=16, diff=7
n=5, sum=25, diff=9
I'm not a mathematician, and am just looking for some help about to start thinking on the problem. Don't solve it (but if it is solved anywhere I appreciate the link).
combinatorics discrete-mathematics summation induction
edited Mar 30 at 21:34
Maria Mazur
50.3k1361126
asked Mar 27 at 17:02
santimirandarpsantimirandarp
213111
$endgroup$
add a comment |
$begingroup$
The first $2n$ natural numbers are arbitrarily divided into $2$ groups of $n$ each. The first group (named $a$) is arranged $a_1<ldots<a_n$. The second group ($b$) is arranged $b_1>ldots>b_n$. Find, with proof, the sum $|a_1-b_1| + ldots + |a_n-b_n|$. Or more compactly $$sum_i=1^n |a_i-b_i|$$
(Guess: Arbitrarily means any possible group of $n$ numbers. The modulus can't be removed because any sum can be a negative number.)
Some pattern
(not sure how to create a table here)
n=1, sum=1,
n=2, sum=4, diff=3
n=3, sum=9, diff=5
n=4, sum=16, diff=7
n=5, sum=25, diff=9
I'm not a mathematician, and am just looking for some help about to start thinking on the problem. Don't solve it (but if it is solved anywhere I appreciate the link).
combinatorics discrete-mathematics summation induction
edited Mar 30 at 21:34
Maria Mazur
50.3k1361126
asked Mar 27 at 17:02
santimirandarpsantimirandarp
213111
$endgroup$
The first $2n$ natural numbers are arbitrarily divided into $2$ groups of $n$ each. The first group (named $a$) is arranged $a_1<ldots<a_n$. The second group ($b$) is arranged $b_1>ldots>b_n$. Find, with proof, the sum $|a_1-b_1| + ldots + |a_n-b_n|$. Or more compactly $$sum_i=1^n |a_i-b_i|$$
(Guess: Arbitrarily means any possible group of $n$ numbers. The modulus can't be removed because any sum can be a negative number.)
Some pattern
(not sure how to create a table here)
n=1, sum=1,
n=2, sum=4, diff=3
n=3, sum=9, diff=5
n=4, sum=16, diff=7
n=5, sum=25, diff=9
I'm not a mathematician, and am just looking for some help about to start thinking on the problem. Don't solve it (but if it is solved anywhere I appreciate the link).
combinatorics discrete-mathematics summation induction
combinatorics discrete-mathematics summation induction
edited Mar 30 at 21:34
Maria Mazur
50.3k1361126
asked Mar 27 at 17:02
santimirandarpsantimirandarp
213111
edited Mar 30 at 21:34
Maria Mazur
50.3k1361126
asked Mar 27 at 17:02
santimirandarpsantimirandarp
213111
edited Mar 30 at 21:34
Maria Mazur
50.3k1361126
edited Mar 30 at 21:34
Maria Mazur
50.3k1361126
edited Mar 30 at 21:34
Maria Mazur
50.3k1361126
50.3k1361126
asked Mar 27 at 17:02
santimirandarpsantimirandarp
213111
asked Mar 27 at 17:02
santimirandarpsantimirandarp
213111
asked Mar 27 at 17:02
santimirandarpsantimirandarp
213111
213111
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Suppose we color the two groups of number red and green, respectively.
We can reach any distribution of colors by starting with "$1$ to $n$ red and $n+1$ to $2n$ green", and then some number of times interchange the colors of two neighboring numbers.
If you can prove that a single interchange will never change your sum-of-differences, you will have proved that the sum doesn't depend on the coloring, and that you can compute that sum from the initial color distribution.
answered Mar 27 at 17:31
Henning MakholmHenning Makholm
244k17312556
$endgroup$
$begingroup$
I don't think I can prove that, though. Once done I guess then we will be able to remove the modulus and use something like gauss sum of natural numbers. Thanks for your ideas...
$endgroup$
– santimirandarp
Mar 27 at 17:50
$begingroup$
@santimirandarp: I would do case analysis on whether there are more, fewer, or the same count of green numbers to the left of our chosen pair than there are red numbers to the right.
$endgroup$
– Henning Makholm
Mar 27 at 18:12
add a comment |
$begingroup$
Try the following approach:
Experiment -- you may notice that the sum of the absolute differences always seems to be n^2
Take the simplest case, where the first n numbers are in the first group and the second n are in the second group. Then the sum of the elements of the first group will be 1/2*n*(n+1), and the sum of the elements of the second group will be n/2*(3n+1) and the difference (which is the same as the differences of the absolute values of the ordered set as all members of the first group are less than all members of the second) is just n^2
Show that taking any subset of the first group as in 2 above, and swapping with any equivalent-sized subset of the second group does not alter the sum of the differences of the absolute values since the ordering always leads to the smaller ones being subtracted from larger ones, which means that all numbers end up having the same sign as in calculation 2.
answered Mar 29 at 11:43
Mark ThomasMark Thomas
111
$endgroup$
add a comment |
$begingroup$
Hint: For every $k$ we have $$a_k+1-a_k >0 >b_k+1-b_k$$
so $$ a_k+1-b_k+1> a_k-b_k$$
This should kill the problem...?
answered Mar 30 at 21:33
Maria MazurMaria Mazur
50.3k1361126
$endgroup$
add a comment |
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
);
);
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%2f3164780%2fsum-of-2n-numbers-arbitrarily-grouped-into-2-groups-of-n%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Suppose we color the two groups of number red and green, respectively.
We can reach any distribution of colors by starting with "$1$ to $n$ red and $n+1$ to $2n$ green", and then some number of times interchange the colors of two neighboring numbers.
If you can prove that a single interchange will never change your sum-of-differences, you will have proved that the sum doesn't depend on the coloring, and that you can compute that sum from the initial color distribution.
answered Mar 27 at 17:31
Henning MakholmHenning Makholm
244k17312556
$endgroup$
$begingroup$
I don't think I can prove that, though. Once done I guess then we will be able to remove the modulus and use something like gauss sum of natural numbers. Thanks for your ideas...
$endgroup$
– santimirandarp
Mar 27 at 17:50
$begingroup$
@santimirandarp: I would do case analysis on whether there are more, fewer, or the same count of green numbers to the left of our chosen pair than there are red numbers to the right.
$endgroup$
– Henning Makholm
Mar 27 at 18:12
add a comment |
$begingroup$
Suppose we color the two groups of number red and green, respectively.
We can reach any distribution of colors by starting with "$1$ to $n$ red and $n+1$ to $2n$ green", and then some number of times interchange the colors of two neighboring numbers.
If you can prove that a single interchange will never change your sum-of-differences, you will have proved that the sum doesn't depend on the coloring, and that you can compute that sum from the initial color distribution.
answered Mar 27 at 17:31
Henning MakholmHenning Makholm
244k17312556
$endgroup$
$begingroup$
I don't think I can prove that, though. Once done I guess then we will be able to remove the modulus and use something like gauss sum of natural numbers. Thanks for your ideas...
$endgroup$
– santimirandarp
Mar 27 at 17:50
$begingroup$
@santimirandarp: I would do case analysis on whether there are more, fewer, or the same count of green numbers to the left of our chosen pair than there are red numbers to the right.
$endgroup$
– Henning Makholm
Mar 27 at 18:12
add a comment |
$begingroup$
Suppose we color the two groups of number red and green, respectively.
We can reach any distribution of colors by starting with "$1$ to $n$ red and $n+1$ to $2n$ green", and then some number of times interchange the colors of two neighboring numbers.
If you can prove that a single interchange will never change your sum-of-differences, you will have proved that the sum doesn't depend on the coloring, and that you can compute that sum from the initial color distribution.
answered Mar 27 at 17:31
Henning MakholmHenning Makholm
244k17312556
$endgroup$
Suppose we color the two groups of number red and green, respectively.
We can reach any distribution of colors by starting with "$1$ to $n$ red and $n+1$ to $2n$ green", and then some number of times interchange the colors of two neighboring numbers.
If you can prove that a single interchange will never change your sum-of-differences, you will have proved that the sum doesn't depend on the coloring, and that you can compute that sum from the initial color distribution.
answered Mar 27 at 17:31
Henning MakholmHenning Makholm
244k17312556
answered Mar 27 at 17:31
Henning MakholmHenning Makholm
244k17312556
answered Mar 27 at 17:31
Henning MakholmHenning Makholm
244k17312556
answered Mar 27 at 17:31
Henning MakholmHenning Makholm
244k17312556
244k17312556
$begingroup$
I don't think I can prove that, though. Once done I guess then we will be able to remove the modulus and use something like gauss sum of natural numbers. Thanks for your ideas...
$endgroup$
– santimirandarp
Mar 27 at 17:50
$begingroup$
@santimirandarp: I would do case analysis on whether there are more, fewer, or the same count of green numbers to the left of our chosen pair than there are red numbers to the right.
$endgroup$
– Henning Makholm
Mar 27 at 18:12
add a comment |
$begingroup$
I don't think I can prove that, though. Once done I guess then we will be able to remove the modulus and use something like gauss sum of natural numbers. Thanks for your ideas...
$endgroup$
– santimirandarp
Mar 27 at 17:50
$begingroup$
@santimirandarp: I would do case analysis on whether there are more, fewer, or the same count of green numbers to the left of our chosen pair than there are red numbers to the right.
$endgroup$
– Henning Makholm
Mar 27 at 18:12
$begingroup$
I don't think I can prove that, though. Once done I guess then we will be able to remove the modulus and use something like gauss sum of natural numbers. Thanks for your ideas...
$endgroup$
– santimirandarp
Mar 27 at 17:50
$begingroup$
I don't think I can prove that, though. Once done I guess then we will be able to remove the modulus and use something like gauss sum of natural numbers. Thanks for your ideas...
$endgroup$
– santimirandarp
Mar 27 at 17:50
$begingroup$
@santimirandarp: I would do case analysis on whether there are more, fewer, or the same count of green numbers to the left of our chosen pair than there are red numbers to the right.
$endgroup$
– Henning Makholm
Mar 27 at 18:12
$begingroup$
@santimirandarp: I would do case analysis on whether there are more, fewer, or the same count of green numbers to the left of our chosen pair than there are red numbers to the right.
$endgroup$
– Henning Makholm
Mar 27 at 18:12
add a comment |
$begingroup$
Try the following approach:
Experiment -- you may notice that the sum of the absolute differences always seems to be n^2
Take the simplest case, where the first n numbers are in the first group and the second n are in the second group. Then the sum of the elements of the first group will be 1/2*n*(n+1), and the sum of the elements of the second group will be n/2*(3n+1) and the difference (which is the same as the differences of the absolute values of the ordered set as all members of the first group are less than all members of the second) is just n^2
Show that taking any subset of the first group as in 2 above, and swapping with any equivalent-sized subset of the second group does not alter the sum of the differences of the absolute values since the ordering always leads to the smaller ones being subtracted from larger ones, which means that all numbers end up having the same sign as in calculation 2.
answered Mar 29 at 11:43
Mark ThomasMark Thomas
111
$endgroup$
add a comment |
$begingroup$
Try the following approach:
Experiment -- you may notice that the sum of the absolute differences always seems to be n^2
Take the simplest case, where the first n numbers are in the first group and the second n are in the second group. Then the sum of the elements of the first group will be 1/2*n*(n+1), and the sum of the elements of the second group will be n/2*(3n+1) and the difference (which is the same as the differences of the absolute values of the ordered set as all members of the first group are less than all members of the second) is just n^2
Show that taking any subset of the first group as in 2 above, and swapping with any equivalent-sized subset of the second group does not alter the sum of the differences of the absolute values since the ordering always leads to the smaller ones being subtracted from larger ones, which means that all numbers end up having the same sign as in calculation 2.
answered Mar 29 at 11:43
Mark ThomasMark Thomas
111
$endgroup$
add a comment |
$begingroup$
Try the following approach:
Experiment -- you may notice that the sum of the absolute differences always seems to be n^2
Take the simplest case, where the first n numbers are in the first group and the second n are in the second group. Then the sum of the elements of the first group will be 1/2*n*(n+1), and the sum of the elements of the second group will be n/2*(3n+1) and the difference (which is the same as the differences of the absolute values of the ordered set as all members of the first group are less than all members of the second) is just n^2
Show that taking any subset of the first group as in 2 above, and swapping with any equivalent-sized subset of the second group does not alter the sum of the differences of the absolute values since the ordering always leads to the smaller ones being subtracted from larger ones, which means that all numbers end up having the same sign as in calculation 2.
answered Mar 29 at 11:43
Mark ThomasMark Thomas
111
$endgroup$
Try the following approach:
Experiment -- you may notice that the sum of the absolute differences always seems to be n^2
Take the simplest case, where the first n numbers are in the first group and the second n are in the second group. Then the sum of the elements of the first group will be 1/2*n*(n+1), and the sum of the elements of the second group will be n/2*(3n+1) and the difference (which is the same as the differences of the absolute values of the ordered set as all members of the first group are less than all members of the second) is just n^2
Show that taking any subset of the first group as in 2 above, and swapping with any equivalent-sized subset of the second group does not alter the sum of the differences of the absolute values since the ordering always leads to the smaller ones being subtracted from larger ones, which means that all numbers end up having the same sign as in calculation 2.
answered Mar 29 at 11:43
Mark ThomasMark Thomas
111
answered Mar 29 at 11:43
Mark ThomasMark Thomas
111
answered Mar 29 at 11:43
Mark ThomasMark Thomas
111
answered Mar 29 at 11:43
Mark ThomasMark Thomas
111
111
add a comment |
add a comment |
$begingroup$
Hint: For every $k$ we have $$a_k+1-a_k >0 >b_k+1-b_k$$
so $$ a_k+1-b_k+1> a_k-b_k$$
This should kill the problem...?
answered Mar 30 at 21:33
Maria MazurMaria Mazur
50.3k1361126
$endgroup$
add a comment |
$begingroup$
Hint: For every $k$ we have $$a_k+1-a_k >0 >b_k+1-b_k$$
so $$ a_k+1-b_k+1> a_k-b_k$$
This should kill the problem...?
answered Mar 30 at 21:33
Maria MazurMaria Mazur
50.3k1361126
$endgroup$
add a comment |
$begingroup$
Hint: For every $k$ we have $$a_k+1-a_k >0 >b_k+1-b_k$$
so $$ a_k+1-b_k+1> a_k-b_k$$
This should kill the problem...?
answered Mar 30 at 21:33
Maria MazurMaria Mazur
50.3k1361126
$endgroup$
Hint: For every $k$ we have $$a_k+1-a_k >0 >b_k+1-b_k$$
so $$ a_k+1-b_k+1> a_k-b_k$$
This should kill the problem...?
answered Mar 30 at 21:33
Maria MazurMaria Mazur
50.3k1361126
answered Mar 30 at 21:33
Maria MazurMaria Mazur
50.3k1361126
answered Mar 30 at 21:33
Maria MazurMaria Mazur
50.3k1361126
answered Mar 30 at 21:33
Maria MazurMaria Mazur
50.3k1361126
50.3k1361126
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%2f3164780%2fsum-of-2n-numbers-arbitrarily-grouped-into-2-groups-of-n%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
