Tuesday, September 9, 2008

Monochromatic triangles in multi-colored planes

My earlier puzzle "A painted plane II" asked the following question:
Let's say I've painted each point on an infinite, continuous plane. Each point is either painted red or blue. Prove that there must exist three points of the same color which form the corners of an equilateral triangle.
I did not invent this puzzle. I took it from one of the many sources in my memory. However, the second question was my invention. This is one of those puzzles that just begs to be modified and generalized, so it was just a matter of finding a variation that was still reasonably challenging.

The most obvious way to vary the problem is by adding more colors. Is it possible to prove it for three colors? Four? Must there always exist a monochromatic triangle (meaning an equilateral triangle whose corners are all the same color), no matter how many colors we have?

I've long wondered about this variation, but I've found it too difficult. It is tempting to give up. After all, the mathematical ocean is a large place, and even trained professionals cannot do more than find a few pretty shells on the shore. But I did find a solution! It turns out that you can always find a monochromatic triangle, as long as there are a finite number of colors. The proof follows.

The key is to reduce the number of colors, one by one. Given n colors, we prove that there must exist a set of points which only use n-1 colors. Within that set, there is a subset which only uses n-2 colors. Another subset of that only uses n-3 colors. We keep going until finally we're left with a set of three points--an equilateral triangle--which must use exactly one color. That's the monochromatic triangle we were looking for.

To see how we might reduce the number of colors, let's first try reducing the number of colors from 2 to 1.
All we need to do is find three points (in this case, red, but they could be blue too) all in a row such that they are evenly spaced. If we assume there are no monochromatic triangles, we can deduce that the upper three points are not red, and therefore blue. Those three blue points form a monochromatic triangle, which contradicts our original assumption.

Let's generalize a bit more, reducing from n colors to n-1 colors.
All we need to do is find X number of points, all of the same color, all in a row, and all evenly spaced. Here, we found a row of blue points, but we could have used any of the n colors. Here, X is 7, but it could have been any number. Assuming there are no monochromatic triangles, there are a bunch of points (shown in black) that cannot be blue. In other words, there exists triangle-shaped set of points which is made up of no more than n-1 colors. Hopefully we have enough space to further reduce the number of colors to n-2, then n-3, and so on until we have only one color left. This last color will form a monochromatic triangle.

But what if we don't have enough space to reduce down to one color? We simply choose X to be larger!

This proof assumes that we can find X evenly spaced points in a row and of the same color. It assumes that this is true, no matter how large X is. How do we know this is the case?

Lucky for us, mathematicians have already proven that this is the case. It is called van der Waerden's Theorem. Van der Waerden's Theorem states that for any natural numbers r and k, there exists a number n(r,k) for which the following is true: If we paint each of the natural numbers from 1 to n(r,k), using no more than r different colors, then there must exist a monochromatic arithmetic sequence of length k. That's exactly what we need! (For an incomplete proof of the theorem, see Wikipedia.)

If we have two colors, we only have to look at n(2,3) points in a row, and we're guaranteed to find a row of three evenly spaced points all of the same color. If we have two colors, we need to find a monochromatic row that is longer than n(2,3) so that we're guaranteed to have enough room to reduce down to a single color. To find a monochromatic row of n(2,3)+1 points, we need to look at a row of n(3,n(2,3)+1) to be guaranteed to find one. If we have four colors, we need to look at a row of length n(4,n(3,n(2,3)+1)+1).

The caution is that though van der Waerdan's theorem tells us that n(r,k) exists, it doesn't tell us what precisely n(r,k) is. Mathematicians only have an upper bound for n(r,k). The best current upper bound was found by Timothy Gowers.*

[Here, V(r,k) just means the same as n(r,k)]

The actual value of n(2,3) is known to be 9, but the formula above gives us a number so large that I don't even have the tools to calculate it. I don't know how much n(3,n(2,3)+1) is, but it's probably extremely large. But luckily we're on an infinite continuous plane, so we can have as many points in as small a space as we like.

Did I forget something? Oh, yeah: QED

*see "A new proof of Szemer├ędi's theorem"


Yoo said...

Now we know that there's always a monochromatic triangle given a finite number of colors. It should also be obvious that there is a way to color a plane so that there's no such triangle given an uncountably infinite number of colors (actually finding such a coloring might be a "bit" harder).

I wonder what the case is if there is "only" a countably infinite number of colors?

miller said...

If you have an uncountable number of colors, you simply need to give each point its own color.

If you have a countably infinite number of colors, I'm not sure what would happen. To prove or disprove that, I suspect you might need to use an entirely different method.