|
|
| Author |
Message |
Thomas Mautsch
science forum addict
Joined: 06 May 2005
Posts: 96
|
 Posted: Wed May 24, 2006 9:16 pm Post subject:
Maximum over an n-cycle
|
|
|
Please help me! - I need to maximize the term
S := a(1)a(2) + a(2)a(3) + a(3)a(4) + ... + a(n-1)a(n) + a(n)a(1)
for given values of a(1), ..., a(n).
In what order do I have to arrange these values? |
|
| Back to top |
|
 |
quasi
science forum Guru
Joined: 15 Jul 2005
Posts: 1700
|
| Posted: Wed May 24, 2006 11:39 pm Post subject:
Re: Maximum over an n-cycle
|
|
|
On 24 May 2006 23:06:49 +0100, Thomas Mautsch <mautsch@ethz.ch> wrote:
| Quote: | Please help me! - I need to maximize the term
S := a(1)a(2) + a(2)a(3) + a(3)a(4) + ... + a(n-1)a(n) + a(n)a(1)
for given values of a(1), ..., a(n).
In what order do I have to arrange these values?
|
Assuming a(1), a(2), ..., a(n) are distinct positive reals, you
already know the answer, namely ...
Let j be the largest odd number <= n
and let k be the largest even number <= n.
If b(1), b(2), ..., b(n) are the sorted values, then the maximum for S
can be obtained by:
a(k)=b((k+1)/2) if k is odd
a(k)=b(n-((k-2)/2)) if k is even
For example:
for n=3: b(1), b(3), b(2)
for n=4: b(1), b(4), b(2), b(3)
for n=5: b(1), b(5), b(2), b(4), b(3)
for n=6: b(1), b(6), b(2), b(5), b(3), b(4)
for n=7: b(1), b(7), b(2), b(6), b(3), b(5), b(4)
for n=8: b(1), b( , b(2), b(7), b(3), b(6), b(4), b(5)
etc.
The above answer is easily discovered via simulation. Proving it is
another story.
quasi |
|
| Back to top |
|
|
quasi
science forum Guru
Joined: 15 Jul 2005
Posts: 1700
|
| Posted: Thu May 25, 2006 1:13 am Post subject:
Re: Maximum over an n-cycle
|
|
|
On Wed, 24 May 2006 19:39:22 -0400, quasi <quasi@null.set> wrote:
| Quote: | On 24 May 2006 23:06:49 +0100, Thomas Mautsch <mautsch@ethz.ch> wrote:
Please help me! - I need to maximize the term
S := a(1)a(2) + a(2)a(3) + a(3)a(4) + ... + a(n-1)a(n) + a(n)a(1)
for given values of a(1), ..., a(n).
In what order do I have to arrange these values?
Assuming a(1), a(2), ..., a(n) are distinct positive reals, you
already know the answer, namely ...
|
Clarification: If we establish the ordering for n distinct positive
reals, the same ordering will also work for n nonnegative reals, not
necessarily distinct.
| Quote: | Let j be the largest odd number <= n
and let k be the largest even number <= n.
|
Correction: Ignore the above 2 lines (I thought I had already deleted
them).
| Quote: | If b(1), b(2), ..., b(n) are the sorted values, then the maximum for S
can be obtained by:
a(k)=b((k+1)/2) if k is odd
a(k)=b(n-((k-2)/2)) if k is even
For example:
for n=3: b(1), b(3), b(2)
for n=4: b(1), b(4), b(2), b(3)
for n=5: b(1), b(5), b(2), b(4), b(3)
for n=6: b(1), b(6), b(2), b(5), b(3), b(4)
for n=7: b(1), b(7), b(2), b(6), b(3), b(5), b(4)
for n=8: b(1), b(, b(2), b(7), b(3), b(6), b(4), b(5)
etc.
The above answer is easily discovered via simulation. Proving it is
another story.
quasi
|
quasi |
|
| Back to top |
|
|
quasi
science forum Guru
Joined: 15 Jul 2005
Posts: 1700
|
| Posted: Thu May 25, 2006 3:55 am Post subject:
Re: Maximum over an n-cycle
|
|
|
On Wed, 24 May 2006 21:13:20 -0400, quasi <quasi@null.set> wrote:
| Quote: | On Wed, 24 May 2006 19:39:22 -0400, quasi <quasi@null.set> wrote:
On 24 May 2006 23:06:49 +0100, Thomas Mautsch <mautsch@ethz.ch> wrote:
Please help me! - I need to maximize the term
S := a(1)a(2) + a(2)a(3) + a(3)a(4) + ... + a(n-1)a(n) + a(n)a(1)
for given values of a(1), ..., a(n).
In what order do I have to arrange these values?
Assuming a(1), a(2), ..., a(n) are distinct positive reals, you
already know the answer, namely ...
Clarification: If we establish the ordering for n distinct positive
reals, the same ordering will also work for n nonnegative reals, not
necessarily distinct.
Let j be the largest odd number <= n
and let k be the largest even number <= n.
Correction: Ignore the above 2 lines (I thought I had already deleted
them).
If b(1), b(2), ..., b(n) are the sorted values, then the maximum for S
can be obtained by:
a(k)=b((k+1)/2) if k is odd
a(k)=b(n-((k-2)/2)) if k is even
For example:
for n=3: b(1), b(3), b(2)
for n=4: b(1), b(4), b(2), b(3)
for n=5: b(1), b(5), b(2), b(4), b(3)
for n=6: b(1), b(6), b(2), b(5), b(3), b(4)
for n=7: b(1), b(7), b(2), b(6), b(3), b(5), b(4)
for n=8: b(1), b(, b(2), b(7), b(3), b(6), b(4), b(5)
etc.
The above answer is easily discovered via simulation. Proving it is
another story.
quasi
quasi
|
Ok, I have a proof now.
It uses a couple of cool new tricks -- new for me anyway.
However it's not an instant proof so it will take some work to write
it out clearly. Unfortunately, I probably won't have time until the
first week of June.
Until then, happy hunting -- it's still open.
To Thomas Mautsch:
Assuming (1) no one finds an easy proof, (2) it's not a known result,
and, (3) my proof is correct and interesting, then perhaps we could
write a joint note for publication?
Well, let's see.
First, let the problem stay out for week or so and see if anyone nails
it.
quasi |
|
| Back to top |
|
|
quasi
science forum Guru
Joined: 15 Jul 2005
Posts: 1700
|
| Posted: Thu May 25, 2006 5:11 am Post subject:
Re: Maximum over an n-cycle
|
|
|
On Wed, 24 May 2006 23:55:23 -0400, quasi <quasi@null.set> wrote:
| Quote: | On Wed, 24 May 2006 21:13:20 -0400, quasi <quasi@null.set> wrote:
On Wed, 24 May 2006 19:39:22 -0400, quasi <quasi@null.set> wrote:
On 24 May 2006 23:06:49 +0100, Thomas Mautsch <mautsch@ethz.ch> wrote:
Please help me! - I need to maximize the term
S := a(1)a(2) + a(2)a(3) + a(3)a(4) + ... + a(n-1)a(n) + a(n)a(1)
for given values of a(1), ..., a(n).
In what order do I have to arrange these values?
Assuming a(1), a(2), ..., a(n) are distinct positive reals, you
already know the answer, namely ...
Clarification: If we establish the ordering for n distinct positive
reals, the same ordering will also work for n nonnegative reals, not
necessarily distinct.
Let j be the largest odd number <= n
and let k be the largest even number <= n.
Correction: Ignore the above 2 lines (I thought I had already deleted
them).
If b(1), b(2), ..., b(n) are the sorted values, then the maximum for S
can be obtained by:
|
Correction: I gave the wrong permutation of the b's -- sorry. Delete
all of the following lines from [cut] to [end cut]
................... [cut] .................................
| Quote: | a(k)=b((k+1)/2) if k is odd
a(k)=b(n-((k-2)/2)) if k is even
For example:
for n=3: b(1), b(3), b(2)
for n=4: b(1), b(4), b(2), b(3)
for n=5: b(1), b(5), b(2), b(4), b(3)
for n=6: b(1), b(6), b(2), b(5), b(3), b(4)
for n=7: b(1), b(7), b(2), b(6), b(3), b(5), b(4)
for n=8: b(1), b(, b(2), b(7), b(3), b(6), b(4), b(5)
etc.
............................ [end cut]............................... |
Let j be the largest odd integer <= n
and let k be the largest even integer <= n.
Then a corrected specification for an optimal sequence
a(1), a(2), ..., a(n) is as follows:
b(1), b(3), ... b(j), b(k), b(k-2), ..., b(2)
For example:
for n=3: b(1), b(3), b(2)
for n=4: b(1), b(3), b(4), b(2)
for n=5: b(1), b(3), b(5), b(4), b(2)
for n=6: b(1), b(3), b(5), b(6), b(4), b(2)
for n=7: b(1), b(3), b(5), b(7), b(6), b(4), b(2)
for n=8: b(1), b(3), b(5), b(7), b(, b(6), b(4), b(2)
| Quote: | The above answer is easily discovered via simulation. Proving it is
another story.
quasi
quasi
Ok, I have a proof now.
It uses a couple of cool new tricks -- new for me anyway.
However it's not an instant proof so it will take some work to write
it out clearly. Unfortunately, I probably won't have time until the
first week of June.
Until then, happy hunting -- it's still open.
To Thomas Mautsch:
Assuming (1) no one finds an easy proof, (2) it's not a known result,
and, (3) my proof is correct and interesting, then perhaps we could
write a joint note for publication?
Well, let's see.
First, let the problem stay out for week or so and see if anyone nails
it.
quasi
|
Sorry about the error -- I accidentally reported the inverse
permutation instead of the actual one.
However my proof was immune to the error, hence it survived intact.
quasi |
|
| Back to top |
|
|
quasi
science forum Guru
Joined: 15 Jul 2005
Posts: 1700
|
| Posted: Thu May 25, 2006 6:29 pm Post subject:
Re: Maximum over an n-cycle
|
|
|
On Thu, 25 May 2006 01:11:28 -0400, quasi <quasi@null.set> wrote:
| Quote: | On Wed, 24 May 2006 23:55:23 -0400, quasi <quasi@null.set> wrote:
On Wed, 24 May 2006 21:13:20 -0400, quasi <quasi@null.set> wrote:
On Wed, 24 May 2006 19:39:22 -0400, quasi <quasi@null.set> wrote:
On 24 May 2006 23:06:49 +0100, Thomas Mautsch <mautsch@ethz.ch> wrote:
Please help me! - I need to maximize the term
S := a(1)a(2) + a(2)a(3) + a(3)a(4) + ... + a(n-1)a(n) + a(n)a(1)
for given values of a(1), ..., a(n).
In what order do I have to arrange these values?
Assuming a(1), a(2), ..., a(n) are distinct positive reals, you
already know the answer, namely ...
Clarification: If we establish the ordering for n distinct positive
reals, the same ordering will also work for n nonnegative reals, not
necessarily distinct.
Let j be the largest odd number <= n
and let k be the largest even number <= n.
Correction: Ignore the above 2 lines (I thought I had already deleted
them).
If b(1), b(2), ..., b(n) are the sorted values, then the maximum for S
can be obtained by:
Correction: I gave the wrong permutation of the b's -- sorry. Delete
all of the following lines from [cut] to [end cut]
.................. [cut] .................................
a(k)=b((k+1)/2) if k is odd
a(k)=b(n-((k-2)/2)) if k is even
For example:
for n=3: b(1), b(3), b(2)
for n=4: b(1), b(4), b(2), b(3)
for n=5: b(1), b(5), b(2), b(4), b(3)
for n=6: b(1), b(6), b(2), b(5), b(3), b(4)
for n=7: b(1), b(7), b(2), b(6), b(3), b(5), b(4)
for n=8: b(1), b(, b(2), b(7), b(3), b(6), b(4), b(5)
etc.
........................... [end cut]...............................
Let j be the largest odd integer <= n
and let k be the largest even integer <= n.
Then a corrected specification for an optimal sequence
a(1), a(2), ..., a(n) is as follows:
b(1), b(3), ... b(j), b(k), b(k-2), ..., b(2)
For example:
for n=3: b(1), b(3), b(2)
for n=4: b(1), b(3), b(4), b(2)
for n=5: b(1), b(3), b(5), b(4), b(2)
for n=6: b(1), b(3), b(5), b(6), b(4), b(2)
for n=7: b(1), b(3), b(5), b(7), b(6), b(4), b(2)
for n=8: b(1), b(3), b(5), b(7), b(, b(6), b(4), b(2)
The above answer is easily discovered via simulation. Proving it is
another story.
quasi
quasi
Ok, I have a proof now.
It uses a couple of cool new tricks -- new for me anyway.
However it's not an instant proof so it will take some work to write
it out clearly. Unfortunately, I probably won't have time until the
first week of June.
Until then, happy hunting -- it's still open.
To Thomas Mautsch:
Assuming (1) no one finds an easy proof, (2) it's not a known result,
and, (3) my proof is correct and interesting, then perhaps we could
write a joint note for publication?
Well, let's see.
First, let the problem stay out for week or so and see if anyone nails
it.
quasi
Sorry about the error -- I accidentally reported the inverse
permutation instead of the actual one.
However my proof was immune to the error, hence it survived intact.
|
But it didn't survive a good night's sleep.
(If that proof cared about surviving, it should never have let me go
to sleep).
It really was an inspired proof, but I see now that it simply doesn't
work. Moreover, the flaw is serious -- it can't be fixed.
Oh well.
I should always be highly suspicious of anything I think I've proved
when I'm overly tired.
However, I now have another proof (a morning proof, not a night
proof). The new proof is clearly correct, but unfortunately, it's very
straightforward -- nothing that would qualify as publishable.
It will still take some work to write it out clearly and I'll still
hold off posting it for now. I'll post it late next week unless
someone else posts a similar or better proof before then.
quasi |
|
| Back to top |
|
|
Hugo Pfoertner
science forum addict
Joined: 02 May 2005
Posts: 51
|
| Posted: Thu May 25, 2006 6:39 pm Post subject:
Re: Maximum over an n-cycle
|
|
|
quasi wrote:
| Quote: |
On Wed, 24 May 2006 23:55:23 -0400, quasi <quasi@null.set> wrote:
On Wed, 24 May 2006 21:13:20 -0400, quasi <quasi@null.set> wrote:
On Wed, 24 May 2006 19:39:22 -0400, quasi <quasi@null.set> wrote:
On 24 May 2006 23:06:49 +0100, Thomas Mautsch <mautsch@ethz.ch> wrote:
Please help me! - I need to maximize the term
S := a(1)a(2) + a(2)a(3) + a(3)a(4) + ... + a(n-1)a(n) + a(n)a(1)
for given values of a(1), ..., a(n).
In what order do I have to arrange these values?
Assuming a(1), a(2), ..., a(n) are distinct positive reals, you
already know the answer, namely ...
Clarification: If we establish the ordering for n distinct positive
reals, the same ordering will also work for n nonnegative reals, not
necessarily distinct.
Let j be the largest odd number <= n
and let k be the largest even number <= n.
Correction: Ignore the above 2 lines (I thought I had already deleted
them).
If b(1), b(2), ..., b(n) are the sorted values, then the maximum for S
can be obtained by:
Correction: I gave the wrong permutation of the b's -- sorry. Delete
all of the following lines from [cut] to [end cut]
.................. [cut] .................................
a(k)=b((k+1)/2) if k is odd
a(k)=b(n-((k-2)/2)) if k is even
For example:
for n=3: b(1), b(3), b(2)
for n=4: b(1), b(4), b(2), b(3)
for n=5: b(1), b(5), b(2), b(4), b(3)
for n=6: b(1), b(6), b(2), b(5), b(3), b(4)
for n=7: b(1), b(7), b(2), b(6), b(3), b(5), b(4)
for n=8: b(1), b(, b(2), b(7), b(3), b(6), b(4), b(5)
etc.
........................... [end cut]...............................
Let j be the largest odd integer <= n
and let k be the largest even integer <= n.
Then a corrected specification for an optimal sequence
a(1), a(2), ..., a(n) is as follows:
b(1), b(3), ... b(j), b(k), b(k-2), ..., b(2)
For example:
for n=3: b(1), b(3), b(2)
for n=4: b(1), b(3), b(4), b(2)
for n=5: b(1), b(3), b(5), b(4), b(2)
for n=6: b(1), b(3), b(5), b(6), b(4), b(2)
for n=7: b(1), b(3), b(5), b(7), b(6), b(4), b(2)
for n=8: b(1), b(3), b(5), b(7), b(, b(6), b(4), b(2)
The above answer is easily discovered via simulation. Proving it is
another story.
|
Just for curiosity I wrote a little program that compares the sums for
all possible permutations. For distinct real a(i) each sum occurs 2*n
times.
There are n!/(2*n) possible distinct sum values.
The lexicographically first solutions found by my program of the 2*n
optimal solutions are for a(i) sorted:
Indices
1 2
1 2 3
1 2 4 3
1 2 4 5 3
1 2 4 6 5 3
1 2 4 6 7 5 3
1 2 4 6 8 7 5 3
1 2 4 6 8 9 7 5 3
1 2 4 6 8 10 9 7 5 3
This result is also found if some or all of the a(i) become negative.
Hugo Pfoertner
| Quote: |
quasi
quasi
Ok, I have a proof now.
It uses a couple of cool new tricks -- new for me anyway.
However it's not an instant proof so it will take some work to write
it out clearly. Unfortunately, I probably won't have time until the
first week of June.
Until then, happy hunting -- it's still open.
To Thomas Mautsch:
Assuming (1) no one finds an easy proof, (2) it's not a known result,
and, (3) my proof is correct and interesting, then perhaps we could
write a joint note for publication?
Well, let's see.
First, let the problem stay out for week or so and see if anyone nails
it.
quasi
Sorry about the error -- I accidentally reported the inverse
permutation instead of the actual one.
However my proof was immune to the error, hence it survived intact.
quasi |
|
|
| Back to top |
|
|
quasi
science forum Guru
Joined: 15 Jul 2005
Posts: 1700
|
| Posted: Thu May 25, 2006 8:14 pm Post subject:
Re: Maximum over an n-cycle
|
|
|
On Thu, 25 May 2006 20:39:42 +0200, Hugo Pfoertner
<nothing@abouthugo.de> wrote:
Thomas Mautsch <mautsch@ethz.ch> wrote:
| Quote: |
Please help me! - I need to maximize the term
S := a(1)a(2) + a(2)a(3) + a(3)a(4) + ... + a(n-1)a(n) + a(n)a(1)
for given values of a(1), ..., a(n).
In what order do I have to arrange these values?
|
quasi wrote (edited):
| Quote: | Assuming a(1), a(2), ..., a(n) are distinct positive reals,
Let j be the largest odd integer <= n
and let k be the largest even integer <= n.
Then a specification for an optimal sequence
a(1), a(2), ..., a(n) is as follows:
b(1), b(3), ... b(j), b(k), b(k-2), ..., b(2)
For example:
for n=3: b(1), b(3), b(2)
for n=4: b(1), b(3), b(4), b(2)
for n=5: b(1), b(3), b(5), b(4), b(2)
for n=6: b(1), b(3), b(5), b(6), b(4), b(2)
for n=7: b(1), b(3), b(5), b(7), b(6), b(4), b(2)
for n=8: b(1), b(3), b(5), b(7), b(, b(6), b(4), b(2)
The above answer is easily discovered via simulation.
|
Hugo Pfoertner wrote:
| Quote: | Just for curiosity I wrote a little program that compares the sums for
all possible permutations. For distinct real a(i) each sum occurs 2*n
times.
There are n!/(2*n) possible distinct sum values.
The lexicographically first solutions found by my program of the 2*n
optimal solutions are for a(i) sorted:
Indices
1 2
1 2 3
1 2 4 3
1 2 4 5 3
1 2 4 6 5 3
1 2 4 6 7 5 3
1 2 4 6 8 7 5 3
1 2 4 6 8 9 7 5 3
1 2 4 6 8 10 9 7 5 3
This result is also found if some or all of the a(i) become negative.
|
Well, the permutations you gave above are the same as mine up to a
cyclic permutation, except in reverse order. In other words, the
result is the same.
However, as you point out, there is no need to require positivity, and
in fact, my proof also doesn't require that assumption. Distinctness
is also not necessary but is a convenient assumption in discovery
mode.
Let me try to state the complete result ...
Let n be a positive integer, n >= 3.
Define f:R^n -> R by f(x) = x[1]*x[2] + x[2]*x[3] + .... + x[n]*x[1].
Given a sorted sequence a of n real numbers
a[1] <= a[2] <= ... <= a[n]
and a permutation s in S_n, define
g(s,a) = f(a[s(1)], a[s(2)], ...,a[s(n)])
Then for a fixed sequence a, g(s,a) is maximized when s is the
permutation such that
s(1), s(2), ..., s(n) = 1, 3, 5 ,..., j, k, k-2, ..., 2
where j is the largest odd integer <= n
and k is the largest even integer <= n.
The proof I came up with (the new proof) is tedious but very
straightforward. The logic is simple so I'm not really worried about
flaws, but then again, since I haven't yet written out the proof in
full, maybe I should worry.
quasi |
|
| Back to top |
|
|
Hugo Pfoertner
science forum addict
Joined: 02 May 2005
Posts: 51
|
| Posted: Thu May 25, 2006 9:42 pm Post subject:
Re: Maximum over an n-cycle
|
|
|
Thomas Mautsch wrote:
| Quote: |
Please help me! - I need to maximize the term
S := a(1)a(2) + a(2)a(3) + a(3)a(4) + ... + a(n-1)a(n) + a(n)a(1)
for given values of a(1), ..., a(n).
In what order do I have to arrange these values?
|
A side question that I found interesting was:
Using the optimal arrangement found by quasi (see below in thread), what
is the expected value of the sum S, if the a(i) are drawn randomly from
a uniform distribution on [0,1]? I ran a simulation on my slowest
computer (all others are busy at http://www.recmath.org/contest  and
got the following results:
n expected
sum
2 0.4999 [2*a1*a2]
3 0.7499 [a1*a2+a2*a3+a3*a1], independent of arrangement
4 1.0669
5 1.405
6 1.749
7 2.097
8 2.444
9 2.791
10 3.136
Hugo Pfoertner |
|
| Back to top |
|
|
quasi
science forum Guru
Joined: 15 Jul 2005
Posts: 1700
|
| Posted: Fri May 26, 2006 4:16 am Post subject:
Re: Maximum over an n-cycle
|
|
|
On Thu, 25 May 2006 16:14:40 -0400, quasi <quasi@null.set> wrote:
| Quote: | On Thu, 25 May 2006 20:39:42 +0200, Hugo Pfoertner
nothing@abouthugo.de> wrote:
Thomas Mautsch <mautsch@ethz.ch> wrote:
Please help me! - I need to maximize the term
S := a(1)a(2) + a(2)a(3) + a(3)a(4) + ... + a(n-1)a(n) + a(n)a(1)
for given values of a(1), ..., a(n).
In what order do I have to arrange these values?
quasi wrote (edited):
Assuming a(1), a(2), ..., a(n) are distinct positive reals,
Let j be the largest odd integer <= n
and let k be the largest even integer <= n.
Then a specification for an optimal sequence
a(1), a(2), ..., a(n) is as follows:
b(1), b(3), ... b(j), b(k), b(k-2), ..., b(2)
For example:
for n=3: b(1), b(3), b(2)
for n=4: b(1), b(3), b(4), b(2)
for n=5: b(1), b(3), b(5), b(4), b(2)
for n=6: b(1), b(3), b(5), b(6), b(4), b(2)
for n=7: b(1), b(3), b(5), b(7), b(6), b(4), b(2)
for n=8: b(1), b(3), b(5), b(7), b(, b(6), b(4), b(2)
The above answer is easily discovered via simulation.
Hugo Pfoertner wrote:
Just for curiosity I wrote a little program that compares the sums for
all possible permutations. For distinct real a(i) each sum occurs 2*n
times.
There are n!/(2*n) possible distinct sum values.
The lexicographically first solutions found by my program of the 2*n
optimal solutions are for a(i) sorted:
Indices
1 2
1 2 3
1 2 4 3
1 2 4 5 3
1 2 4 6 5 3
1 2 4 6 7 5 3
1 2 4 6 8 7 5 3
1 2 4 6 8 9 7 5 3
1 2 4 6 8 10 9 7 5 3
This result is also found if some or all of the a(i) become negative.
Well, the permutations you gave above are the same as mine up to a
cyclic permutation, except in reverse order. In other words, the
result is the same.
However, as you point out, there is no need to require positivity, and
in fact, my proof also doesn't require that assumption. Distinctness
is also not necessary but is a convenient assumption in discovery
mode.
Let me try to state the complete result ...
Let n be a positive integer, n >= 3.
Define f:R^n -> R by f(x) = x[1]*x[2] + x[2]*x[3] + .... + x[n]*x[1].
Given a sorted sequence a of n real numbers
a[1] <= a[2] <= ... <= a[n]
and a permutation s in S_n, define
g(s,a) = f(a[s(1)], a[s(2)], ...,a[s(n)])
Then for a fixed sequence a, g(s,a) is maximized when s is the
permutation such that
s(1), s(2), ..., s(n) = 1, 3, 5 ,..., j, k, k-2, ..., 2
where j is the largest odd integer <= n
and k is the largest even integer <= n.
The proof I came up with (the new proof) is tedious but very
straightforward. The logic is simple so I'm not really worried about
flaws, but then again, since I haven't yet written out the proof in
full, maybe I should worry.
quasi
|
I'm having trouble with correct proofs on this problem. The new proof
falls short. What I actually proved is that no _transposition_ of the
permutation order s, specified above, increases the value of f. That
doesn't mean that no _permutation_ of s increases the value of f.
So for now, I withdraw any claim to having a complete proof.
quasi |
|
| Back to top |
|
|
Chip Eastham
science forum Guru
Joined: 01 May 2005
Posts: 412
|
| Posted: Fri May 26, 2006 5:15 am Post subject:
Re: Maximum over an n-cycle
|
|
|
quasi wrote:
| Quote: | On Thu, 25 May 2006 16:14:40 -0400, quasi <quasi@null.set> wrote:
On Thu, 25 May 2006 20:39:42 +0200, Hugo Pfoertner
nothing@abouthugo.de> wrote:
Thomas Mautsch <mautsch@ethz.ch> wrote:
Please help me! - I need to maximize the term
S := a(1)a(2) + a(2)a(3) + a(3)a(4) + ... + a(n-1)a(n) + a(n)a(1)
for given values of a(1), ..., a(n).
In what order do I have to arrange these values?
quasi wrote (edited):
Assuming a(1), a(2), ..., a(n) are distinct positive reals,
Let j be the largest odd integer <= n
and let k be the largest even integer <= n.
Then a specification for an optimal sequence
a(1), a(2), ..., a(n) is as follows:
b(1), b(3), ... b(j), b(k), b(k-2), ..., b(2)
For example:
for n=3: b(1), b(3), b(2)
for n=4: b(1), b(3), b(4), b(2)
for n=5: b(1), b(3), b(5), b(4), b(2)
for n=6: b(1), b(3), b(5), b(6), b(4), b(2)
for n=7: b(1), b(3), b(5), b(7), b(6), b(4), b(2)
for n=8: b(1), b(3), b(5), b(7), b(, b(6), b(4), b(2)
The above answer is easily discovered via simulation.
Hugo Pfoertner wrote:
Just for curiosity I wrote a little program that compares the sums for
all possible permutations. For distinct real a(i) each sum occurs 2*n
times.
There are n!/(2*n) possible distinct sum values.
The lexicographically first solutions found by my program of the 2*n
optimal solutions are for a(i) sorted:
Indices
1 2
1 2 3
1 2 4 3
1 2 4 5 3
1 2 4 6 5 3
1 2 4 6 7 5 3
1 2 4 6 8 7 5 3
1 2 4 6 8 9 7 5 3
1 2 4 6 8 10 9 7 5 3
This result is also found if some or all of the a(i) become negative.
Well, the permutations you gave above are the same as mine up to a
cyclic permutation, except in reverse order. In other words, the
result is the same.
However, as you point out, there is no need to require positivity, and
in fact, my proof also doesn't require that assumption. Distinctness
is also not necessary but is a convenient assumption in discovery
mode.
Let me try to state the complete result ...
Let n be a positive integer, n >= 3.
Define f:R^n -> R by f(x) = x[1]*x[2] + x[2]*x[3] + .... + x[n]*x[1].
Given a sorted sequence a of n real numbers
a[1] <= a[2] <= ... <= a[n]
and a permutation s in S_n, define
g(s,a) = f(a[s(1)], a[s(2)], ...,a[s(n)])
Then for a fixed sequence a, g(s,a) is maximized when s is the
permutation such that
s(1), s(2), ..., s(n) = 1, 3, 5 ,..., j, k, k-2, ..., 2
where j is the largest odd integer <= n
and k is the largest even integer <= n.
The proof I came up with (the new proof) is tedious but very
straightforward. The logic is simple so I'm not really worried about
flaws, but then again, since I haven't yet written out the proof in
full, maybe I should worry.
quasi
I'm having trouble with correct proofs on this problem. The new proof
falls short. What I actually proved is that no _transposition_ of the
permutation order s, specified above, increases the value of f. That
doesn't mean that no _permutation_ of s increases the value of f.
|
You also have that the value of f remains unchanged by cyclic
permutation of the entries, (1,2,3,...,n).
A search on "greedy algorithm" turns up a literature that shows a
successful one has some underlying structure called a "matroid".
The general nature of this is that if an improvement is possible,
it can be attained by a stepwise sequence, which would be your
transpositions if we know how to look at this the right way.
regards, chip |
|
| Back to top |
|
|
Hugo Pfoertner
science forum addict
Joined: 02 May 2005
Posts: 51
|
| Posted: Fri May 26, 2006 8:30 am Post subject:
Re: Maximum over an n-cycle
|
|
|
Hugo Pfoertner schrieb:
| Quote: |
Thomas Mautsch wrote:
Please help me! - I need to maximize the term
S := a(1)a(2) + a(2)a(3) + a(3)a(4) + ... + a(n-1)a(n) + a(n)a(1)
for given values of a(1), ..., a(n).
In what order do I have to arrange these values?
A side question that I found interesting was:
Using the optimal arrangement found by quasi (see below in thread), what
is the expected value of the sum S, if the a(i) are drawn randomly from
a uniform distribution on [0,1]? I ran a simulation on my slowest
computer (all others are busy at http://www.recmath.org/contest and
got the following results:
n expected
sum
2 0.4999 [2*a1*a2]
3 0.7499 [a1*a2+a2*a3+a3*a1], independent of arrangement
4 1.0669
5 1.405
6 1.749
7 2.097
8 2.444
9 2.791
10 3.136
Hugo Pfoertner
|
Inserting a(i)=i into the conjectured optimal arrangement leads to
http://www.research.att.com/~njas/sequences/A110610
and also to a solution for the problem of finding the minimum of this
special sum:
http://www.research.att.com/~njas/sequences/A110611
Hugo |
|
| Back to top |
|
|
Hugo Pfoertner
science forum addict
Joined: 02 May 2005
Posts: 51
|
| Posted: Fri May 26, 2006 9:22 am Post subject:
Re: Maximum over an n-cycle
|
|
|
Hugo Pfoertner schrieb:
| Quote: |
Hugo Pfoertner schrieb:
Thomas Mautsch wrote:
Please help me! - I need to maximize the term
S := a(1)a(2) + a(2)a(3) + a(3)a(4) + ... + a(n-1)a(n) + a(n)a(1)
for given values of a(1), ..., a(n).
In what order do I have to arrange these values?
A side question that I found interesting was:
Using the optimal arrangement found by quasi (see below in thread), what
is the expected value of the sum S, if the a(i) are drawn randomly from
a uniform distribution on [0,1]? I ran a simulation on my slowest
computer (all others are busy at http://www.recmath.org/contest and
got the following results:
n expected
sum
2 0.4999 [2*a1*a2]
3 0.7499 [a1*a2+a2*a3+a3*a1], independent of arrangement
4 1.0669
5 1.405
6 1.749
7 2.097
8 2.444
9 2.791
10 3.136
Hugo Pfoertner
Inserting a(i)=i into the conjectured optimal arrangement leads to
http://www.research.att.com/~njas/sequences/A110610
and also to a solution for the problem of finding the minimum of this
special sum:
http://www.research.att.com/~njas/sequences/A110611
Hugo
|
Examples for arrangements minimizing the given sum are for a(i) sorted:
n indices
2 1 2
3 1 2 3
4 1 3 2 4
5 1 4 3 2 5
6 1 5 3 4 2 6
7 1 6 3 4 5 2 7
8 1 7 3 5 4 6 2 8
9 1 8 3 6 5 4 7 2 9
10 1 9 3 7 5 6 4 8 2 10
11 1 10 3 8 5 6 7 4 9 2 11
12 1 11 3 9 5 7 6 8 4 10 2 12
Hugo Pfoertner |
|
| Back to top |
|
|
Hugo Pfoertner
science forum addict
Joined: 02 May 2005
Posts: 51
|
| Posted: Sat May 27, 2006 3:50 pm Post subject:
Re: Maximum over an n-cycle
|
|
|
Hugo Pfoertner wrote:
| Quote: |
Hugo Pfoertner wrote:
Hugo Pfoertner wrote:
Thomas Mautsch wrote:
Please help me! - I need to maximize the term
S := a(1)a(2) + a(2)a(3) + a(3)a(4) + ... + a(n-1)a(n) + a(n)a(1)
for given values of a(1), ..., a(n).
In what order do I have to arrange these values?
A side question that I found interesting was:
Using the optimal arrangement found by quasi (see below in thread), what
is the expected value of the sum S, if the a(i) are drawn randomly from
a uniform distribution on [0,1]? I ran a simulation on my slowest
computer (all others are busy at http://www.recmath.org/contest and
got the following results:
n expected
sum
2 0.4999 [2*a1*a2]
3 0.7499 [a1*a2+a2*a3+a3*a1], independent of arrangement
4 1.0669
5 1.405
6 1.749
7 2.097
8 2.444
9 2.791
10 3.136
Hugo Pfoertner
Inserting a(i)=i into the conjectured optimal arrangement leads to
http://www.research.att.com/~njas/sequences/A110610
and also to a solution for the problem of finding the minimum of this
special sum:
http://www.research.att.com/~njas/sequences/A110611
Hugo
Examples for arrangements minimizing the given sum are for a(i) sorted:
n indices
2 1 2
3 1 2 3
4 1 3 2 4
5 1 4 3 2 5
6 1 5 3 4 2 6
7 1 6 3 4 5 2 7
8 1 7 3 5 4 6 2 8
9 1 8 3 6 5 4 7 2 9
10 1 9 3 7 5 6 4 8 2 10
11 1 10 3 8 5 6 7 4 9 2 11
12 1 11 3 9 5 7 6 8 4 10 2 12
Hugo Pfoertner
|
For a(i) drawn from a uniform distribution on [0,1] and optimal
arrangements I get the following expected sum values:
Maximizing arrangements:
S_n = (n^3+3*n^2-7*n+12) / (3*(n+1)*(n+2)) for n>=2
Minimizing arrangements:
S_n = (2*n^3+9*n^2+16*n-12) / (12*(n+1)*(n+2)) for n even
S_n = (2*n^3+9*n^2+16*n-3) / (12*(n+1)*(n+2)) for n odd, n>=3
Hugo Pfoertner |
|
| Back to top |
|
|
quasi
science forum Guru
Joined: 15 Jul 2005
Posts: 1700
|
| Posted: Sat May 27, 2006 6:29 pm Post subject:
Re: Maximum over an n-cycle
|
|
|
On Sat, 27 May 2006 17:50:30 +0200, Hugo Pfoertner
<nothing@abouthugo.de> wrote:
| Quote: | Hugo Pfoertner wrote:
Hugo Pfoertner wrote:
Hugo Pfoertner wrote:
Thomas Mautsch wrote:
Please help me! - I need to maximize the term
S := a(1)a(2) + a(2)a(3) + a(3)a(4) + ... + a(n-1)a(n) + a(n)a(1)
for given values of a(1), ..., a(n).
In what order do I have to arrange these values?
A side question that I found interesting was:
Using the optimal arrangement found by quasi (see below in thread), what
is the expected value of the sum S, if the a(i) are drawn randomly from
a uniform distribution on [0,1]? I ran a simulation on my slowest
computer (all others are busy at http://www.recmath.org/contest and
got the following results:
n expected
sum
2 0.4999 [2*a1*a2]
3 0.7499 [a1*a2+a2*a3+a3*a1], independent of arrangement
4 1.0669
5 1.405
6 1.749
7 2.097
8 2.444
9 2.791
10 3.136
Hugo Pfoertner
Inserting a(i)=i into the conjectured optimal arrangement leads to
http://www.research.att.com/~njas/sequences/A110610
and also to a solution for the problem of finding the minimum of this
special sum:
http://www.research.att.com/~njas/sequences/A110611
Hugo
Examples for arrangements minimizing the given sum are for a(i) sorted:
n indices
2 1 2
3 1 2 3
4 1 3 2 4
5 1 4 3 2 5
6 1 5 3 4 2 6
7 1 6 3 4 5 2 7
8 1 7 3 5 4 6 2 8
9 1 8 3 6 5 4 7 2 9
10 1 9 3 7 5 6 4 8 2 10
11 1 10 3 8 5 6 7 4 9 2 11
12 1 11 3 9 5 7 6 8 4 10 2 12
Hugo Pfoertner
For a(i) drawn from a uniform distribution on [0,1] and optimal
arrangements I get the following expected sum values:
Maximizing arrangements:
S_n = (n^3+3*n^2-7*n+12) / (3*(n+1)*(n+2)) for n>=2
Minimizing arrangements:
S_n = (2*n^3+9*n^2+16*n-12) / (12*(n+1)*(n+2)) for n even
S_n = (2*n^3+9*n^2+16*n-3) / (12*(n+1)*(n+2)) for n odd, n>=3
Hugo Pfoertner
|
Interesting.
I'll try to verify these when I get a chance.
quasi |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Fri Jan 09, 2009 12:41 am | All times are GMT
|
|
Guitar Lessons | Mortgages | Rapidshare and Megaupload | Loans | Credit Cards
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
