Solving a third Erdösproblem (?)

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.

About these ads

This entry was posted on November 2, 2010 at 05:22 and is filed under Problem Solving. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Solving a third Erdösproblem (?)”

Erdösproblem, part III « Woett's Blog Says:
November 4, 2010 at 01:17 | Reply
[...] So far I found more, what I like to call, NP-primitive counterexamples to the question asked here. Why NP? Because it’s easy to show (by the reasoning from the previous post) that [...]

Leave a Reply Cancel reply

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Twitter account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

Woett's Blog