Prev: Telescopic-Eclipse Technique Chapt10, Fiberglass Experiment #103; ATOM TOTALITY
Next: Calculating Minimum Metal Consumption
From: hanrahan398 on 24 May 2010 13:50
On May 24, 5:54 pm, Ray Vickson <RGVick...(a)shaw.ca> wrote:
> On May 24, 3:49 am, hanrahan...(a)yahoo.co.uk wrote:

> > On May 23, 3:52 am, Ray Vickson <RGVick...(a)shaw.ca> wrote:
>
> > > On May 22, 6:14 am, hanrahan...(a)yahoo.co.uk wrote:
> > > > Does someone know of an online proof of the rearrangement inequality
> > > > for more than 2 sequences?

> > > What do you mean? The usual rearrangement results refer to inner
> > > products of the form sum x_i * y_s(i) for two equi-length sequences
> > > {x_j} and {y_j} and for s(.) a permutation. Do you mean that you have
> > > "triple" products of the form sum x_i*y_s(i)*z_t(i)? Are you claiming
> > > that there are results about this, but you don't know their proofs?
>
> > Yes. One result in particular:
>
> > for any no. of ascending sequences of positive reals {a_1,...,a_n},
> > {b_1,...,b_n}, {c_1,...,c_n}, ..., {z_1,...,z_n}, and permutations
> > {B_1,...,B_n}, {C_1,...,C_n}, ..., {Z_1,...,Z_n}, a theorem states
> > that
>
> > (a_1)(b_1)...(z_1) + ... + (a_n)(b_n)...(z_n)
>
> > >= (a_1)(B_1)...(Z_1) + ... + (a_n)(B_n)...(Z_n)
>
> > or in shorter notation:
>
> > sum (a_i * b_i * ... *z_i) >= sum (a_i * b_s(i) * ... * z_s(i) )
>
> If the same permutation s(.) is applied to all sequences {b},{c},...,
> {z}, isn't b_s(i) * ... * z_s(i) just a re-arrangement of b_i * ...
> z_i = P_i; in other words, can't we just apply the two-sequence result
> to the increasing sequences a_1, a_2, ..., a_n and P_1, P_2, ... ,
> P_n? (The P_j are increasing because all b_j, c_j, ..., z_j are > 0
> and they are increasing in j.

This is correct, but the theorem is supposed to hold regardless of
whether the permutations applied to {b},{c},...{z} are the same or
not.

Michael

From: Don Coppersmith on 24 May 2010 11:59
> On May 23, 3:52 am, Ray Vickson <RGVick...(a)shaw.ca>
> wrote:
> > On May 22, 6:14 am, hanrahan...(a)yahoo.co.uk wrote:
>
> > > Does someone know of an online proof of the
> rearrangement inequality
> > > for more than 2 sequences?
>
> > What do you mean? The usual rearrangement results
> refer to inner
> > products of the form sum x_i * y_s(i) for two
> equi-length sequences
> > {x_j} and {y_j} and for s(.) a permutation. Do you
> mean that you have
> > "triple" products of the form sum
> x_i*y_s(i)*z_t(i)? Are you claiming
> > that there are results about this, but you don't
> know their proofs?
>
> Yes. One result in particular:
>
> for any no. of ascending sequences of positive reals
> {a_1,...,a_n},
> {b_1,...,b_n}, {c_1,...,c_n}, ..., {z_1,...,z_n}, and
> permutations
> {B_1,...,B_n}, {C_1,...,C_n}, ..., {Z_1,...,Z_n}, a
> theorem states
> that
>
> (a_1)(b_1)...(z_1) + ... + (a_n)(b_n)...(z_n)
>
> >= (a_1)(B_1)...(Z_1) + ... + (a_n)(B_n)...(Z_n)
>
> or in shorter notation:
>
> sum (a_i * b_i * ... *z_i) >= sum (a_i * b_s(i) * ...
> * z_s(i) )
>
> This is used by Arthur Engel on p.170 of his book
> 'Problem Solving
> Strategies', but he doesn't give a proof.
>
> Michael

Without the restriction that all the elements be positive,
a counterexample would have been:
a = (0,1), b=(-1,0), c=(-1,0).

With the restriction in place, use an inductive proof.
Suppose all elements are nonnegative,
and suppose a given set of permutations leads to
the largest possible sum.
Suppose the largest summand is *not* the product of the
largest individual elements, but rather it involves
a_i which is smaller than a_j.
Swap the positions of a_i and a_j, and argue that
the sum strictly increases.
On the other hand, if the largest summand was already
the product of the largest individual elements,
then strip that off and repeat.

Don Coppersmith
First  |  Prev  | 
Pages: 1 2
Prev: Telescopic-Eclipse Technique Chapt10, Fiberglass Experiment #103; ATOM TOTALITY
Next: Calculating Minimum Metal Consumption