## [Computational Complexity] An ill define question inspired by that HS question

Expand Messages
• RECALL the problem from my last post: Each point in the plane is colored either red or green. Let ABC be a fixed triangle. Prove that there is a triangle DEF
Message 1 of 1 , Dec 10, 2007
• 0 Attachment
RECALL the problem from my last post:
Each point in the plane is colored either red or green. Let ABC be a fixed triangle. Prove that there is a triangle DEF in the plane such that DEF is similar to ABC and the vertices of DEF all have the same color.
The answers to all of the problems on the exam are posted See here for the webpage for the competition. The problem above is problem 5.

One of the key observations needed to solve the problem is the following theorem:
If the reals are 2-colored then there exists 3 points that are the same color that are equally spaced.

Before you can say `VDW theorem!' or `Roth's Theorem!' or `Szemeredi's theorem for k=3 !' realize that this was an exam for High School Students who would not know such thing. And indeed there is an easier proof that a HS student could (and in fact some did) use:
Let a,b both be RED. If (a+b)/2 is RED then a,(a+b)/2,b works. If 2b-a is RED then a,b,2b-a works. If 2a-b is RED then 2a-b,a,b works. IF none of these hold then 2a-b,(a+b)/2,2b-a are all BLUE and that works.
By VDW the following, which we denote VDWR, is true by just restricting the coloring to N:
VDWR: For any k,c, for any c-coloring of R (yes R) there exists a monochromatic arithmetic progression of length k.

This raises the following ill-defined question:
Is there a proof of VDWR that is EASIER than using VDW's theorem. Or at least different- perhaps using properties of the reals (the case of c=2, k=3 used that the midpoint of two reals is always a real).

--
Posted By GASARCH to Computational Complexity at 12/10/2007 12:53:00 PM
Your message has been successfully submitted and would be delivered to recipients shortly.