# Thread: Another Van der Waerden Problem

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

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