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

Is it true that if and then there exist or so that and ?

And I can’t find a way to do this where the ‘s are . And, if this indeed is a counterexample, I’m bold enough to conjecture that it’s the easiest. 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.

### Like this:

Like Loading...

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.

November 4, 2010 at 01:17 |

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