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 yesterday
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 yesterday
Abdenaceur LichihebAbdenaceur Lichiheb
1436
$endgroup$
$begingroup$
The answer is wrong. For example, $100$ is closer to each element than $104$ is.
$endgroup$
– Harnak
yesterday
2
$begingroup$
math.stackexchange.com/questions/113270/…
$endgroup$
– Matti P.
yesterday
$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.
yesterday
$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
yesterday
$begingroup$
@Harnak Oh, never mind. Everybody makes mistakes :)
$endgroup$
– L. F.
yesterday
|
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 yesterday
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 yesterday
Abdenaceur LichihebAbdenaceur Lichiheb
1436
asked yesterday
Abdenaceur LichihebAbdenaceur Lichiheb
1436
edited 18 hours ago
Abdenaceur Lichiheb
asked yesterday
Abdenaceur LichihebAbdenaceur Lichiheb
1436
asked yesterday
Abdenaceur LichihebAbdenaceur Lichiheb
1436
asked yesterday
Abdenaceur LichihebAbdenaceur Lichiheb
1436
1436
$begingroup$
The answer is wrong. For example, $100$ is closer to each element than $104$ is.
$endgroup$
– Harnak
yesterday
2
$begingroup$
math.stackexchange.com/questions/113270/…
$endgroup$
– Matti P.
yesterday
$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.
yesterday
$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
yesterday
$begingroup$
@Harnak Oh, never mind. Everybody makes mistakes :)
$endgroup$
– L. F.
yesterday
|
show 1 more comment
$begingroup$
The answer is wrong. For example, $100$ is closer to each element than $104$ is.
$endgroup$
– Harnak
yesterday
2
$begingroup$
math.stackexchange.com/questions/113270/…
$endgroup$
– Matti P.
yesterday
$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.
yesterday
$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
yesterday
$begingroup$
@Harnak Oh, never mind. Everybody makes mistakes :)
$endgroup$
– L. F.
yesterday
$begingroup$
The answer is wrong. For example, $100$ is closer to each element than $104$ is.
$endgroup$
– Harnak
yesterday
$begingroup$
The answer is wrong. For example, $100$ is closer to each element than $104$ is.
$endgroup$
– Harnak
yesterday
2
2
$begingroup$
math.stackexchange.com/questions/113270/…
$endgroup$
– Matti P.
yesterday
$begingroup$
math.stackexchange.com/questions/113270/…
$endgroup$
– Matti P.
yesterday
$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.
yesterday
$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.
yesterday
$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
yesterday
$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
yesterday
$begingroup$
@Harnak Oh, never mind. Everybody makes mistakes :)
$endgroup$
– L. F.
yesterday
$begingroup$
@Harnak Oh, never mind. Everybody makes mistakes :)
$endgroup$
– L. F.
yesterday
|
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 yesterday
HarnakHarnak
1,082412
$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
yesterday
$begingroup$
You're right. However, that was not my intent. I'll edit this. Thanks for the suggestion :)
$endgroup$
– Harnak
yesterday
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 yesterday
L. F.L. F.
1737
$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 yesterday
HarnakHarnak
1,082412
$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
yesterday
$begingroup$
You're right. However, that was not my intent. I'll edit this. Thanks for the suggestion :)
$endgroup$
– Harnak
yesterday
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 yesterday
HarnakHarnak
1,082412
$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
yesterday
$begingroup$
You're right. However, that was not my intent. I'll edit this. Thanks for the suggestion :)
$endgroup$
– Harnak
yesterday
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 yesterday
HarnakHarnak
1,082412
$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 yesterday
HarnakHarnak
1,082412
edited yesterday
answered yesterday
HarnakHarnak
1,082412
answered yesterday
HarnakHarnak
1,082412
answered yesterday
HarnakHarnak
1,082412
1,082412
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
yesterday
$begingroup$
You're right. However, that was not my intent. I'll edit this. Thanks for the suggestion :)
$endgroup$
– Harnak
yesterday
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
yesterday
$begingroup$
You're right. However, that was not my intent. I'll edit this. Thanks for the suggestion :)
$endgroup$
– Harnak
yesterday
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
yesterday
$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
yesterday
$begingroup$
You're right. However, that was not my intent. I'll edit this. Thanks for the suggestion :)
$endgroup$
– Harnak
yesterday
$begingroup$
You're right. However, that was not my intent. I'll edit this. Thanks for the suggestion :)
$endgroup$
– Harnak
yesterday
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 yesterday
L. F.L. F.
1737
$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 yesterday
L. F.L. F.
1737
$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 yesterday
L. F.L. F.
1737
$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 yesterday
L. F.L. F.
1737
edited yesterday
answered yesterday
L. F.L. F.
1737
answered yesterday
L. F.L. F.
1737
answered yesterday
L. F.L. F.
1737
1737
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
yesterday
2
$begingroup$
math.stackexchange.com/questions/113270/…
$endgroup$
– Matti P.
yesterday
$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.
yesterday
$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
yesterday
$begingroup$
@Harnak Oh, never mind. Everybody makes mistakes :)
$endgroup$
– L. F.
yesterday