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

2011-11-16, 14:45   #56

Oct 2011
Maryland

2×5×29 Posts

Quote:
 Originally Posted by chris2be8 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
That is actually a pretty cool problem. Sort of like a 12 man round robin, but not because the referee rounds can't play each other.

2011-11-16, 15:29   #57
literka

Mar 2010

26×3 Posts

Quote:
 Originally Posted by R.D. Silverman That would be cheating.

Believe me, it wouldn't be cheating. This is an unsolved problem. If you think that it may help you to read previous results, then do not hesitate. By now, few skillful mathematicians were trying to prove it and partial results were published.

There is a danger in this and probably you will experience it. Trying to prove it is time consuming. Also, it is very easy to make a mistake. If at some point you think that you found a simple proof, try rather to find error. This is what my experience says to me.

Later I will write in this thread another problem, easier one. This time it will not be open problem (I proved it) and I believe it may be helpful to find a final proof.

Last fiddled with by literka on 2011-11-16 at 15:30

2011-11-16, 17:24   #58
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by R.D. Silverman 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.
well I'm not mathematician but my logic says that solving for an average of the set of reals might help solve the latter part:

let ${a_i}^2=c_i$ then $1=\sum_{i=1}^{i=n} c_i$

so the average of $c_i$ is $\frac{1}{n}$ so the average for $a_i$ is $sqrt{\frac{1}{n}}$ although I feel confident this can help I don't quite know how.

2011-11-16, 17:46   #59
ccorn

Apr 2010

5·31 Posts

Quote:
 Originally Posted by literka 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.
Geometrically, this means that at least half of all the vertices of an n-dimensional hypercube (all coordinates +/-1) are not farther than unit distance from an arbitrary (n-1)-dimensional hyperplane containing the origin. The hyperplane's normal vector is (a1,...,an). This should be provable.

2011-11-16, 20:04   #60
ccorn

Apr 2010

5·31 Posts

Quote:
 Originally Posted by science_man_88 so the average of $c_i$ is $\frac{1}{n}$ so the average for $a_i$ is $sqrt{\frac{1}{n}}$ although I feel confident this can help I don't quite know how.
The RMS of $(a_1,\ldots,a_n)$ is $sqrt{\frac{1}{n}}$, therefore the average of $(|a_1|, \ldots, |a_n|)$ is not greater than that.

2011-11-16, 20:31   #61
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D4816 Posts

Quote:
 Originally Posted by ccorn Geometrically, this means that at least half of all the vertices of an n-dimensional hypercube (all coordinates +/-1) are not farther than unit distance from an arbitrary (n-1)-dimensional hyperplane containing the origin. The hyperplane's normal vector is (a1,...,an). This should be provable.
Yes, which is why I suggested looking at the dual of the feasible set
formulation. I have not been able to push through an argument, however.

I also looked at an inductive approach. It is easy to prove for dimension 1
or 2. But showing that it is true for n+1 based on its being true for n
got rapidly intractable for me. I assume that others have tried induction
and failed???

 2011-11-16, 21:12 #62 ccorn     Apr 2010 5·31 Posts (Referring to the nomenclature of post #59) The claim clearly holds in the case that the hyperplane cuts through 2[I]n[/I]-1 unconnected edges of the hypercube. This case is met if e.g. the hyperplane's normal vector (a1,...,an) has a "dominating" element so close to +/-1 (thereby suppressing all other elements in magnitude) that the hyperplane cuts all 2[I]n[/I]-1 parallel edges of the hypercube running along the corresponding coordinate direction (corresponding to the index of the dominating element). Edit: In fact, cutting through a prolonged edge (overshooting each vertex by one unit length) instead of cutting through the edge itself would suffice. This widens the applicability of the all-parallel-edges case. Working on that. Last fiddled with by ccorn on 2011-11-16 at 21:47
 2011-11-16, 21:44 #63 literka     Mar 2010 26·3 Posts Simpler problem (proved) Let C(n,k) denote binomial coefficient C(n,k)=n!/[k! * (n-k)!]. Operator "<=" means "less or equal". Let a1>=a2>=...>=a2n. Let { bi } (1<=i<=2n) be a Bernoulli sequence of independent random variables i.e. they are independent and P(bi=1)=P(bi=-1)=0.5 Let a random variable x be defined as the sum x=b1*a1+b2*a2+...+b2n*a2n Then P(x<=a1)>=C(2n,n)/(2^2n)
2011-11-16, 22:16   #64
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by ccorn The RMS of $(a_1,\ldots,a_n)$ is $sqrt{\frac{1}{n}}$, therefore the average of $(|a_1|, \ldots, |a_n|)$ is not greater than that.
$sqrt{\frac{1}{n}}=sqrt{\frac{1}{n}}$ and so it isn't greater I do see how a flaw occurs but here was my logic so nobody else will try using it:

sum of (n elements)^2 =1 so the average of (elements)^2 = 1/n each element is the square root so I get $sqrt{\frac{1}{n}}$

Last fiddled with by science_man_88 on 2011-11-16 at 22:16

2011-11-16, 22:22   #65
ccorn

Apr 2010

5×31 Posts

Quote:
 Originally Posted by literka Let C(n,k) denote binomial coefficient C(n,k)=n!/[k! * (n-k)!]. Operator "<=" means "less or equal". Let a1>=a2>=...>=a2n. Let { bi } (1<=i<=2n) be a Bernoulli sequence of independent random variables i.e. they are independent and P(bi=1)=P(bi=-1)=0.5 Let a random variable x be defined as the sum x=b1*a1+b2*a2+...+b2n*a2n Then P(x<=a1)>=C(2n,n)/(2^2n)
Counterexample: a1 > 0, a2 = ... = a2[I]n[/I] = 0. Then P(x <= a1) should be 1, but your formula is different.

Edit: No abs() on x? No restriction to a2[I]n[/I] > 0?

Last fiddled with by ccorn on 2011-11-16 at 22:41

2011-11-16, 22:59   #66
literka

Mar 2010

110000002 Posts

Quote:
 Originally Posted by ccorn Counterexample: a1 > 0, a2 = ... = a2[I]n[/I] = 0. Then P(x <= a1) should be 1, but your formula is different. Edit: Ah, wait. I overlooked the greater sign in the formula. Edit: No abs() on x? No restriction to a2[I]n[/I] > 0?

You were right, there is an error in the text.
I should be :

Let C(n,k) denote binomial coefficient C(n,k)=n!/[k! * (n-k)!].
Operator "<=" means "less or equal".
Let a1>=a2>=...>=a2n>=0
Let { bi } (1<=i<=2n) be a Bernoulli sequence of independent random variables i.e. they are independent and
P(bi = 1) = P(bi = -1) = 0.5
Let a random variable x be defined as
x=abs(b1*a1+b2*a2+...+b2n*a2n)

where abs(y) means absolute value of y.

Then
P(x<=a1)>=C(2n,n)/(2^2n)

Last fiddled with by literka on 2011-11-16 at 23:09

 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 06:03.

Fri Dec 9 06:03:21 UTC 2022 up 113 days, 3:31, 0 users, load averages: 0.76, 0.98, 1.02