Prove or disprove:
For all functions $f:\Bbb Z^+ \to \{0,1\}$ , the following is true: There exists positive integers n and d such that: $f(n)=f(n+d)=f(n+2d)=f(n+3d)$
Prove or disprove:
For all functions $f:\Bbb Z^+ \to \{0,1\}$ , the following is true: There exists positive integers n and d such that: $f(n)=f(n+d)=f(n+2d)=f(n+3d)$
The Szemerédi’s theorem applies here. It says that for all $0 < d < 1$, and $k$ positive integer, there exists $N$, such that every subset of $\{1, \dotsc, N \}$ with cardinal at least $dN$ contains an arithmetic progression with length $k$.
Take $d = 1/2$ and $k = 4$, and let $N = N(1/2, 4)$. Either $[1, N]\cap f^{-1}(1)$ as cardinal at least $N/2$, or $[1, N] \cap f^{-1}(0)$ has. So there is a arithmetic progression of length 4 in one of them. Qed.
Edit
It appears that this easy corollary of the Szemerédi’s theorem is in fact a special case (2 colors) of the easier van der Waerden's theorem (1927).