Find a number having minimum sum of distances between a set of numbers
$begingroup$
Lets say we have a set of numbers ${ 5, 7, 1, 2, 5, 100 }$. I want to find a number $x$ such that the sum of distances of every number from the set to $x$ is minimal.
My first thought was that $x$ is the average of all elements of the set: $frac{5+7+1+2+5+100}{6}$, but it is not true, it fails the above example.
Any help or hint will be appriciated, thanks.
optimization average median
asked Jan 29 at 10:58
Abdenaceur LichihebAbdenaceur Lichiheb
1436
$endgroup$
|
show 1 more comment
$begingroup$
Lets say we have a set of numbers ${ 5, 7, 1, 2, 5, 100 }$. I want to find a number $x$ such that the sum of distances of every number from the set to $x$ is minimal.
My first thought was that $x$ is the average of all elements of the set: $frac{5+7+1+2+5+100}{6}$, but it is not true, it fails the above example.
Any help or hint will be appriciated, thanks.
optimization average median
asked Jan 29 at 10:58
Abdenaceur LichihebAbdenaceur Lichiheb
1436
$endgroup$
$begingroup$
The answer is wrong. For example, $100$ is closer to each element than $104$ is.
$endgroup$
– Harnak
Jan 29 at 11:01
2
$begingroup$
math.stackexchange.com/questions/113270/…
$endgroup$
– Matti P.
Jan 29 at 11:04
$begingroup$
@Harnak Sorry but I don't quite understand your statement. $104$ is the total distance $sum_{x in S} |x - n|$ where $n$ is the desired number and $S = {1, 2, 5, 5, 7, 100}$. How do you achieve $100$? See my proof.
$endgroup$
– L. F.
Jan 29 at 11:12
$begingroup$
@L.F., I was just answering to the OP before editing. He stated that the solution was 104, but I thought he referred to the minimizer and not to the distance. So, that's why I provided an example of why 104 couldn't be a minimizer. I think I just misinterpreted what he meant.
$endgroup$
– Harnak
Jan 29 at 11:16
$begingroup$
@Harnak Oh, never mind. Everybody makes mistakes :)
$endgroup$
– L. F.
Jan 29 at 11:17
|
show 1 more comment
$begingroup$
Lets say we have a set of numbers ${ 5, 7, 1, 2, 5, 100 }$. I want to find a number $x$ such that the sum of distances of every number from the set to $x$ is minimal.
My first thought was that $x$ is the average of all elements of the set: $frac{5+7+1+2+5+100}{6}$, but it is not true, it fails the above example.
Any help or hint will be appriciated, thanks.
optimization average median
asked Jan 29 at 10:58
Abdenaceur LichihebAbdenaceur Lichiheb
1436
$endgroup$
Lets say we have a set of numbers ${ 5, 7, 1, 2, 5, 100 }$. I want to find a number $x$ such that the sum of distances of every number from the set to $x$ is minimal.
My first thought was that $x$ is the average of all elements of the set: $frac{5+7+1+2+5+100}{6}$, but it is not true, it fails the above example.
Any help or hint will be appriciated, thanks.
optimization average median
optimization average median
asked Jan 29 at 10:58
Abdenaceur LichihebAbdenaceur Lichiheb
1436
asked Jan 29 at 10:58
Abdenaceur LichihebAbdenaceur Lichiheb
1436
edited Jan 30 at 10:40
Abdenaceur Lichiheb
asked Jan 29 at 10:58
Abdenaceur LichihebAbdenaceur Lichiheb
1436
asked Jan 29 at 10:58
Abdenaceur LichihebAbdenaceur Lichiheb
1436
asked Jan 29 at 10:58
Abdenaceur LichihebAbdenaceur Lichiheb
1436
1436
$begingroup$
The answer is wrong. For example, $100$ is closer to each element than $104$ is.
$endgroup$
– Harnak
Jan 29 at 11:01
2
$begingroup$
math.stackexchange.com/questions/113270/…
$endgroup$
– Matti P.
Jan 29 at 11:04
$begingroup$
@Harnak Sorry but I don't quite understand your statement. $104$ is the total distance $sum_{x in S} |x - n|$ where $n$ is the desired number and $S = {1, 2, 5, 5, 7, 100}$. How do you achieve $100$? See my proof.
$endgroup$
– L. F.
Jan 29 at 11:12
$begingroup$
@L.F., I was just answering to the OP before editing. He stated that the solution was 104, but I thought he referred to the minimizer and not to the distance. So, that's why I provided an example of why 104 couldn't be a minimizer. I think I just misinterpreted what he meant.
$endgroup$
– Harnak
Jan 29 at 11:16
$begingroup$
@Harnak Oh, never mind. Everybody makes mistakes :)
$endgroup$
– L. F.
Jan 29 at 11:17
|
show 1 more comment
$begingroup$
The answer is wrong. For example, $100$ is closer to each element than $104$ is.
$endgroup$
– Harnak
Jan 29 at 11:01
2
$begingroup$
math.stackexchange.com/questions/113270/…
$endgroup$
– Matti P.
Jan 29 at 11:04
$begingroup$
@Harnak Sorry but I don't quite understand your statement. $104$ is the total distance $sum_{x in S} |x - n|$ where $n$ is the desired number and $S = {1, 2, 5, 5, 7, 100}$. How do you achieve $100$? See my proof.
$endgroup$
– L. F.
Jan 29 at 11:12
$begingroup$
@L.F., I was just answering to the OP before editing. He stated that the solution was 104, but I thought he referred to the minimizer and not to the distance. So, that's why I provided an example of why 104 couldn't be a minimizer. I think I just misinterpreted what he meant.
$endgroup$
– Harnak
Jan 29 at 11:16
$begingroup$
@Harnak Oh, never mind. Everybody makes mistakes :)
$endgroup$
– L. F.
Jan 29 at 11:17
$begingroup$
The answer is wrong. For example, $100$ is closer to each element than $104$ is.
$endgroup$
– Harnak
Jan 29 at 11:01
$begingroup$
The answer is wrong. For example, $100$ is closer to each element than $104$ is.
$endgroup$
– Harnak
Jan 29 at 11:01
2
2
$begingroup$
math.stackexchange.com/questions/113270/…
$endgroup$
– Matti P.
Jan 29 at 11:04
$begingroup$
math.stackexchange.com/questions/113270/…
$endgroup$
– Matti P.
Jan 29 at 11:04
$begingroup$
@Harnak Sorry but I don't quite understand your statement. $104$ is the total distance $sum_{x in S} |x - n|$ where $n$ is the desired number and $S = {1, 2, 5, 5, 7, 100}$. How do you achieve $100$? See my proof.
$endgroup$
– L. F.
Jan 29 at 11:12
$begingroup$
@Harnak Sorry but I don't quite understand your statement. $104$ is the total distance $sum_{x in S} |x - n|$ where $n$ is the desired number and $S = {1, 2, 5, 5, 7, 100}$. How do you achieve $100$? See my proof.
$endgroup$
– L. F.
Jan 29 at 11:12
$begingroup$
@L.F., I was just answering to the OP before editing. He stated that the solution was 104, but I thought he referred to the minimizer and not to the distance. So, that's why I provided an example of why 104 couldn't be a minimizer. I think I just misinterpreted what he meant.
$endgroup$
– Harnak
Jan 29 at 11:16
$begingroup$
@L.F., I was just answering to the OP before editing. He stated that the solution was 104, but I thought he referred to the minimizer and not to the distance. So, that's why I provided an example of why 104 couldn't be a minimizer. I think I just misinterpreted what he meant.
$endgroup$
– Harnak
Jan 29 at 11:16
$begingroup$
@Harnak Oh, never mind. Everybody makes mistakes :)
$endgroup$
– L. F.
Jan 29 at 11:17
$begingroup$
@Harnak Oh, never mind. Everybody makes mistakes :)
$endgroup$
– L. F.
Jan 29 at 11:17
|
show 1 more comment
2 Answers
2
active
oldest
votes
$begingroup$
You are looking to minimize $$sum_{y in A} |y - x|$$
with respect to $x$ where $A$ is your set.
It can be proved that any median minimizes this problem. In your case, the only median is $5$, so that's the result.
answered Jan 29 at 11:06
HarnakHarnak
1,309512
$endgroup$
9
$begingroup$
I upvoted your answer because it's correct, but I'd like to make a suggestion about the phrase "this is a well known result": it appears to serve the purpose of making you look well-read, and the OP look ignorant, which might both be true, but does saying it help? Probably not. If you'd included a reference, that'd be great -- OP could learn something. Most likely, this exercise is leading up to the very result you cited, and explaining the computation in this case would be more educational than citing the very thing that can be proved in general from similar computations.
$endgroup$
– John Hughes
Jan 29 at 13:26
$begingroup$
You're right. However, that was not my intent. I'll edit this. Thanks for the suggestion :)
$endgroup$
– Harnak
Jan 29 at 23:15
add a comment |
$begingroup$
First sort your [multi]set: ${1, 2, 5, 5, 7, 100}$. The number you want is $5$. The sum is $4 + 3 + 0 + 0 + 2 + 95 = 104.$
Proof: suppose you have another number $n neq 5$.
Note that for any number $x$, $|x - a| + |x - b| le |a - b|$.
Hence, it must hold that the sum of its distances to the two $5$s, i.e. $$|n - 5| + |n - 5| ge |5 - 5| + |5 - 5| = 0.$$ Similarly, $$|n - 2| + |n - 7| ge |5 - 2| + |5 - 7| = 5,$$
$$|n - 1| + |n - 100| ge |5 - 1| + |5 - 100| = 99.$$
You can't have the total distance any lower.
Q.E.D.
In general, first sort your set, then any number between (including) the middle two numbers will do. For example, for set ${1, 2, 3, 4, 5, 6}$, any $x$ such that $3 le x le 4$ does.
answered Jan 29 at 11:06
L. F.L. F.
18511
$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%2f3092033%2ffind-a-number-having-minimum-sum-of-distances-between-a-set-of-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You are looking to minimize $$sum_{y in A} |y - x|$$
with respect to $x$ where $A$ is your set.
It can be proved that any median minimizes this problem. In your case, the only median is $5$, so that's the result.
answered Jan 29 at 11:06
HarnakHarnak
1,309512
$endgroup$
9
$begingroup$
I upvoted your answer because it's correct, but I'd like to make a suggestion about the phrase "this is a well known result": it appears to serve the purpose of making you look well-read, and the OP look ignorant, which might both be true, but does saying it help? Probably not. If you'd included a reference, that'd be great -- OP could learn something. Most likely, this exercise is leading up to the very result you cited, and explaining the computation in this case would be more educational than citing the very thing that can be proved in general from similar computations.
$endgroup$
– John Hughes
Jan 29 at 13:26
$begingroup$
You're right. However, that was not my intent. I'll edit this. Thanks for the suggestion :)
$endgroup$
– Harnak
Jan 29 at 23:15
add a comment |
$begingroup$
You are looking to minimize $$sum_{y in A} |y - x|$$
with respect to $x$ where $A$ is your set.
It can be proved that any median minimizes this problem. In your case, the only median is $5$, so that's the result.
answered Jan 29 at 11:06
HarnakHarnak
1,309512
$endgroup$
9
$begingroup$
I upvoted your answer because it's correct, but I'd like to make a suggestion about the phrase "this is a well known result": it appears to serve the purpose of making you look well-read, and the OP look ignorant, which might both be true, but does saying it help? Probably not. If you'd included a reference, that'd be great -- OP could learn something. Most likely, this exercise is leading up to the very result you cited, and explaining the computation in this case would be more educational than citing the very thing that can be proved in general from similar computations.
$endgroup$
– John Hughes
Jan 29 at 13:26
$begingroup$
You're right. However, that was not my intent. I'll edit this. Thanks for the suggestion :)
$endgroup$
– Harnak
Jan 29 at 23:15
add a comment |
$begingroup$
You are looking to minimize $$sum_{y in A} |y - x|$$
with respect to $x$ where $A$ is your set.
It can be proved that any median minimizes this problem. In your case, the only median is $5$, so that's the result.
answered Jan 29 at 11:06
HarnakHarnak
1,309512
$endgroup$
You are looking to minimize $$sum_{y in A} |y - x|$$
with respect to $x$ where $A$ is your set.
It can be proved that any median minimizes this problem. In your case, the only median is $5$, so that's the result.
answered Jan 29 at 11:06
HarnakHarnak
1,309512
edited Jan 29 at 23:50
answered Jan 29 at 11:06
HarnakHarnak
1,309512
answered Jan 29 at 11:06
HarnakHarnak
1,309512
answered Jan 29 at 11:06
HarnakHarnak
1,309512
1,309512
9
$begingroup$
I upvoted your answer because it's correct, but I'd like to make a suggestion about the phrase "this is a well known result": it appears to serve the purpose of making you look well-read, and the OP look ignorant, which might both be true, but does saying it help? Probably not. If you'd included a reference, that'd be great -- OP could learn something. Most likely, this exercise is leading up to the very result you cited, and explaining the computation in this case would be more educational than citing the very thing that can be proved in general from similar computations.
$endgroup$
– John Hughes
Jan 29 at 13:26
$begingroup$
You're right. However, that was not my intent. I'll edit this. Thanks for the suggestion :)
$endgroup$
– Harnak
Jan 29 at 23:15
add a comment |
9
$begingroup$
I upvoted your answer because it's correct, but I'd like to make a suggestion about the phrase "this is a well known result": it appears to serve the purpose of making you look well-read, and the OP look ignorant, which might both be true, but does saying it help? Probably not. If you'd included a reference, that'd be great -- OP could learn something. Most likely, this exercise is leading up to the very result you cited, and explaining the computation in this case would be more educational than citing the very thing that can be proved in general from similar computations.
$endgroup$
– John Hughes
Jan 29 at 13:26
$begingroup$
You're right. However, that was not my intent. I'll edit this. Thanks for the suggestion :)
$endgroup$
– Harnak
Jan 29 at 23:15
9
9
$begingroup$
I upvoted your answer because it's correct, but I'd like to make a suggestion about the phrase "this is a well known result": it appears to serve the purpose of making you look well-read, and the OP look ignorant, which might both be true, but does saying it help? Probably not. If you'd included a reference, that'd be great -- OP could learn something. Most likely, this exercise is leading up to the very result you cited, and explaining the computation in this case would be more educational than citing the very thing that can be proved in general from similar computations.
$endgroup$
– John Hughes
Jan 29 at 13:26
$begingroup$
I upvoted your answer because it's correct, but I'd like to make a suggestion about the phrase "this is a well known result": it appears to serve the purpose of making you look well-read, and the OP look ignorant, which might both be true, but does saying it help? Probably not. If you'd included a reference, that'd be great -- OP could learn something. Most likely, this exercise is leading up to the very result you cited, and explaining the computation in this case would be more educational than citing the very thing that can be proved in general from similar computations.
$endgroup$
– John Hughes
Jan 29 at 13:26
$begingroup$
You're right. However, that was not my intent. I'll edit this. Thanks for the suggestion :)
$endgroup$
– Harnak
Jan 29 at 23:15
$begingroup$
You're right. However, that was not my intent. I'll edit this. Thanks for the suggestion :)
$endgroup$
– Harnak
Jan 29 at 23:15
add a comment |
$begingroup$
First sort your [multi]set: ${1, 2, 5, 5, 7, 100}$. The number you want is $5$. The sum is $4 + 3 + 0 + 0 + 2 + 95 = 104.$
Proof: suppose you have another number $n neq 5$.
Note that for any number $x$, $|x - a| + |x - b| le |a - b|$.
Hence, it must hold that the sum of its distances to the two $5$s, i.e. $$|n - 5| + |n - 5| ge |5 - 5| + |5 - 5| = 0.$$ Similarly, $$|n - 2| + |n - 7| ge |5 - 2| + |5 - 7| = 5,$$
$$|n - 1| + |n - 100| ge |5 - 1| + |5 - 100| = 99.$$
You can't have the total distance any lower.
Q.E.D.
In general, first sort your set, then any number between (including) the middle two numbers will do. For example, for set ${1, 2, 3, 4, 5, 6}$, any $x$ such that $3 le x le 4$ does.
answered Jan 29 at 11:06
L. F.L. F.
18511
$endgroup$
add a comment |
$begingroup$
First sort your [multi]set: ${1, 2, 5, 5, 7, 100}$. The number you want is $5$. The sum is $4 + 3 + 0 + 0 + 2 + 95 = 104.$
Proof: suppose you have another number $n neq 5$.
Note that for any number $x$, $|x - a| + |x - b| le |a - b|$.
Hence, it must hold that the sum of its distances to the two $5$s, i.e. $$|n - 5| + |n - 5| ge |5 - 5| + |5 - 5| = 0.$$ Similarly, $$|n - 2| + |n - 7| ge |5 - 2| + |5 - 7| = 5,$$
$$|n - 1| + |n - 100| ge |5 - 1| + |5 - 100| = 99.$$
You can't have the total distance any lower.
Q.E.D.
In general, first sort your set, then any number between (including) the middle two numbers will do. For example, for set ${1, 2, 3, 4, 5, 6}$, any $x$ such that $3 le x le 4$ does.
answered Jan 29 at 11:06
L. F.L. F.
18511
$endgroup$
add a comment |
$begingroup$
First sort your [multi]set: ${1, 2, 5, 5, 7, 100}$. The number you want is $5$. The sum is $4 + 3 + 0 + 0 + 2 + 95 = 104.$
Proof: suppose you have another number $n neq 5$.
Note that for any number $x$, $|x - a| + |x - b| le |a - b|$.
Hence, it must hold that the sum of its distances to the two $5$s, i.e. $$|n - 5| + |n - 5| ge |5 - 5| + |5 - 5| = 0.$$ Similarly, $$|n - 2| + |n - 7| ge |5 - 2| + |5 - 7| = 5,$$
$$|n - 1| + |n - 100| ge |5 - 1| + |5 - 100| = 99.$$
You can't have the total distance any lower.
Q.E.D.
In general, first sort your set, then any number between (including) the middle two numbers will do. For example, for set ${1, 2, 3, 4, 5, 6}$, any $x$ such that $3 le x le 4$ does.
answered Jan 29 at 11:06
L. F.L. F.
18511
$endgroup$
First sort your [multi]set: ${1, 2, 5, 5, 7, 100}$. The number you want is $5$. The sum is $4 + 3 + 0 + 0 + 2 + 95 = 104.$
Proof: suppose you have another number $n neq 5$.
Note that for any number $x$, $|x - a| + |x - b| le |a - b|$.
Hence, it must hold that the sum of its distances to the two $5$s, i.e. $$|n - 5| + |n - 5| ge |5 - 5| + |5 - 5| = 0.$$ Similarly, $$|n - 2| + |n - 7| ge |5 - 2| + |5 - 7| = 5,$$
$$|n - 1| + |n - 100| ge |5 - 1| + |5 - 100| = 99.$$
You can't have the total distance any lower.
Q.E.D.
In general, first sort your set, then any number between (including) the middle two numbers will do. For example, for set ${1, 2, 3, 4, 5, 6}$, any $x$ such that $3 le x le 4$ does.
answered Jan 29 at 11:06
L. F.L. F.
18511
edited Jan 29 at 11:13
answered Jan 29 at 11:06
L. F.L. F.
18511
answered Jan 29 at 11:06
L. F.L. F.
18511
answered Jan 29 at 11:06
L. F.L. F.
18511
18511
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%2f3092033%2ffind-a-number-having-minimum-sum-of-distances-between-a-set-of-numbers%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$
The answer is wrong. For example, $100$ is closer to each element than $104$ is.
$endgroup$
– Harnak
Jan 29 at 11:01
2
$begingroup$
math.stackexchange.com/questions/113270/…
$endgroup$
– Matti P.
Jan 29 at 11:04
$begingroup$
@Harnak Sorry but I don't quite understand your statement. $104$ is the total distance $sum_{x in S} |x - n|$ where $n$ is the desired number and $S = {1, 2, 5, 5, 7, 100}$. How do you achieve $100$? See my proof.
$endgroup$
– L. F.
Jan 29 at 11:12
$begingroup$
@L.F., I was just answering to the OP before editing. He stated that the solution was 104, but I thought he referred to the minimizer and not to the distance. So, that's why I provided an example of why 104 couldn't be a minimizer. I think I just misinterpreted what he meant.
$endgroup$
– Harnak
Jan 29 at 11:16
$begingroup$
@Harnak Oh, never mind. Everybody makes mistakes :)
$endgroup$
– L. F.
Jan 29 at 11:17