mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Other Mathematical Topics

Reply
 
Thread Tools
Old 2011-11-16, 00:22   #45
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23·937 Posts
Default

Quote:
Originally Posted by literka View Post
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?
R.D. Silverman is offline   Reply With Quote
Old 2011-11-16, 00:41   #46
ccorn
 
ccorn's Avatar
 
Apr 2010

5×31 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
ccorn is offline   Reply With Quote
Old 2011-11-16, 00:44   #47
literka
 
literka's Avatar
 
Mar 2010

26·3 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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?

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).
literka is offline   Reply With Quote
Old 2011-11-16, 00:53   #48
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

165108 Posts
Default

Quote:
Originally Posted by ccorn View Post
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...
R.D. Silverman is offline   Reply With Quote
Old 2011-11-16, 01:00   #49
ccorn
 
ccorn's Avatar
 
Apr 2010

5·31 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
ccorn is offline   Reply With Quote
Old 2011-11-16, 01:20   #50
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

165108 Posts
Default

Quote:
Originally Posted by literka View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-11-16, 01:24   #51
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

1D4816 Posts
Default

Quote:
Originally Posted by ccorn View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-11-16, 01:32   #52
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

23·937 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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......
R.D. Silverman is offline   Reply With Quote
Old 2011-11-16, 01:39   #53
literka
 
literka's Avatar
 
Mar 2010

19210 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
literka is offline   Reply With Quote
Old 2011-11-16, 12:21   #54
chris2be8
 
chris2be8's Avatar
 
Sep 2009

5·13·37 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2011-11-16, 14:06   #55
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

165108 Posts
Default

Quote:
Originally Posted by literka View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
The Month of Double Check effort Aillas PrimeNet 48 2012-02-15 19:17
Whiner-of-the-Month cheesehead Soap Box 0 2009-01-24 07:59
One month of NPLB em99010pepe No Prime Left Behind 5 2008-02-24 14:37
Best month ever for PSPs prp effort ltd Prime Sierpinski Project 22 2006-03-02 17:55
New Month's Resolution 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔