Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Alex7's blog

By Alex7, history, 4 years ago, In English,

Here is a classic problem where you have a set N points on a straight line and you want to choose some point (from that set) such that the sum of the distances between that point and every other point is minimized.

A famous problem adopting this simple idea is IOI 2011 Ricehub.

It makes sense that the optimal point is the median of our N points. I usually prove it either by visualization or studying the how many times we end up summing the line segments between each two consecutive points.

Are there any simpler more elegant proofs ?

Show us how beautiful your minds are :D!

  • Vote: I like it
  • +53
  • Vote: I do not like it

4 years ago, # |
  Vote: I like it +102 Vote: I do not like it

Suppose you're at a point in the line. If you're moving towards the median, you're moving closer to at least half of the points, and moving away from at most half of the points, so moving closer to the median can only decrease the total sum of distances to all points. It follows that the minimum sum has to be at the median.