Re: 2^(n-1)
- From: tommy1729 <tommy1729@xxxxxxxxx>
- Date: Thu, 19 Jul 2007 14:38:12 EDT
In article
<galathaea-454CE2.20141418072007@xxxxxxxxxxxxxxx>,
galathaea <galathaea@xxxxxxxxxx> wrote:
!! In article
!!
<29960810.1184771581209.JavaMail.jakarta@xxxxxxxxxxxxx
forum.org>,
!! 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
er sign combos
now the proof is simply induction with a few lemmas
lemma 1
| +/-a_1 +/-a_2 +/-a_3 +/- ... +/-a_n | = +/-a_1
_1 +/-a_2 +/- ... +/-a_n
for some arrangement of signs on the right given
iven the left
(all signs independent)
lemma 1 is true , BUT this reduces the number of possibilities
for instance
abs ( -1 -4 +2 ) = abs ( +1 +4 -2 )
so bye lemma 1 you have potentially already divided the number of possibilties ( 2^n) bye 2 ; giving 2^(n-1)
but this is far from a proof , and such a lemma is not proven to apply in the proof.
as above and throughout - assume all positive
ve (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
om 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
_n +/-(a_1 +/-a_2 +/- ... +/-a_(n-1))|
which reduces to the case of 2 values
but what if a = b ???
a^2 + b^2 + ...= 1
lemma 2
if sum(a_i^2, i=1...n) = 1 then sum(a_i^2,
2, i=1...(n-1)) <=1
obvious
(they are nonnegative values - ie. a_i^2 >= 0 pulls
ls 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
-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
but although you can prove the case for 3 , it is with another logic ...
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
ch that |+/-a_2 +/-...+/-a_n| <= 1
yes but thats an assumption ...
going from n-1 to n and from n to n+1
is kind a like proving infinite number of primes bye going from one prime to another ...
infinity is the problem ( as often in math )
using lemma 2
but this means that |a_1 - |+/-a_2 +/-...+/-a_n|| <=
1
(because a_1 is positive and the difference cannot
ot 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
tommy1729
.
- Follow-Ups:
- Re: 2^(n-1)
- From: galathaea
- Re: 2^(n-1)
- References:
- Re: 2^(n-1)
- From: galathaea
- Re: 2^(n-1)
- Prev by Date: Re: Ultimate debunking of Cantor's Theory
- Next by Date: Re: Another question-25 years since high school math...
- Previous by thread: Re: 2^(n-1)
- Next by thread: Re: 2^(n-1)
- Index(es):
Relevant Pages
|
