Can you color the integers red and blue such that
there are no monochromatic arithmetic progressions (AP's)
extending infintely in both directions? Sure  just color
zero and all the positive integers red, and all the
negative integers blue.
Now try coloring just the positive integers with red and
blue such that there are no onesided infinite monochromatic
AP's. This is almost as easy  color
the first one red, the next two blue, the next three red,
the next four blue, and so on. If an AP
has step size d, then eventually it will hit a blue integer
and eventually hit a red integer, as soon as the
monochromatic blocks reach size d.
What about finite AP's? Given any
coloring of the positive integers,
can you find a monochromatic finite AP
of arbitrarily long length?
Surprisingly, yes!
The Van der Waerden theorem says that given any
number of colors and specifications for lengths,
there's an M large enough so that no matter
how you color the first M integers with those colors,
you can always find a monochromatic AP of at least
one of the given lengths and colors!
Presentation Suggestions:
You may ask students to think about
the first two questions
(perhaps a bonus problem on a HW)
before doing this Fun Fact.
The Math Behind the Fact:
The Van der Waerden theorem follows from the diagonal Van
der Waerden theorem in which all the
specified lengths are equal. This in
turn can be proven with a very clever
application of the pigeonhole principle
and double induction. The key observation is
that one may treat a block of m integers
colored with k colors as a single integer colored
with k^{m} colors.
The Van der Waerden theorem also follows as a consequence of
the much more difficult HalesJewett Theorem, which involves
monochromatic combinatorial lines in colored
highdimensional lattices.
All of these results are part of a branch of mathematics
called Ramsey Theory.
How to Cite this Page:
Su, Francis E., et al. "Van der Waerden Theorem."
Math Fun Facts.
<http://www.math.hmc.edu/funfacts>.
