tag:blogger.com,1999:blog-3722233.post7187732429106737591..comments2024-05-23T03:24:52.112-05:00Comments on Computational Complexity: Funny Answers on a Math Olympiad (MD)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger23125tag:blogger.com,1999:blog-3722233.post-88734821781089997892009-11-09T23:16:56.299-06:002009-11-09T23:16:56.299-06:00Side-length = zero..?Side-length = zero..?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61088281397393541812007-12-25T05:11:00.000-06:002007-12-25T05:11:00.000-06:00*then*thenAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55007132063560060482007-12-25T05:10:00.000-06:002007-12-25T05:10:00.000-06:00I can prove the opposite.If only A, B and C points...I can prove the opposite.<BR/><BR/>If only A, B and C points are red and ALL OTHER points are green, than there is NO other triangle (which is not the ABC itself) with points of the same color.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16623235203185084302007-12-14T00:58:00.000-06:002007-12-14T00:58:00.000-06:00You can create a grid by taking lines parallel to ...You can create a grid by taking lines parallel to each at the distanced apart from each other with the height of the triangle if that were the original line were the base. All he triangles that are part of the grid are similar to the original triangle.<BR/><BR/>if you have any 3 consecutive intersections on one of the lines of the grid, let's call them X, Y and Z that are the same color. Then consider the two intersections on the next line over, let's call them V and W, and the one intersection on the second line over, let's call it U, such that you have the 5 triangles, XVY, VYW, YWZ, VUW, and XUZ. One of these triangles will have three corners with the same color, because if any of U,V, or W has the same color as X,Y, and Z then there is triangle, and if they all don't then they forma triangle themselves.<BR/><BR/>Similarly if you have 3 equally distant intersections of the same color, you will have a triagle with three equally colored corners.<BR/><BR/>So if you have a sequence of consecutive intersections that has either three equally spaced same colored intersections then you will have a single colored triangle.<BR/><BR/>It is not possible to have more then 8 conscutive intersections without having 3 equally spaced intersections of the same color. This can be shown by enumerating 31 of the 1020 3-digit through 9-digit binary stings.<BR/><BR/>sorry if this not an optimally clear explanation, a diagram would help. And if anyone wants and I remember to check I will post those 31 numbers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88421248754546999882007-12-09T22:09:00.000-06:002007-12-09T22:09:00.000-06:00Apply the Baire Category Theorem to conclude that ...Apply the Baire Category Theorem to conclude that at least one of the color regions is dense in an open subset of the plane. Since every open subset contains a similar copy of every triangle, use an approximation argument to show that every dense subset contains an appropriate triple of vertices.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82635651370938374422007-12-09T21:18:00.000-06:002007-12-09T21:18:00.000-06:00Andy, oh yeah, I almost had that construction when...Andy, oh yeah, I almost had that construction when I posted earlier, approaching it 'the hard way'. Funny I didn't realize the result.<BR/><BR/>That approach does yield an alternative way of proving the problem though. We can use broewer's theorem to show that there must be a continuous line of just one color of some length. In order for the problem statement to be false then every triangle similar to DEF with two points on that line must have the third point be the other color. That results in a solid region of the opposite color, therefore that region must contain a similar triangle with all three vertices the same color. QED. (Yeah, I know, I skipped the case where the path is something like a hilbert curve).<BR/><BR/>Bill, did all of the students who go the correct answer use the same approach, or was there a variety of methods.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43833378843775300132007-12-09T18:53:00.000-06:002007-12-09T18:53:00.000-06:00Bram: Yes, the problem of a monochromatic congruen...Bram: Yes, the problem of a monochromatic congruent triangle is much harder. In fact, it is false!<BR/><BR/>Color the plane so that (x, y) is red if the floor of x is even, and green otherwise. Then there is no equilateral triangle DEF of height 1 with monochromatic vertices.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10608993721050919792007-12-09T10:52:00.000-06:002007-12-09T10:52:00.000-06:00Isn't this a bit of a trick question intended to g...Isn't this a bit of a trick question intended to get you to think along two dimensions whereas the key insight comes from thinking along one dimension?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14989122617566119252007-12-09T08:28:00.000-06:002007-12-09T08:28:00.000-06:00Start with the fixed triangle ABC. Now Draw a line...Start with the fixed triangle ABC. Now Draw a line l1 parallel to BC within the triangle infinitely close to A. (First strip)(if BC already on this line then draw a line parallel to BC outside of the fixed triangle) Triangle ABC will have at least two vertices colored by the same color. Same will be the situation for triangle formed by A-l1. Now draw another line l2 infinitely close to l1 parallel to l1. Also inside this triangulate the strip formed by l1 and l2 to obtain 2 similar triangles and 1 inverted triangle. Repeat this process.<BR/><BR/>Now in this triangulated triangle ABC one can prove that all similar triangles can not be same color avoiding.<BR/><BR/>Whats the grading for this answer?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73802666620107540052007-12-09T01:32:00.000-06:002007-12-09T01:32:00.000-06:00Oh, I see, it's asking for triangles which are *si...Oh, I see, it's asking for triangles which are *similar*, I was looking for triangles which are *congruent*, which is a much more difficult problem.<BR/><BR/>Similar triangles is easy. Just make a skewed grid of triangle vertices and appropriately apply the Hales-Jewett theorem. Bill, would you give partial credit to someone who stated that the second half of the proof was finite and therefore could be verified by a straightforward but tedious pencil and paper calculation which was left as an exercise to the reader?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59653033247769495292007-12-08T22:46:00.000-06:002007-12-08T22:46:00.000-06:00To address not the problem but the comments, I thi...To address not the problem but the comments, I think both were not serious (though I agree that the first sounds slightly more 'sincere'.<BR/><BR/>They both sound like answers given on exams from students who want to put at least -something- down, just to be funny/entertaining for pity points.<BR/><BR/>I don't think you should fear any turn to post-modern mathematics, just that those tropes are more widespread as pseudo-intellectual filler.Mitchhttps://www.blogger.com/profile/06352106235527027461noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48634881947395673082007-12-08T22:02:00.000-06:002007-12-08T22:02:00.000-06:00And then a typical high school response would proc...And then a typical high school response would proceed by using Roth's theorem on length-3 arithmetic progressions to prove this lemma :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73093854978960560482007-12-08T21:18:00.000-06:002007-12-08T21:18:00.000-06:00As DaveMB suggests, start by proving this:There ex...As DaveMB suggests, start by proving this:<BR/><BR/>There exists points X,Y,Z where Y is the midpoint of the line segment XZ, and X, Y, and Z are all the same color.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4340091042042060372007-12-08T19:59:00.000-06:002007-12-08T19:59:00.000-06:00i don't get your point, Bram. The heights of the s...i don't get your point, Bram. The heights of the similar triangles are arbitrary.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15247687386720465092007-12-08T14:42:00.000-06:002007-12-08T14:42:00.000-06:00That's a very odd question. My first thought is to...That's a very odd question. My first thought is to try using broewer's theorem to make very long extended continuous paths of one color, then run two vertices along it and show that the third vertex must hit the same color somewhere, but that approach can be busted by construction. Make DEF an equilateral triangle, and color the plane such that all points with the same cartesian coordinate x value are the same color, and the coloration is such that any two points whose y value differs exactly by the height of the given triangle are different colors. I don't see how to demonstrate the problem even for that very specific case, and suspect that the key insight for the general problem exists in there.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78632132385588908702007-12-08T06:37:00.000-06:002007-12-08T06:37:00.000-06:00if ABC is an equilateral triangle C,D and E are th...if ABC is an equilateral triangle C,D and E are the same point. CDE is a similar triangle, (not in general position though.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10230540641403473772007-12-08T03:31:00.000-06:002007-12-08T03:31:00.000-06:00Anon 6: you get only 1 triangle in this way if ABC...Anon 6: you get only 1 triangle in this way if ABC is equilateral.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16838465817492219282007-12-07T19:23:00.000-06:002007-12-07T19:23:00.000-06:00Two Points say A and B of ABC obviously have the s...Two Points say A and B of ABC obviously have the same color. Now add the two distinct similar triangles ABD, ABE that share the side AB and have the angles in the same clockwise order such that D and E are on the same side of AB as C. Then ( i think) the triangle CDE is similar as well and it is easy to see that the vertices of one of the triangles all have same color.<BR/><BR/>I haven't figured out why CDE is similar though, and maybe it's even wrong.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53006622339649339862007-12-07T17:08:00.000-06:002007-12-07T17:08:00.000-06:00Bernd L: Re-read my commentwhich was comment 2.We ...Bernd L: Re-read my comment<BR/>which was comment 2.<BR/>We need to show that<BR/>FOR EVERY 2-COLORING<BR/>OF THE PLANE<BR/>blah blah happens.<BR/><BR/>You don't get to pick<BR/>the 2-coloring.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48860239184628007282007-12-07T16:59:00.000-06:002007-12-07T16:59:00.000-06:00I'm sure I'm not understanding the question either...I'm sure I'm not understanding the question either because it is trivial to pick two similar triangles, place them on the plane and color their corresponding edges with the same color (which I can freely do since their exists such a plane coloring).Unknownhttps://www.blogger.com/profile/16888729787755023147noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21873176012220711782007-12-07T15:25:00.000-06:002007-12-07T15:25:00.000-06:00Useful Lemma: If Y is the midpoint of the line seg...Useful Lemma: If Y is the midpoint of the line segment XZ, and X, Y, and Z are all the same color, then such a triangle DEF similar to ABC exists with D, E, and F all the same color.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55717849672070048422007-12-07T14:47:00.000-06:002007-12-07T14:47:00.000-06:00More formally:For EVERY triangle ABC,for EVERY 2-c...More formally:<BR/>For EVERY triangle ABC,<BR/>for EVERY 2-coloring of the<BR/>plane, there exists a triangle<BR/>DEF similar to ABC such that the three vertices<BR/>of DEF are all the same<BR/>color.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59665078205172866392007-12-07T14:42:00.000-06:002007-12-07T14:42:00.000-06:00I'm not sure I get the question ... what does it m...I'm not sure I get the question ... what does it mean, each point is either red or green? Does that mean that the color of each one is chosen randomly, independent of the others? And what plane are we talking about, and how are the points placed? I know this is not very relevant to the story, but I'm curious and want to know what the correct answer is.Anonymousnoreply@blogger.com