mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-11-16, 14:45   #56
KyleAskine
 
KyleAskine's Avatar
 
Oct 2011
Maryland

2×5×29 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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.
KyleAskine is offline   Reply With Quote
Old 2011-11-16, 15:29   #57
literka
 
literka's Avatar
 
Mar 2010

26×3 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
literka is offline   Reply With Quote
Old 2011-11-16, 17:24   #58
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts
Default

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

5·31 Posts
Default

Quote:
Originally Posted by literka View Post
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.
ccorn is offline   Reply With Quote
Old 2011-11-16, 20:04   #60
ccorn
 
ccorn's Avatar
 
Apr 2010

5·31 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
ccorn is offline   Reply With Quote
Old 2011-11-16, 20:31   #61
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
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???
R.D. Silverman is offline   Reply With Quote
Old 2011-11-16, 21:12   #62
ccorn
 
ccorn's Avatar
 
Apr 2010

5·31 Posts
Default

(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
ccorn is offline   Reply With Quote
Old 2011-11-16, 21:44   #63
literka
 
literka's Avatar
 
Mar 2010

26·3 Posts
Default 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)
literka is offline   Reply With Quote
Old 2011-11-16, 22:16   #64
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts
Default

Quote:
Originally Posted by ccorn View Post
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
science_man_88 is offline   Reply With Quote
Old 2011-11-16, 22:22   #65
ccorn
 
ccorn's Avatar
 
Apr 2010

5×31 Posts
Default

Quote:
Originally Posted by literka View Post
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: Ah, wait. I overlooked the greater sign in the formula.

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
ccorn is offline   Reply With Quote
Old 2011-11-16, 22:59   #66
literka
 
literka's Avatar
 
Mar 2010

110000002 Posts
Default

Quote:
Originally Posted by ccorn View Post
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
literka 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 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

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.

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