Van Der Waerdens Theorem

Named for Dutch mathematician B. L. van der Waerden.

Let numbers C and N be given. There is some number V(C, N) such that if you take V(C, N) evenly-spaced fence posts, and paint each post in one of C different colors, then there are at least N evenly-spaced posts of the same color.

For example, when C=2, you have two colors of paint. V(2, 3) is bigger than 8, because you can color 8 posts like this:

B R R B B R R B 

and no three posts of the same color are evenly spaced. But you can't add a ninth post to the end without having three evenly-spaced posts of the same color. If you add a red post, you get

B R R B B R R B R

and if you add a blue post you get

B R R B B R R B B

There might, of course, be some way of painting the 9 posts so that there aren't three evenly-spaced posts of the same color.

Now, you might wonder what the values of V(C, N) are for various C and N. And in fact the proof of the theorem provides an upper bound. For the case of C=2 and N=3, for example, the theorem says that if you paint 325 fence posts red and blue, there will be three evenly-spaced red posts or three evenly-spaced blue posts. But actually, you don't need 325 posts; you only need 9. Any coloring of the 9 posts will have three evenly spaced posts of one color.

For C=3 and N=3, the theorem says that if you paint 7*(2*3^7+1)*(2*3^(2*3^7+1)+1) posts red, green, or blue, there must be three evenly-spaced posts of the same color. But actually, you don't need 1.56e1012 posts; you only need 27. (It is possible to paint 26 posts so that no three evenly-spaced posts are the same color.)

Anyone who can reduce the general lower bound to any 'reasonable' function can win a large cash prize.

-- MarkJasonDominus

---

CategoryMath