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:
“...I believed passionately that Communists were a race of horned men who divided their time equally between the burning of Nancy Drew books and the devising of a plan of nuclear attack that would land the largest and most lethal bomb squarely upon the third-grade class of Thomas Jefferson School in Morristown, New Jersey.”
—Fran Lebowitz (b. 1950)