mersenneforum.org Problem of the Month
 Register FAQ Search Today's Posts Mark Forums Read

2011-11-16, 00:22   #45
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23·937 Posts

Quote:
 Originally Posted by literka Try this problem, but only if you want to waste your time, since it is a very difficult problem: Let { ai }, where i=1,2...n, be a sequence of n real numbers. Assume that a1^2 +a2^2+...+an^2 is equal 1.
I take a_1 = 1, all the others are 0.

Quote:
 Take all possible sums of the form abs(b1*a1 + b2*a2 +...+ bn*an) where bi is sign (is equal 1 or -1) and abs(x) means absolute value of x. This way we construct 2^n real numbers. Show that at least half of these numbers is less or equal 1.
This sum reduces to abs(1 * 1 + 0 + 0 + ......)
or abs(1 * -1 + 0 + 0 + .....)

ALL of them are 1. Perhaps there is a missing condition?

2011-11-16, 00:41   #46
ccorn

Apr 2010

5×31 Posts

Quote:
 Originally Posted by R.D. Silverman I take a_1 = 1, all the others are 0. [...] ALL of them are 1. Perhaps there is a missing condition?
I understand the (ai) to be a given finite tuple of reals which I cannot restrict to my liking.

2011-11-16, 00:44   #47
literka

Mar 2010

26·3 Posts

Quote:
 Originally Posted by R.D. Silverman I take a_1 = 1, all the others are 0. This sum reduces to abs(1 * 1 + 0 + 0 + ......) or abs(1 * -1 + 0 + 0 + .....) ALL of them are 1. Perhaps there is a missing condition?

Ok. Since I am afraid I was misunderstood I reformulate last sentence of the problem:
Out of 2n constructed numbers take these, which are less than 1 and these which are equal 1 (hence if a number is equal 1, we take it). Show that this way we take at least
2^(n-1)
numbers (at least half of all numbers).

2011-11-16, 00:53   #48
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

165108 Posts

Quote:
 Originally Posted by ccorn I understand the (ai) to be a given finite tuple of reals which I cannot restrict to my liking.
OK. But my argument still shows that there exists at least 1 tuple
for which the result is not true. Indeed, even if we restrict a_i to
be non-zero there exists other tuples for which the result is false.

e.g. take N = 4, a_i, i=1...4 = 1/2, 1/2, 1/2, 1/2

The second sum is 0 six times, 2 twice, and 1 eight times.

The problem needs to say something about the permissible set
of tuples for a_i. There are some tuples for which the result is not true...

2011-11-16, 01:00   #49
ccorn

Apr 2010

5·31 Posts

Quote:
 Originally Posted by R.D. Silverman e.g. take N = 4, a_i, i=1...4 = 1/2, 1/2, 1/2, 1/2 The second sum is 0 six times, 2 twice, and 1 eight times.
Which means the second sum is not greater than 1 precisely 14 out of 16 times, which fulfills the claim.

2011-11-16, 01:20   #50
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

165108 Posts

Quote:
 Originally Posted by literka In your example all numbers are less or equal 1. You did not read may text carefully. Read it once again, please. Ok. Since I am afraid I was misunderstood I reformulate last sentence of the problem: Out of 2n constructed numbers take these, which are less than 1 and these which are equal 1 (hence if a number is equal 1, we take it). Show that this way we take at least 2^(n-1) numbers (at least half of all numbers).
Ah! Yes. Got it. Interesting problem. I misinterpreted it.

I may look at it as a feasible set problem in integer programming. i.e.

Maximize 1 subject to:

Given a set of points in E^n: A = {a_1, .... a_n} all lying on the
unit sphere, [this is constraint 1]

and given all possible constraints
Sum(a_i b_j) <= 1 for b_j = 1 or -1 and i = 1, .....n

the problem is to find a lower bound on the size of the feasible set. Show
that it is at least 2^{n-1}. One can sometimes get such results by
looking at the problem DUAL. The Complimentary slackness thm. can
sometimes be applied to the dual. I will think about it.

2011-11-16, 01:24   #51
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D4816 Posts

Quote:
 Originally Posted by ccorn Which means the second sum is not greater than 1 precisely 14 out of 16 times, which fulfills the claim.
Yes. I had the inequality reversed somehow..... A red cow flew by the window.

2011-11-16, 01:32   #52
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23·937 Posts

Quote:
 Originally Posted by R.D. Silverman Ah! Yes. Got it. Interesting problem. I misinterpreted it. I may look at it as a feasible set problem in integer programming. i.e. Maximize 1 subject to: Given a set of points in E^n: A = {a_1, .... a_n} all lying on the unit sphere, [this is constraint 1] and given all possible constraints Sum(a_i b_j) <= 1 for b_j = 1 or -1 and i = 1, .....n the problem is to find a lower bound on the size of the feasible set. Show that it is at least 2^{n-1}. One can sometimes get such results by looking at the problem DUAL. The Complimentary slackness thm. can sometimes be applied to the dual. I will think about it.
After some deeper reflection, I seriously doubt this will work.....One has to
view the feasible set in a peculiar way for this to work. {i.e. the feasible set would consists of the points {a_1 b_j1, a_2 b_j2, ......} as the b_j's run through all possible combinations......

2011-11-16, 01:39   #53
literka

Mar 2010

19210 Posts

Quote:
 Originally Posted by R.D. Silverman A the problem is to find a lower bound on the size of the feasible set. Show that it is at least 2^{n-1}.
You've got it. It is an old paper of Burkholder, who proved that there is a constant c>0 such that we take at least c*2n numbers. There is more on my internet page www.literka.addr.com/mathcountry/problem.htm

 2011-11-16, 12:21 #54 chris2be8     Sep 2009 5·13·37 Posts You can find a monthly problem at http://domino.research.ibm.com/Comm/...ges/index.html Most take more effort to solve than I have free time though. Chris K
2011-11-16, 14:06   #55
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

165108 Posts

Quote:
 Originally Posted by literka Try this problem, but only if you want to waste your time, since it is a very difficult problem: Let { ai }, where i=1,2...n, be a sequence of n real numbers. Assume that a1^2 +a2^2+...+an^2 is equal 1. Take all possible sums of the form abs(b1*a1 + b2*a2 +...+ bn*an) where bi is sign (is equal 1 or -1) and abs(x) means absolute value of x. This way we construct 2^n real numbers. Show that at least half of these numbers is less or equal 1.
This problem fascinates me. It should be within my grasp, yet the solution
eludes me. I don't want to read the references (yet). That would be cheating.

It reminds me of some of the elementary combinatorial/additive
problems that were routinely posed by Uncle Paul. (Erdos). Many of
them still elude the entire community.

 Similar Threads Thread Thread Starter Forum Replies Last Post Aillas PrimeNet 48 2012-02-15 19:17 cheesehead Soap Box 0 2009-01-24 07:59 em99010pepe No Prime Left Behind 5 2008-02-24 14:37 ltd Prime Sierpinski Project 22 2006-03-02 17:55 JuanTutors Lounge 6 2005-02-28 22:59

All times are UTC. The time now is 19:55.

Sat Nov 26 19:55:06 UTC 2022 up 100 days, 17:23, 1 user, load averages: 1.06, 1.01, 1.03