Friday, 9 August 2013

How can I prove this problem about ordering of differences of numbers?

How can I prove this problem about ordering of differences of numbers?

This is the problem: Given several real numbers (arbitrary amount and
values) : $A_1,A_2 \ldots A_n$
Find the combination which yields the maximum value for the following
formula:
$y = |A_x -A_y| + |A_y-A_z| \ldots$
Where all the numbers have to be used but no number can be used more than
once.
My solution: $|A_x -A_y|$ means the difference between these two numbers.
We want thus maximize the differences between the number in a certain
order.
To do so, I'd first sort the list from bigger to smaller.
Then I will pick number alternatively from the start and the end of the
list. Thus ensuring the differences are biggest possible. In other words I
will start with the largest number, then I will choose the best possible
decision at that moment which is the smaller. Then I am in the smaller,
the best possible decision is the second-to-largest, etc. You can think of
the solution recursively also.
This is an eager process(as opposed to say Chess where you can not always
choose the best play at a given moment on time). But I am sure yields the
best result.
Now, this is the question:
How can I prove this is true? How can make a mathematical proof of this?
Or thinking more in general, is there any work on what kind of problems
are suited for a eager algorithms? For instance, this process has a
maximum, and it is of limited execution. This makes me think I can prove
these kind of problems can be solved with 'best decision at each step'
kind of algorthims. Anyone can through a light on this?

No comments:

Post a Comment