IMO 1987 SL 17

Origin: ROM

Problem

Prove that there exists a four-coloring of the set M = {1, 2, . . ., 1987} such that any arithmetic progression with 10 terms in the set M is not monochromatic. Alternative formulation. Let M = {1, 2, . . ., 1987}. Prove that there is a function f : M \to{1, 2, 3, 4} that is not constant on every set of 10 terms from M that form an arithmetic progression.

Solution

The number of 4-colorings of the set M is equal to 41987. Let A be the number of arithmetic progressions in M with 10 terms. The number of col- orings containing a monochromatic arithmetic progression with 10 terms is less than 4A \cdot 41977. So, if A < 49, then there exist 4-colorings with the required property.

Now we estimate the value of A. If the first term of a 10-term progression is k and the difference is d, then 1 \leqk \leq1978 and d \leq / 1987−k ; hence A = 1978  k=1 1987 −k

< 1986 + 1985 + \cdot \cdot \cdot + 9 = 1995 \cdot 1978 < 49.