Problem of the Month - Page 7

ccorn · 2011-11-16, 23:44

Quote:

Originally Posted by literka

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 a₁>=a₂>=...>=a_2n>=0
Let { b_i } (1<=i<=2n) be a Bernoulli sequence of independent random variables i.e. they are independent and
P(b_i = 1) = P(b_i = -1) = 0.5
Let a random variable x be defined as
x=abs(b₁*a₁+b₂*a₂+...+b_2n*a_2n)

where abs(y) means absolute value of y.

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

So this is essentially the original problem you posted in this thread, but with the maximum norm instead of the euclidian norm for (a₁,...a_2[I]n[/I]) and with a weaker probability estimate, bounded below by asymptotically $\frac{1}{\sqrt{\pi n}}$ (using Stirling's asymptotic formula). If I have misunderstood that, please correct me.

literka · 2011-11-17, 00:03

Quote:

Originally Posted by ccorn

So this is essentially the original problem you posted in this thread, but with the maximum norm instead of the euclidian norm for (a₁,...a_2[I]n[/I]) and with a weaker probability estimate, bounded below by asymptotically $\frac{1}{\sqrt{\pi n}}$ (using Stirling's asymptotic formula). If I have misunderstood that, please correct me.

I formulated and proved this to have a tool for a main problem. After some time I stopped trying to find a main proof, since it was taking me to much time.
Your geometrical interpretation of a problem was known before. In fact, I saw this problem quoted this geometrical way.

ccorn · 2011-11-29, 01:27

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 (a₁,...,a_n).

The hypercube's (n-1)-dimensional bounding sphere S_[I]n[/I]-1 has radius $\sqrt{n}$ . Let A_[I]n[/I]-1 be the subset of points of S_[I]n[/I]-1 that have distance at most 1 from the central hyperplane with normal vector (a₁,...,a_n). (For n=3, imagine the surface of a striped billiard ball.) The claim of Literka's first problem is that at least half of the hypercube's vertices are in the stripe A_[I]n[/I]-1.

The hypercube has lots of symmetries. In particular, its vertices are spaced evenly across S_[I]n[/I]-1.* Therefore, the ratio f_n of the measures of A_[I]n[/I]-1 and S_[I]n[/I]-1 provides sort of an expected value for the fraction of all hypercube vertices that belong to A_[I]n[/I]-1. If f_n were to drop below 1/2 for some n, this would suggest that there are counterexamples.

As it turns out (left as an exercise for the readers), $f_n = \mathrm{I}(\frac{1}{n};\frac{1}{2},\frac{n-1}{2})$ where I(z;a,b) denotes the Regularized (incomplete) Beta function. One finds that $\lim_{n\to\infty} f_n = \mathrm{erf}(\frac{1}{\sqrt{2}})\approx 0.68$ , the within-1-standard-deviation probability of a normal distribution. This does not prove Literka's first problem, but at least it does not indicate a contradiction.

*: "Spaced evenly" meaning that the Voronoi regions (on S_[I]n[/I]-1) of the vertices are all congruent.

literka · 2012-03-21, 13:45

Let f be a concave function (example of concave function is f(x)= log x ) defined on the interval [0,1].
Let |f|₁ be the first norm of f.
Let |f|₂ be the second norm of f.
First norm means integral of absolute value of f over [0,1].
Second norm means square root of the integral of f² over [0,1].

With the above assumptions show that
sqrt(2)*|f|₁ >= |f|₂

Have a fun.
Hint: solution is very simple.

Dubslow · 2012-03-21, 17:16

You mean f'' < 0 for concave?

literka · 2012-03-21, 17:31

Quote:

Originally Posted by Dubslow

You mean f'' < 0 for concave?

Yes, but only in the case function has a second derivative. (My theorem concerns broader class of functions.) I used a definition as it is in http://en.wikipedia.org/wiki/Concave_function.
Sorry, I forgot to add an assumption f>=0, of course.
I figured out this problem long time ago, when I was a student. That is why I can hardly remember it. Of course without the assumption f>=0 theorem is not true.

literka · 2012-03-23, 18:42

I realized that there is probably an open problem associated with the above theorem. So I decided to write a webpage with a proof of this theorem and with a problem, which I believe is an open problem. See my page www.literka.addr.com/mathcountry/concave.htm.

sascha77 · 2012-03-24, 13:01

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

Thanks for the interesting link !
I love such puzzles. (that are easy to understand, but not so easy to solve)

I also have a problem, that has a relation to mersenne numbers.
But maybe the problem is just "a problem of the minute". I do not know, yet.

1.) Let p be a prime number with p>=3 and p is not a Wieferich prime.
(Wieferich prime p is prime number with property: $2^{p-1} \equiv 1 \;\;(\;mod p^2\;)$

2.) Let k be a natural number with k>=2

Is it possible to chose p and k as descibed in (1) and (2), so that
$2*k*p^{2}+1$ is prime and satisfies the congruence:

$2^p \equiv 1 \;\;(\;mod\; 2*k*p^{2}+1\;)$

science_man_88 · 2012-03-24, 13:56

Quote:

Originally Posted by sascha77

Thanks for the interesting link !
I love such puzzles. (that are easy to understand, but not so easy to solve)

I also have a problem, that has a relation to mersenne numbers.
But maybe the problem is just "a problem of the minute". I do not know, yet.

1.) Let p be a prime number with p>=3 and p is not a Wieferich prime.
(Wieferich prime p is prime number with property: $2^{p-1} \equiv 1 \;\;(\;mod p^2\;)$

2.) Let k be a natural number with k>=2

Is it possible to chose p and k as descibed in (1) and (2), so that
$2*k*p^{2}+1$ is prime and satisfies the congruence:

$2^p \equiv 1 \;\;(\;mod\; 2*k*p^{2}+1\;)$

Code:

forprime(p=1,1000,for(k=2,100*p,if((2^p)<(2*k*p^2+1),print(p","k);break())))

the least p that seems to have any hope of solution for k>=2 is p=11.

sascha77 · 2012-03-24, 14:43

Quote:

Originally Posted by science_man_88

Code:

forprime(p=1,1000,for(k=2,100*p,if((2^p)<(2*k*p^2+1),print(p","k);break())))

the least p that seems to have any hope of solution for k>=2 is p=11.

I see. From what I understand $2^p < 2*k*p^2+1$ is your break-condition.
But you can also set a maximum limit for k direct.
Maybe this speeds up the calculation a little bit ?

$2^{p} \equiv 1 \;(mod \;2*k*p^{2}+1)$

<-> $2*k*p^{2}+1 \;divides \;2^{p}-1$

Therefore: $2^{p}-1 \ge 2*k*p^{2}+1$

$2^{p} \ge 2*k*p^{2}+2$

$2^{p-1}-1 \ge k*p^{2}$

$\frac{2^{p-1}-1}{p^{2}} \ge k$

-> so k must be smaller as $\frac{2^{p-1}-1}{p^{2}}$

science_man_88 · 2012-03-24, 14:48

Quote:

Originally Posted by sascha77

I see. From what I understand $2^p < 2*k*p^2+1$ is your break-condition.
But you can also set a maximum limit for k direct.
Maybe this speeds up the calculation a little bit ?

$2^{p} \equiv 1 \;(mod \;2*k*p^{2}+1)$

<-> $2*k*p^{2}+1 \;divides \;2^{p}-1$

Therefore: $2^{p}-1 \ge 2*k*p^{2}+1$

$2^{p} \ge 2*k*p^{2}+2$

$2^{p-1}-1 \ge k*p^{2}$

$\frac{2^{p-1}-1}{p^{2}} \ge k$

-> so k must be smaller as $\frac{2^{p-1}-1}{p^{2}}$

2*m*p+1 | 2^p-1 so really all your asking is can 2*m*p+1 divide 2 Mersennes but with only one p m=k*p is what you can check for.

2012-03-21, 13:45	#70
literka Mar 2010 C0₁₆ Posts	A problem just for fun. Let f be a concave function (example of concave function is f(x)= log x ) defined on the interval [0,1]. Let \|f\|₁ be the first norm of f. Let \|f\|₂ be the second norm of f. First norm means integral of absolute value of f over [0,1]. Second norm means square root of the integral of f² over [0,1]. With the above assumptions show that sqrt(2)\|f\|₁ >= \|f\|₂ Have a fun. Hint: solution is very simple. Last fiddled with by literka on 2012-03-21 at 13:56*

2012-03-23, 18:42	#73
literka Mar 2010 2⁶·3 Posts	I realized that there is probably an open problem associated with the above theorem. So I decided to write a webpage with a proof of this theorem and with a problem, which I believe is an open problem. See my page www.literka.addr.com/mathcountry/concave.htm. Last fiddled with by literka on 2012-03-23 at 18:51

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

2012-03-21, 17:16	#71
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3×29×83 Posts	You mean f'' < 0 for concave?