Results 1 to 2 of 2

Math Help - Another Van der Waerden Problem

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    18

    Another Van der Waerden Problem

    Show that for n,k \in \mathbb{N}, there exists W*=W*(n,k) such that if the interval {1, 2, ..., W*(n,k)} is k-colored, then there will be a monochromatic arithmetic progression of length n and the common difference of the arithmetic progression is of the same color.

    I know that the first condition is simply Van der Waerden's Theorem. But I don't see how to incorporate the second condition in order to prove existence. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2009
    Posts
    125
    Hi!

    let me try by induction on k.
    If k=1 then for every n \ge 1 it suffices to take W^*(n,1)=n and the statement holds.

    Suppose that the statement holds for k \ge 1, that is, for every n \ge 1 there exists some W^*(n,k) such that if the interval \{1, 2,\ldots, W^*(n,k)\} is k-coloured then there will be a monochromatic arithmetic progression of length n and the common difference of the arithmetic progression is of the same colour.
    We'll show that for k+1, for every n \ge 1 it will suffice to take W^*(n,k+1)=W\left((n-1)W^*(n,k)+1,k+1\right), where W denotes van der Waerden number.

    Let the interval \{1, 2,\ldots, W\left((n-1)W^*(n,k)+1,k+1\right)\} be (k+1)-coloured, it must contain a monochromatic arithmetic progression of length (n-1)W^*(n,k)+1, let's denote it A=\{a, a+d, a+2d, \ldots, a+(n-1)W^*(n,k)d\} and let,WLOG, blue be its colour.
    If there's j \in \{1,2,\ldots, W^*(n,k)\} such that jd is blue, then B=\{a, a+jd, a+2jd,\cdots, a+(n-1)jd\} \subseteq A is a blue arithmetic progression of length n with blue common difference jd, and we're done.
    So suppose this is not the case, then C=\{1d, 2d,\ldots, W^*(n,k)d\} is an arithmetic progression of length W^*(n,k) coloured with k colours. By the induction hypothesis, k-coloured interval \{1, 2,\ldots, W^*(n,k)\} contains a monochromatic arithmetic progression \{b, b+e,\ldots, b+(n-1)e\} with the common difference e of the same colour. This means that \{db, db+de,\ldots, db+(n-1)de\}\subseteq C is a monochromatic arithmetic progression of length n with common difference de of the same colour. The induction step is completed.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A proof using Van der Waerden's Theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 8th 2009, 12:47 PM

Search Tags


/mathhelpforum @mathhelpforum