[Explanation of the math confusion] To solve the problem, think locally. At each possible number, you can move up or down, and see whether this increases or decreases the total cost. For example if you’re at 3 (which has cost 3) if you move up 1 to 4, you get cost of 6, and if you move down to 2 you get cost of 2.

One way you can think of the cost of 4 relative to 3, is that when you move up to 4 you move away 1 step from each of the three data points - so you increase the cost of three. You can think of moving from 3 to 2 as moving toward 2 data-points and away from 1, which is a net benefit.

Overall, the goal is to find a state where movement in either direction causes you to move away from more points than you move toward. And that will always be the central data point, which has $n$ data points on either side, and yet as it moves toward $n$ of them it moves away from $n + 1$ (it moves off the data point is was standing on). And yes, if you have an even number of datapoints, then every point between the two central datapoints is a median.

Thanks to Buck Shlegeris for teaching me this.

shardo

shardo

shardo

shardo

shardo

shardo