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.


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

  1. Erdösproblem, part III « Woett's Blog Says:

    […] 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

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

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

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

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

Facebook photo

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


Connecting to %s

%d bloggers like this: