If we color $5$ consecutive integers in $2$ colors, then there must be a 3-term arithmetic progression with first two elements of the same color.

Indeed, if the first two elements are of the same color then we are done, and likewise we must have that the first four elements alternate colors, and then we have no color available for the fifth element. $4$ integers do not suffice, by the sequence of colors RGRG. We can ask:

How many consecutive numbers are needed to ensure that any $m$-coloring contains a 3-term arithmetic progression whose first two elements are monochromatic?

For $m=1$ it is $3$.

For $m=3$, by trial and error, I think $15$ elements do it. $14$ do not suffice, by this sequence of length 14 (which cannot be extended): RGRG BRBR GBGB RR.

For general $m$ we can no more just determine the next value based on the previous ones.

  • $\begingroup$ I don't understand your example 3-coloring 14 consecutive integers. Don't the first, third, and fifth elements form a 3-term arithmetic progression whose first two elements are red? $\endgroup$ – bof Mar 18 '17 at 23:43

The answer is $2m+1$.

Suppose we $m$-color $2m+1$ consecutive integers. Among the first $m+1$ of them, two must have the same color, by the pigeonhole principle. If we make those two the starting two terms of our arithmetic progression, they could be as far as $m$ apart, so we need $m$ integers more to ensure that a third term exists.

If we only have $2m$ integers, we could assign them the colors $$1, 2, \dots, m-1, m, 1, 2, \dots, m-1, m$$ and avoid having any $3$-term progression whose first two terms have the same color. This proves that $2m+1$ is the best we can do.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.