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