# Van der Waerden's theorem

Acolyte
Posers and Puzzles 21 Jan '03 14:43
1. Acolyte
21 Jan '03 14:431 edit
Suppose you have an (infinitely) long line of tiles, and you have to colour them each either red or blue. If there are enough tiles, will you always be able to find three tiles, equally spaced, that are all the same colour?

Once you've done that, how about more colours? How about trying to find four or more equally spaced tiles all the same colour?

Hint: for the second part, a general method will do. Don't try to spell it out tile by tile!
2. royalchicken
CHAOS GHOST!!!
21 Jan '03 17:22

Once you've done that, how about more colours? How about trying to find four or more equally spaced tiles all the same colour?

Isn't this just equivalent to saying that given sets S1, S2, S3...Sk, such that:

S1 U S2 U S3 U ... U Sk = N (the natural numbers),

There exists some j &lt;= k such that Sj contains an arithmetic sequence? Or did I miss something? Of course it still has to be proved...I have a couple free hours.
3. Acolyte
21 Jan '03 17:51
Originally posted by royalchicken
Isn't this just equivalent to saying that given sets S1, S2, S3...Sk, such that:

S1 U S2 U S3 U ... U Sk = N (the natural numbers),

There exists some j <= k such that Sj contains an arithmetic sequence? Or did I miss something? Of course it still has to be proved...I have a couple free hours.
Well... the sets are disjoint (though I suppose that's not important, come to think of it) and you're not looking for an infinite arithmetic progression, just one of some length x. I phrased it in non-mathematical terms as I don't usually like setting puzzles that look like part of a Maths exam. If you find the question too easy, consider this: say you only consider {1,2,...,N}. How big does N have to be to guarantee that this set contains the relevant progression, for various values of x and k?
4. royalchicken
CHAOS GHOST!!!
21 Jan '03 18:05
That was a quite clever way of phrasing it. I am working on proving it as we speak.
5. royalchicken
CHAOS GHOST!!!
24 Jan '03 20:57
Hmm. How to rephrase the question?

What about saying that given two positive integers, p,m, there must exist a constant q(p,m) such that for all n&gt;=q(p,m), if {1,2,3,...,n} ( S1 U S2 U Sm, then one S contains an arithmetic sequence of length p? This can fairly easily be proved by induction on p and m.