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