MathDB
Hales–Jewett theorem

Source: Iran PPCE 2004

January 9, 2009
geometry3D geometrycombinatorics proposedcombinatorics

Problem Statement

Let l,d,k l,d,k be natural numbers. We want to prove that for large numbers n n, for each k k-coloring of the n n-dimensional cube with side length l l, there is a d d-dimensional subspace that all of its vertices have the same color. Let H(l,d,k) H(l,d,k) be the least number such that for n≥H(l,d,k) n\geq H(l,d,k) the previus statement holds. a) Prove that: H(l,d \plus{} 1,k)\leq H(l,1,k) \plus{} H(l,d,k^l)^{H(l,1,k)} b) Prove that H(l \plus{} 1,1,k \plus{} 1)\leq H(l,1 \plus{} H(l \plus{} 1,1,k),k \plus{} 1) c) Prove the statement of problem. d) Prove Van der Waerden's Theorem.
Back to ProblemsView on AoPS