1
$\begingroup$

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)$

  • 0
    I think it is true too. Moreover I think that that for all positive integers k there exists n and d such that f(n)=f(n+d)=f(n+$2$d)=f(n+$3$d)=......=f(n+kd)2012-05-04

1 Answers 1

2

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