Archive for November, 2010

Random update

November 23, 2010

The reason for the fact that is has been more than 2 weeks since my last update is simple; contrary to popular belief, I have been busy. With a few things actually. I have been a bit busy studying (who would’ve thought). I have been busy writing my first article (thank you very much), which will be finished end of the week, hopefully. I have been busy playing guitar (obviously, I suck). And, last but not least, I have been juggling like there was no tomorrow (again, I suck). When I’ll improve, I might put some videos of me juggling here. That ought to be fun ūüôā My personal bests are, as of this moment:

3 balls: 12 minutes (close to 2500 catches)
4 balls: 57 seconds (over 200 catches)
5 balls: 15 catches
6 balls: 6 catches
7+ balls: err, no

I’ll update you on all of these things as soon as I’ve got some news.

EDIT 25 november: Woohoo! I flashed 6 balls ūüėÄ
EDIT 30 november: I updated a few personal bests. As of tomorrow I won’t do that anymore to be able to track my progress. But right now I’m too happy with my clean run of 15 ūüėÄ

Advertisements

PGOM LD AD LD CD

November 5, 2010

A variant on a well-known poem;

The title (basically) said it and I again will say
I’m in my prime; today it’s my 21st¬†birthday!

Erd√∂sproblem 3, part III

November 4, 2010

So far I found about 10 more, what I like to call, NP-primitive counterexamples to the question¬†asked here. When do I call a counterexample¬†NP-primitive? When it’s easy to show (by the reasoning from the previous post) that¬†it’s indeed a¬†counterexample and if¬†no (strict) subset of¬†it is a NP-primitive¬†counterexample.¬†And given a NP-primitive counterexample, it’s easy to construct other easy to check counterexamples. The question now is of course: are there infinitely many NP-primitive counterexamples? Conceivably, this is not too hard. The¬†ones I found so far:

\{2,3,4,5,6,8,9,10,12,15,16\}
\{2,3,4,5,6,7,8,9,15,16,24\}
\{2,3,4,5,6,7,8,9,10,15,230\}
\{2,3,4,5,6,8,9,10,12,15,18,180\}
\{2,3,4,5,6,7,8,9,14,15,31,2474\}
\{2,3,4,5,6,7,8,9,11,15,75,8153\}
\{2,3,4,5,6,7,8,9,12,13,93,44155\}
\{2,3,4,5,6,7,8,10,12,14,60,105\}
\{2,3,4,5,6,7,8,10,12,15,42,210,420\}
\{3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,21,72,453\}
\{3,4,5,6,7,8,9,10,11,12,14,15,16,18,20,21,30,154,315\}
\{3,4,5,6,7,8,9,10,11,12,13,14,15,18,20,24,30,840,450450\}

And you can even make more by e.g. replacing 60 in the fifth to last set with 120, 140 and 840. A more general, and to me more sensible, conjecture of Erdös, Graham and Spencer is the following:

If \displaystyle \sum_{i=1}^k \dfrac{1}{x_i} < N - \dfrac{1}{m}, then the x_i can be split into N subsets
A_1, A_2, .., A_n such that for all j with 1 \le j \le N we have: \displaystyle \sum_{a_i \in A_j} \dfrac{1}{a_i} \le 1, as long as m \le 30.

This is known for m = \dfrac{7}{2} (see here) and \{2,3,3,5,5,5,5\} shows that m = 30 is tight. Very probably this conjecture is cute enough to deserve a closer look at sometime.

EDIT: A counterexample to this last conjecture was found by Song Guo (Electronic J. of Combinatorics 15 (2008), #N43). You can find it online, if you’re interested. That paper also refers to other articles about these conjectures. The main question of finding the maximal m is still open, in any case

Erd√∂sproblem 3, part II

November 3, 2010

I checked my dictionary, but apparently there is no english word for the dutch word ‘tangconstructie’. Anyway, remember how I, rhetorically, asked ‘how else could it be?’ yesterday? Well,¬†I am more than delighted to say that I am able¬†to give a counterexample to the metaconjecture that every proof of a counterexample to the question of Erd√∂s and Graham I talked about in the previous post, works¬†via a case-by-case-argument.

Consider the set X = \{2,3,4,5,6,8,9,10,12,15,16\} and let lcm\{S\} be the least common multiple of all members of S, for a set S of positive integers. Then \displaystyle \sum_{x_i \in X} \dfrac{1}{x_i} = 2 - \dfrac{1}{lcm\{X\}}. Now, assume we have a partition of X in two sets A and B with \displaystyle \sum_{a_i \in A} \dfrac{1}{a_i} < 1 and \displaystyle \sum_{b_i \in B} \dfrac{1}{b_i} < 1. Then in particular we have:

2 - \dfrac{1}{lcm\{X\}}
= \displaystyle \sum_{x_i \in X} \dfrac{1}{x_i}
= \displaystyle \sum_{a_i \in A} \dfrac{1}{a_i} + \displaystyle \sum_{b_i \in B} \dfrac{1}{b_i}
\le 1 - \dfrac{1}{lcm\{A\}} + 1 - \dfrac{1}{lcm\{B\}}
\le 2 - \dfrac{2}{lcm\{X\}}

And boom goes the dynamite.

Solving a third Erd√∂sproblem (?)

November 2, 2010

In their monograph on problems in combinatorial number theory, Erdös and Graham ask the following question:

Is it true that if 1 < x_1 < x_2 < .. < x_k and \displaystyle \sum_{i=1}^k \dfrac{1}{x_i} < 2 then there exist \epsilon_i = 0 or 1 so that \displaystyle \sum_{i=1}^k \dfrac{\epsilon_i}{x_i} < 1 and \displaystyle \sum_{i=1}^k \dfrac{1-\epsilon_i}{x_i} < 1?

And I can’t find a way to do this where the x_i‘s are \{2,3,4,5,6,8,9,11,12,13,16\}. And, if this indeed is a counterexample, I’m bold enough to conjecture that it’s the easiest. \{2,3,4,5,6,7,8,11,12,13,33\} could very well be a candidate too, but I haven’t checked that one thoroughly.

Edit: I now proved that the first one of these is indeed a counterexample, but of course, the proof is¬†a case-by-case-argument (how else could it be?), so I won’t put it here, because¬†of uglyness.

Weighed cointossing

November 2, 2010

Assume S = \{s_1, s_2, .. \}¬†is a set with 1 \le¬†s_1¬†\le s_2 \le .. ,¬†such that \displaystyle \sum \dfrac{1}{s_i} diverges.¬† Let a_i = \pm 1, each with probability \dfrac{1}{2}. What can we say about \displaystyle \sum_{i=1}^n \dfrac{a_i}{s_i} when n goes to infinity? Must there, for example,¬†be infinitely many sign changes with probability 1? It can’t be hard to show this for bounded s_i, but what about S = \aleph¬†for example? I honestly have no clue whatsoever.

EDIT 22 Februari 2011
I can show that there is a positive probability that \left|\displaystyle \sum_{i=1}^n \dfrac{a_i}{s_i}\right| > c for any c, for n large enough; Let k = k(c) be the smallest integer such that \displaystyle \sum_{i=1}^k \dfrac{1}{s_i} > c (note that this k exists since the sum of \dfrac{1}{s_i} is assumed to go to infinity).
Then either the probability that \displaystyle \sum_{i=k+1}^n \dfrac{a_i}{s_i} \ge 0 is at least \dfrac{1}{2} or the probability that \displaystyle \sum_{i=k+1}^n \dfrac{a_i}{s_i} \le 0 is at least \dfrac{1}{2} (*). Assume the first case (second case goes analogous), then we have: P\left(\displaystyle \sum_{i=1}^n \dfrac{a_i}{s_i} > c\right) \ge P\left(\displaystyle \sum_{i=k+1}^n \dfrac{a_i}{s_i} \ge 0\right) \displaystyle \prod_{j=1}^k P(a_j = 1) \ge \dfrac{1}{2}\dfrac{1}{2^k} = \dfrac{1}{2^{k+1}} > 0

(*) It is fun to note that both are the case, independent of S. This can be used to show that P\left(\left|\displaystyle \sum_{i=1}^n \dfrac{a_i}{s_i}\right| > c\right) \ge \dfrac{1}{2^k} for all n \ge k