Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

Simplest most elegant proof?

Revision en2, by Alex7, 2016-02-29 05:25:43

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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Alex7 2016-02-29 05:25:43 5 Tiny change: '\nShow us your how beaut' -> '\nShow us how beaut'
en1 English Alex7 2016-02-29 04:31:38 765 Initial revision (published)