MathDB
Van der Warden Theorem!

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

September 15, 2012
functionprobabilityarithmetic sequencecombinatorics proposedcombinatorics

Problem Statement

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