tag:blogger.com,1999:blog-3722233.post2615276144271159182..comments2023-03-20T21:49:52.361-05:00Comments on Computational Complexity: An ill define question inspired by that HS questionLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-70633481939536865052007-12-14T13:47:00.000-06:002007-12-14T13:47:00.000-06:00in such a structure if you do have 3 equally space...<I>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<BR/><BR/>Why would you consider this possibility though? What makes it stand out as more plausible than many other things?</I><BR/><BR/>I had that insight after examining some of the possible colorings of structures composed of similar triangles. <BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16810694255344403292007-12-14T09:48:00.000-06:002007-12-14T09:48:00.000-06:00in such a structure if you do have 3 equally space...<I>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</I><BR/><BR/>Why would you consider this possibility though? What makes it stand out as more plausible than many other things?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73496965791068447832007-12-14T01:31:00.000-06:002007-12-14T01:31:00.000-06:00I don't mean any offense to the person who wrote u...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.<BR/><BR/>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. <BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10811994371937979562007-12-11T23:34:00.000-06:002007-12-11T23:34:00.000-06:00This xkcd comic seems very relevant to this post:...<A HREF="http://xkcd.com/356" REL="nofollow">This</A> xkcd comic seems very relevant to this post:Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54621260726619886112007-12-11T11:34:00.000-06:002007-12-11T11:34:00.000-06:00My answer to Bill's question would be 'probably no...My answer to Bill's question would be 'probably not', for the reason that VDWR implies VDW in the following, relatively simple, way.<BR/><BR/>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}.<BR/><BR/>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}.<BR/><BR/>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}.<BR/>Thus any c-coloring to R' leads to a k-AP.<BR/><BR/><BR/>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. <BR/><BR/>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).<BR/><BR/>Clearing denominators in Q', we obtain a finite subset N' of N, for which all c-colorings must induce a monochromatic k-AP.Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45428257106222623252007-12-10T16:49:00.000-06:002007-12-10T16:49:00.000-06:00The simple argument given in the post for (3,2) ex...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48065004862083100882007-12-10T15:42:00.000-06:002007-12-10T15:42:00.000-06:00Hmm...I'm thinking about an induction proof (on k)...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".)<BR/><BR/>Silly question: Does the original argument for (3,2) extend to (3,c)? If not, then "standard" Ramsey-type arguments seem unavoidable...Johnhttps://www.blogger.com/profile/18079824074256670713noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22678360131177636692007-12-10T13:54:00.000-06:002007-12-10T13:54:00.000-06:00The qoriginal question seems ill-defined to me.Wou...The qoriginal question seems ill-defined to me.<BR/><BR/>Wouldn't it depend on the particular distribution of colored points on the plane?Dr. Thomashttps://www.blogger.com/profile/07479248934680221162noreply@blogger.com