Monday, December 10, 2007

An ill define question inspired by that HS question

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).

8 comments:

  1. The qoriginal question seems ill-defined to me.

    Wouldn't it depend on the particular distribution of colored points on the plane?

    ReplyDelete
  2. Hmm...I'm thinking about an induction proof (on k) but it seems unlikely to work (without a VDW-like argument, that is. The VDW argument, on the other hand, _does_ seem like it'd be simplified a bit because you can put APs in between the terms of a "big AP".)

    Silly question: Does the original argument for (3,2) extend to (3,c)? If not, then "standard" Ramsey-type arguments seem unavoidable...

    ReplyDelete
  3. The simple argument given in the post for (3,2) extends to any arithmetic progression (not just reals) as well - in particular works for natural numbers as well. So the simple argument is not special for reals.

    ReplyDelete
  4. My answer to Bill's question would be 'probably not', for the reason that VDWR implies VDW in the following, relatively simple, way.

    Let's prove VDW(k, c) using VDWR(k, c). For each real number r, assign a variable x_r, taking values in {1, 2, ... c}.

    The statement that R can be c-colored to avoid monochromatic k-APs (which we're assuming is false) is equivalent to the satisfiability of an (uncountable) collection of formulae {f_i} (one for each potential k-AP), each involving a finite number of varibles from {x_r}.

    Since the collection is unsatisfiable, by the Compactness Theorem for propositional logic (easily adapted to the c-valued setting), some finite subset of clauses are unsatisfiable. These involve the variables of finitely many r, say R' = {r_1, ... r_t}.
    Thus any c-coloring to R' leads to a k-AP.


    Now let's argue that we can WLOG replace R' with a collection of *rational* numbers. Create variables V = v_1, ... v_t; for each subset of R' that's in arithmetic progression, we can stipulate a corresponding AP in V by linear equalities and inequalities with rational coefficients.

    We know this linear program is satisfiable over R, namely, by V := R'. Since the ineqs are rational, a general result tells us that there's also a rational solution. So we can find a finite rational set Q' having all of the k-APs corresponding to those of R' (and maybe even more, but that's OK since it just makes APs harder to avoid).

    Clearing denominators in Q', we obtain a finite subset N' of N, for which all c-colorings must induce a monochromatic k-AP.

    ReplyDelete
  5. This xkcd comic seems very relevant to this post:

    ReplyDelete
  6. I don't mean any offense to the person who wrote up the answer for the exam, but I think they did it in the least helpful way for people who took the test to understand how they might figure it out themselves.

    The two main insights that you need to solve the problem are that you can create a structure of adjacent similar triangles to force the coloring, and secondly in such a structure if you do have 3 equally spaced points with the same color on a line then there is guaranteed a triangle with three equally colored corners.

    However the solution starts not with the insights but with the proof that is required to make use of the insights. So rather then immediately making sense as the student reads, it starts with a sub-proof of a seemingly irrelevant fact the relevance of which only becomes apparent at the end. It's easy to imagine that students would be discouraged by solutions like that because of the huge leap from the problem to the first step of the solution.

    ReplyDelete
  7. in such a structure if you do have 3 equally spaced points with the same color on a line then there is guaranteed a triangle with three equally colored corners

    Why would you consider this possibility though? What makes it stand out as more plausible than many other things?

    ReplyDelete
  8. in such a structure if you do have 3 equally spaced points with the same color on a line then there is guaranteed a triangle with three equally colored corners

    Why would you consider this possibility though? What makes it stand out as more plausible than many other things?


    I had that insight after examining some of the possible colorings of structures composed of similar triangles.

    unfortunately there are a lot of math problems that come down to recognizing and exploiting patterns in the structure of what you are dealing with. I don't know If there is a universal problem solving guide that will get you the answer to every problem . For me it, there's a lot of "this is interesting, let's explore it, and see if it gets me anywhere.", and the more problems I do the better I get at recognizing and useful patterns sooner.

    ReplyDelete