Problem

Source: Iran 3rd round 2012-Special Lesson exam-Part 2-P2

Tags: function, probability, arithmetic sequence, combinatorics proposed, combinatorics



Suppose $W(k,2)$ is the smallest number such that if $n\ge W(k,2)$, for each coloring of the set $\{1,2,...,n\}$ with two colors there exists a monochromatic arithmetic progression of length $k$. Prove that $W(k,2)=\Omega (2^{\frac{k}{2}})$.