I didn't know about this little theorem until yesterday. Here's an example to introduce it.
Take the integers and split them into two lists of 5 numbers any way you like. Arrange the numbers in the first group in ascending order and those in the second list in descending order. For example we might have
|
1 |
3 |
4 |
5 |
10 |
|
9 |
8 |
7 |
6 |
2 |
Now work out the differences between each corresponding pair of numbers and add up the differences
|
1 |
3 |
4 |
5 |
10 |
|
9 |
8 |
7 |
6 |
2 |
|
8 |
5 |
3 |
1 |
8 |
This is not a coincidence and can be replaced by for any any . Split the numbers into any two groups of numbers, arrange the first group in ascending order, the second in descending order, calcule the differences between the corresponding numbers in the two groups, and add up the differences. The total will always be . At the end of this post I have given a Python program that runs random trials for a given and checks the sum is indeed as claimed.
Why should this be? Well let's take the example above and for each pair of numbers see which is the maximum and which the minimum. The motivation for this is that for any pair of numbers the difference between them is the maximum of the pair minus the minimum. Here's the table with rows for the maxima and minima.
|
ascending |
1 |
3 |
4 |
5 |
10 |
|
descending |
9 |
8 |
7 |
6 |
2 |
|
maximum |
9 |
8 |
7 |
6 |
10 |
|
minimum |
1 |
3 |
4 |
5 |
2 |
Look at the numbers in the maximum row. Do you notice anything about them? What about the ones in the minimum row?
Do you see? The maxima are just the numbers , just not in order. We can arrange them in order, and then rewrite them like this (you'll see why we're doing this in a moment)
, which when added come to .
Similarly the minima are just the remaining numbers , just not in order, and when added they come to .
Almost there. Recall that each difference is a maximum minus a minimum, so using for summation we can write
differences = maxima - minima, which comes to
as expected.
Now this is not a proof but it points way to one. If we could show that whatever the value of it is always the case that the maxima are the integers in some order and the minima are the integers in some order then a general proof would more or less fall out.
It took me a long time to understand why this is indeed true but I think I've grasped it now, but I need a bit of time to write it up clearly, so I'm going to leave that until tomorrow now.
Footnote: According to Wikipedia this problem was presented by Vyacheslav Proizvolov asin the 1985 All-Union Soviet Student Olympiads, so it is comparatively modern, as these things go.