Re: 2^(n-1)

In article <galathaea-454CE2.20141418072007@xxxxxxxxxxxxxxx>,
galathaea <galathaea@xxxxxxxxxx> wrote:

!! In article
!! <29960810.1184771581209.JavaMail.jakarta@xxxxxxxxxxxxxxxxxxxxxx>,
!! tommy1729 <tommy1729@xxxxxxxxx> wrote:
!!
!! !! Let {a1,a2,..a_n} be a sequence of real numbers such that
!! !!
!! !! sum i=1 .. inf (a_i)^2 = 1
!! !!
!! !! Let us consider 2^n numbers of the form +-a1+-a2-+...+-an (We take all
!! !! possible of sums of elements with plus or minus signs). Show that among them
!! !! there are at least
!! !! 2^(n-1) numbers such that
!! !! abs(+-a1+-a2+-a3...+-an) <= 1
!! !! (Having absolute value smaller or equal 1).
!! !!
!! !!
!! !! Notice: Numbers corresponding to different sequences of signs we regard as
!! !! distinct, although they may have equal values. In other words: we count also
!! !! multiplicity of occuring numbers.
!! !!
!! !! prove it
!!
!! do you mean a_(i1), a_(i2), ..., a_(in)
!! where the i are a collection of n mutually distinct elements of N?
!!
!! or must they be consecutive?

i'm sorry i misread
it was that "inf" you put in the sum that threw me off

this is actually pretty straightforward

the points (+/-a_1, +/-a_2, ..., +/-a_n)

order the coordinates a_1 > a_2 > a_3 > ... > a_n
in the "first" n-drant
(ie. all positive)

by the symmetry of the sphere
any solution we find here will apply to all other sign combos

now the proof is simply induction with a few lemmas

lemma 1
| +/-a_1 +/-a_2 +/-a_3 +/- ... +/-a_n | = +/-a_1 +/-a_2 +/- ... +/-a_n
for some arrangement of signs on the right given the left
(all signs independent)

as above and throughout - assume all positive (which does not restrict)

in case 2

if a>b, |a - b| = a - b
else = b - a

|a + b| is obvious and all others are formed from negation

now if a_1, a_2, ..., a_(n-1) have this property
then |a_n +/-a_1 +/-a_2 +/- ... +/-a_(n-1)| = |a_n +/-(a_1 +/-a_2 +/- ... +/-a_(n-1))|
which reduces to the case of 2 values


lemma 2
if sum(a_i^2, i=1...n) = 1 then sum(a_i^2, i=1...(n-1)) <=1

obvious
(they are nonnegative values - ie. a_i^2 >= 0 pulls out to the stated inequality)

so
proving for the 2-point case

if a>=b>=0, a^2 + b^2 = 1 then a + b > 1
then (a + b) > 1 > (a - b) > 0 > (b - a) > -1 > (-a - b)

this follows from (a+b)^2 = a^2 + b^2 + 2ab = 1 + 2ab >= 1

so case 2, 2 of the cases have |+/-a +/-b| <= 1

then assume that your question is true for (n-1)
given a_1>=a_2>=...>=a_n>=0
then by assumption there exists 2^(n-2) signs such that |+/-a_2 +/-...+/-a_n| <= 1
using lemma 2

but this means that |a_1 - |+/-a_2 +/-...+/-a_n|| <= 1
(because a_1 is positive and the difference cannot be less than -1)

also |-a_1 + |+/-a_2 +/-...+/-a_n|| <= 1 by symmetry of the signs

and these correspond to formulae of the correct form by lemma 1
so we have just produce 2^(n-2) + 2^(n-2) = 2^(n-1) such signed formulae

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
galathaea: prankster, fablist, magician, liar
.