Woett's Blog

The Angel Problem

March 20, 2011

Go to http://library.msri.org/books/Book29/files/conway.pdf. Read the proof of Theorem 3.1. Am I being ridiculous if I believe it to be incorrect?

Posted in General, Problem Solving | Leave a Comment »

I’m done.

February 1, 2011

From its start back in May 2010, this blog has been one big failure. It took me over half a year, but I finally realised that I

– Can’t write
– Can’t present math in a clear fashion
– Can’t be bothered to write posts on a regular basis

At least these things are all true when the language I use is English. So, if Chewbacca lives on Endor, I must quit!

Probably, this implies that I will start a new blog sometime in the future. That could be in a few months, but it could also be in a few decades, I dont know. When the time is ripe, I will let you know. That’s a promise. You might ask why I would want to start a new blog, ever, given the above three reasons why this one failed. Well, because I can say that I learned a lot from this blog, so I can confidentially assert that my writing will be better next time.

Catch you on the flipside.

Posted in General, Motivation | Leave a Comment »

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 😀

Posted in General, Motivation, There's more than math | Leave a Comment »

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!

Posted in Motivation, There's more than math | 4 Comments »

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

Posted in Problem Solving | 1 Comment »

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.

Posted in Problem Solving | Leave a Comment »

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.

Posted in Problem Solving | 1 Comment »

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$

Posted in Problem Solving | Leave a Comment »

Generalizing generalities

October 31, 2010

Theorem.
Let $L_n$ be the least common multiple of $\{1,2,..,n\}$ and $X_n = L_n \displaystyle \sum_{i=1}^n \dfrac{r_i}{i s_i}$ with $r_i, s_i \in Z$ for all $i$ , $r_{i+m} = r_i$ for some $m$ and $s_{i+m'} = s_i$ for some $m'$ . Then $\gcd(X_n, L_n) > 1$ for infinitely many $n$ .

Proof.
It is clear that it is necessary that the numerator of $X_n$ does not equal $1$ infinitely often. So let’s start with that. Assume that the numerator of $X_{n-1}$ does equal $1$ for some large $n$ , where $n$ is not a prime power. Then: $|X_n| + |X_{n-1}| \ge |X_n - X_{n-1}| = \left|\dfrac{L_n r_n}{n s_n}\right| > \dfrac{L_n}{n^2} > 2$ . And since $|X_{n-1}| \le 1$ , we have $|X_n| > 1$ , which is never a unit fraction. Let $a$ be an integer for which $a \ge \max(m, m', \displaystyle \max_i (|s_i|))$ and $p$ be a prime larger than $a$ such that $p$ divides $X_a$ . Note that if such a prime doesn’t exist for any $a$ , we would have that all the prime divisors of $X_a$ (which, as we saw, exist for infinitely many $a$ ), are smaller than or equal to $a$ . But a prime divisor of $X_a$ which is smaller than or equal to $a$ also divides $L_a$ . And this would immediately imply our theorem. So we may assume the existence of a prime $p$ $> a \ge$ $\max(m, m', \displaystyle \max_i(|s_i|))$ dividing $X_a$ . Now, let $k$ be any (positive) multiple of lcm $(\varphi(m), \varphi(m'))$ and set $n = ap^k$ ;

$X_n = L_n \displaystyle \sum_{i=1}^n \dfrac{r_i}{i s_i}$
$\equiv L_n \displaystyle \sum_{i=1}^a \dfrac{r_{ip^k}}{ip^k s_{ip^k}}$ $\pmod{p}$
$\equiv \dfrac{L_n}{p^k} \displaystyle \sum_{i=1}^a \dfrac{r_i}{i s_i}$ $\pmod{p}$
$\equiv 0$ $\pmod{p}$

Posted in Problem Solving | Leave a Comment »

Another generalization

October 31, 2010

Let $L_n$ be the least common multiple of $\{1,2,..,n\}$ and $X_n = L_n \displaystyle \sum_{i=1}^n \dfrac{b_i}{i}$ , where $b_{i+m}$ $= b_i \in \aleph$ for all $i$ and some $m$ . Then $\gcd(X_n, L_n) > 1$ necessarily happens infinitely often.

Proof.
Assume a $p > a$ exists that divides $X_a = L_a \displaystyle \sum_{i=1}^a \dfrac{b_i}{i}$ for some $a \ge m$ . Note that we may assume so, because if such a $p$ doesn’t exist, we’re immediately done since every primedivisor of $X_a$ must then be smaller than or equal to $a$ and thus also be a divisor of $L_a$ . Let $k$ be any multiple of $\varphi(m)$ and $n = ap^k$ . We then have:

$X_n = L_n \displaystyle \sum_{i=1}^n \dfrac{b_i}{i} \equiv L_n \displaystyle \sum_{i=1}^a \dfrac{b_{ip^k}}{ip^k} \equiv \dfrac{L_n}{p^k} \displaystyle \sum_{i=1}^a \dfrac{b_i}{i} \equiv 0 \pmod{p}$

Posted in Problem Solving | Leave a Comment »

Woett's Blog

The Angel Problem

I’m done.

Random update

PGOM LD AD LD CD

Erdösproblem 3, part III

Erdösproblem 3, part II

Solving a third Erdösproblem (?)

Weighed cointossing

Generalizing generalities

Another generalization

Recent Posts

Categories

Blogroll

Archives