Archive for the ‘Problem Solving’ Category

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?

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

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}

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}

G-g-generalize

October 29, 2010

I never meant for it to happen. It violates all intentions of this blog to generalize a theorem. So I’d like to blame Ernie Croot for the suggestion;

Let B be any (unordered) set of integers. 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 \in B for all i. Then \gcd(X_n, L_n) > 1 necessarily happens infinitely often in exactly 2 cases: there either exists an odd prime p for which b_i \equiv b_j \pmod{p} for all b_i, b_j \in B, or all the b_i are even. And it’s not even necessary to start the sum at i = 1.

Another random conjecture

October 28, 2010

In spirit of yesterdays post, could the following be true, wild as it is?;

\displaystyle \sum_{i=1}^n \dfrac{1}{i} \equiv 0 \pmod{p} implies n \le n_p

If true, n_p = O(p^p) can’t be far from the truth. Do we have n_p = O(p^k)? I very much doubt it.. n_3 = 22, n_5 = 24 and n_7 \ge 16735 \approx 7^5 in any case.

EDIT: By just googling “harmonic number 16735” I found some articles from around 1990, that are devoted to exactly this conjecture and it seems like it’s true (it’s proven for all p < 550 with the possible exception of 83, 127 and 397), but hard. The only remaining conjecture from the previous post seems to hold up too. Anyway, they use p-adic methods, which I am (still) not that familiar with, so I’m definitely going to search for some literature about it.

Three random conjectures

October 28, 2010

Please refute at least one of the following:

\displaystyle \sum_{i=1}^n \dfrac{1}{i} \equiv 0 \pmod{p^2} implies n < p^2

\displaystyle \sum_{i=1}^n \dfrac{1}{i} \equiv 0 \pmod{p^3} implies n = p - 1

\displaystyle \sum_{i=1}^n \dfrac{1}{i} \equiv 0 \pmod{p^4} never happens

EDIT. p = 11, n = 10583 is quite a cute counterexample to the first 2 of these.