Largest Progression-free Subsets
Find the cardinality (denoted by Ak(m)) of the largest subset of {1, 2, ..., m} which contains no progression of k distinct terms. The elements of the forbidden progressions are not required to be consecutive.
For example, A4(10) = 8, because {1, 2, 3, 5, 6, 8, 9, 10} has no arithmetic progressions of length 4, while all 9-element subsets of {1, 2, ..., 10} have one. Paul Erdős set a $1000 prize for a question related to this number, collected by Endre Szemerédi for what has become known as Szemerédi's theorem.
Read more about this topic: Problems Involving Arithmetic Progressions
Famous quotes containing the word largest:
“We saw many straggling white pines, commonly unsound trees, which had therefore been skipped by the choppers; these were the largest trees we saw; and we occasionally passed a small wood in which this was the prevailing tree; but I did not notice nearly so many of these trees as I can see in a single walk in Concord.”
—Henry David Thoreau (1817–1862)