Results 1 to 2 of 2

Thread: Another Van der Waerden Problem

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    18

    Another Van der Waerden Problem

    Show that for n,k$\displaystyle \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 $\displaystyle k$.
    If $\displaystyle k=1$ then for every $\displaystyle n \ge 1$ it suffices to take $\displaystyle W^*(n,1)=n$ and the statement holds.

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

    Let the interval $\displaystyle \{1, 2,\ldots, W\left((n-1)W^*(n,k)+1,k+1\right)\}$ be $\displaystyle (k+1)$-coloured, it must contain a monochromatic arithmetic progression of length $\displaystyle (n-1)W^*(n,k)+1$, let's denote it $\displaystyle A=\{a, a+d, a+2d, \ldots, a+(n-1)W^*(n,k)d\}$ and let,WLOG, blue be its colour.
    If there's $\displaystyle j \in \{1,2,\ldots, W^*(n,k)\}$ such that $\displaystyle jd$ is blue, then $\displaystyle B=\{a, a+jd, a+2jd,\cdots, a+(n-1)jd\} \subseteq A$ is a blue arithmetic progression of length $\displaystyle n$ with blue common difference $\displaystyle jd$, and we're done.
    So suppose this is not the case, then $\displaystyle C=\{1d, 2d,\ldots, W^*(n,k)d\}$ is an arithmetic progression of length $\displaystyle W^*(n,k)$ coloured with $\displaystyle k$ colours. By the induction hypothesis, $\displaystyle k$-coloured interval $\displaystyle \{1, 2,\ldots, W^*(n,k)\}$ contains a monochromatic arithmetic progression $\displaystyle \{b, b+e,\ldots, b+(n-1)e\}$ with the common difference $\displaystyle e$ of the same colour. This means that $\displaystyle \{db, db+de,\ldots, db+(n-1)de\}\subseteq C$ is a monochromatic arithmetic progression of length $\displaystyle n$ with common difference $\displaystyle 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: Sep 8th 2009, 11:47 AM

Search Tags


/mathhelpforum @mathhelpforum