## Friday, December 07, 2007

I was assigned to grade the following problem from the Maryland Math Olympiad from 2007 (for High School Students):
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.
I think I was assigned to grade it since it looks like the kind of problem I would make up, even though I didn't. It was problem 5 (out of 5) and hence it was what we thought was the hardest problem. About 100 people tried it, and less than 5 got it right, and less than 10 got partial credit (and they didn't get much).

All the vertices are red because I can make them whatever color I want. I can also write at a 30 degree angle to the bottom of this paper if thats what I feel like doing at the moment. Just like 2+2=5 if thats what my math teacher says. Math is pretty subjective anyway. (NOTE- this was written at a 30 degree angle.)

I like to think that we live in a world where points are not judged by their color, but by the content of their character. Color should be irrelevant in the the plane. To prove that there exists a group of points where only one color is acceptable is a reprehensible act of bigotry and discrimination.
Were they serious? Hard to say, but I would guess the first one might have been but the second one was not.

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

2. More formally:
For EVERY triangle ABC,
for EVERY 2-coloring of the
plane, there exists a triangle
DEF similar to ABC such that the three vertices
of DEF are all the same
color.

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

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

5. which was comment 2.
We need to show that
FOR EVERY 2-COLORING
OF THE PLANE
blah blah happens.

You don't get to pick
the 2-coloring.

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

I haven't figured out why CDE is similar though, and maybe it's even wrong.

7. Anon 6: you get only 1 triangle in this way if ABC is equilateral.

8. if ABC is an equilateral triangle C,D and E are the same point. CDE is a similar triangle, (not in general position though.)

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

10. i don't get your point, Bram. The heights of the similar triangles are arbitrary.

11. As DaveMB suggests, start by proving this:

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.

12. And then a typical high school response would proceed by using Roth's theorem on length-3 arithmetic progressions to prove this lemma :)

13. To address not the problem but the comments, I think both were not serious (though I agree that the first sounds slightly more 'sincere'.

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.

I don't think you should fear any turn to post-modern mathematics, just that those tropes are more widespread as pseudo-intellectual filler.

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

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?

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

Now in this triangulated triangle ABC one can prove that all similar triangles can not be same color avoiding.

16. 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?

17. Bram: Yes, the problem of a monochromatic congruent triangle is much harder. In fact, it is false!

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.

18. Andy, oh yeah, I almost had that construction when I posted earlier, approaching it 'the hard way'. Funny I didn't realize the result.

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

Bill, did all of the students who go the correct answer use the same approach, or was there a variety of methods.

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

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

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.

Similarly if you have 3 equally distant intersections of the same color, you will have a triagle with three equally colored corners.

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.

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.

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.

21. I can prove the opposite.

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.

22. 23. Side-length = zero..?