Van der Waerden's theorem states that for any given positive integers *C* and *N*, there is some number *V*(*C*, *N*) such that if
the integers {1, 2, ..., *V*(*C*, *N*)} are colored, each with one of *C*
different colors, then there are at least *N* integers in arithmetic progression all of the same color.

For example, when *C*=2, you have two colors of paint, say red and blue. *V*(2, 3) is bigger than 8, because you can color the integers from {1,...,8} like this:

1 2 3 4 5 6 7 8 B R R B B R R Band no three integers of the same color form an arithmetic progression. But you can't add a ninth integer to the end without creating such a progression. If you color the number 9 red, you get

1 2 3 4 5 6 7 8 9 B Rand if you color it blue you getRB BRR B \R

1 2 3 4 5 6 7 8 9Of course, this doesn't prove that there isBR R BBR R BB

It is an open problem to determine the values of *V*(*C*, *N*) for various *C* and *N*. The proof of the theorem provides only an
upper bound. For the case of *C*=2 and *N*=3, for example, van der Waerden's theorem says it is sufficient to color the integers
{1,...,325} with two colors to guarantee there will be a single-colored arithmetic progression of length 3. But in fact, the bound of 325 is very loose; the minimum required number of integers is only 9. Any coloring of the integers {1,...,9} will have three evenly spaced integers of one color.

For *C*=3 and *N*=3, the bound given by the theorem is 7(2·3^{7}+1)(2·3^{7·(2·37+1)}+1), or approximately 4.22·10^{14616}.
But actually, you don't need that many integers to guarantee a single-colored progression of length 3; you only need 27. (It is possible to color {1,...,26} with three colors so that there is no single-colored arithmetic progression of length 3; for example, RRYYRRYBYBBRBRRYRYYBRBBYBY.)

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

Divide {0,...,324} into the 65 blocks {0,...,4}, {5,...,9}, ... {320,...,324}.
Since each integer is colored either red or blue, each block is colored in
one of 32 different ways. By the Pigeonhole principle, there are two
blocks among the first 33 that are colored identically. That is,
there are two integers *b*_{1} and *b*_{2},
both in {0,...,32},
such that
*c*(*b*_{1}·5 + *k*) =
*c*(*b*_{2}·5 + *k*)
for all *k* in {0,...,4}.

Among the three integers
*b*_{1}·5 + 0,
*b*_{1}·5 + 1, and
*b*_{1}·5 + 2,
there must be at least two that are the same color.
(The pigeonhole principle again.) Call these
*b*_{1}·5 + *a*_{1} and
*b*_{1}·5 + *a*_{2},
where the *a*_{i} are in {0,1,2}
and *a*_{1} < *a*_{2}.
Suppose (without loss of generality) that these
two integers are both red. (If they are both blue,
just exchange 'red' and 'blue' in what follows.)

Let *a*_{3} = 2·*a*_{2} - *a*_{1}.
If *a*_{3} is red, then we have found our arithmetic progression:
*b*_{1}·5 + *a*_{i} are all red.

Otherwise, *b*_{1}·5 + *a*_{3} is blue.
Since *a*_{3} ≤ 4, *b*_{1}·5 + *a*_{3} is in the *b*_{1} block, and since the *b*_{2} block
is colored identically, *b*_{2}·5 + *a*_{3}
is also blue.

Now let *b*_{3} = 2·*b*_{2} - *b*_{1}.
*b*_{3} ≤ 64.
Consider the integer *b*_{3}·5 + *a*_{3},
which must be ≤ 324. What color is it?

If it is red, then
*b*_{1}·5 + *a*_{1},
*b*_{2}·5 + *a*_{2}, and
*b*_{3}·5 + *a*_{3}
form a red arithmetic progression.
But if it is blue, then
*b*_{1}·5 + *a*_{3},
*b*_{2}·5 + *a*_{3}, and
*b*_{3}·5 + *a*_{3}
form a blue arithmetic progression. Either way, we are done.

A similar argument can be advanced to show that
*V*(3, 3) ≤ 7(2·3^{7}+1)(2·3^{7·(2·37+1)}+1).
One begins by dividing the integers into
2·3^{7·(2·37+1)}+1 groups of
7(2·3^{7}+1) integers each; of
the first 3^{7·(2·37+1)}+1 groups,
two must be colored identically. Divide each of these two groups
into 2·3^{7}+1 subgroups of 7 integers each;
of the first 3^{7}+1 subgroups in each group, two of the
subgroups must be colored identically. Within each of these identical
subgroups, two of the first four integers must be the same color, say red;
this implies either a red progression or an element of a different color, say blue, in the same subgroup. Since we have two identically-colored subgroups, there is a third subgroup, still in the same group that contains an element which, if either red or blue, would complete a red or blue progression,
by a construction analogous to the one for *V*(2, 3). Suppose
that this element is yellow. Since there is a group that is colored identically, it must contain copies of the red, blue, and yellow elements we have identified; we can now find a pair of red elements, a pair of blue elements, and a pair of yellow elements that 'focus' on the same integer, so that whatever color it is, it must complete a progression.

It should be noted that the proof for *V*(2, 3) depends essentially on proving
that *V*(32, 2) ≤ 65. We divide the integers {0,...,324} into 65 'blocks',
each of which can be colored in 32 different ways, and then show that two
blocks must be the same color. Similarly, the proof for
*V*(3, 3) depends on proving that *V*(3^{7·(2·37+1)}, 2) ≤
2·3^{7·(2·37+1)}+1.
By a double induction on the number of colors and the length of the
progression, the theorem is proved in general.