# Thread: Another Van der Waerden Problem

1. ## 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.

2. 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.