TAOCP 2.3.4.3 Exercise 6
Assume for contradiction that no such number $N$ exists.
Exercise 6. [**] [M23] (Otto Schreier.) In a famous paper [Nieuw Archief voor Wiskunde (2) 15 (1927), 212-216], B. L. van der Waerden proved the following theorem:
If $k$ and $m$ are positive integers, and if we have $k$ sets $S_1,\ldots,S_k$ of positive integers with every positive integer included in at least one of these sets, then at least one of the sets $S_j$ contains an arithmetic progression of length $m$.
The latter statement means there exist integers $a$ and $\delta>0$ such that
$$ a+\delta,\ a+2\delta,\ \ldots,\ a+m\delta $$
are all in $S_j$. If possible, use this result and the infinity lemma to prove the following stronger statement:
If $k$ and $m$ are positive integers, there is a number $N$ such that if we have $k$ sets $S_1,\ldots,S_k$ of integers with every integer between 1 and $N$ included in at least one of these sets, then at least one of the sets $S_j$ contains an arithmetic progression of length $m$.
Verified: no
Solve time: 39s
Assume for contradiction that no such number $N$ exists. Then for every positive integer $n$ there exist $k$ sets $S_1^{(n)},\ldots,S_k^{(n)}$ of integers in ${1,\ldots,n}$, covering the whole interval, such that none of the sets contains an arithmetic progression of length $m$. Consider the collection $T$ of all finite sequences $(x_1,\ldots,x_r)$ of positive integers such that $x_1<\cdots<x_r$ and $(x_1,\ldots,x_r)\subseteq S_j^{(n)}$ for some $j$ and some $n\ge r$. This collection satisfies the hypotheses of the infinity lemma: any initial segment of a sequence in $T$ is again in $T$, each sequence has only finitely many possible extensions in $T$, and there is no infinite sequence of positive integers avoiding an arithmetic progression of length $m$ (by van der Waerden's theorem). Therefore $T$ must be finite. Let $N$ be the largest integer appearing in any sequence in $T$. Then for $n\ge N$, every cover of ${1,\ldots,n}$ by $k$ sets must contain an arithmetic progression of length $m$ in one of the sets. This completes the proof.
∎