Show that it is possible to color the set of integers \[M=\{ 1, 2, 3, \cdots, 1987 \},\] using four colors, so that no arithmetic progression with $10$ terms has all its members the same color.
Problem
Source:
Tags: arithmetic sequence
hxy09
28.05.2009 17:18
We can replace $ 10$ by $ 7$,and consider $ M$ in base $ 7$(this was a well known problem,it must have been discussed somewhere but I just cannot find a link)
MGM97
16.04.2014 18:05
I want to solve this question by double counting. It is clear that you can color the set of integers {1,2,..., 1987} is 4^1987 . Let the quantity of arithmetic progressions with 10 terms be A. Now form a table which its rows are all that progressions and its columns are all the conditions of coloring that set. Now write 1 the intersection of the row I and column j if and only if the coloring condition j has just one color for the progression I. Now the sum of the numbers of each row is 4×(4^1977) . Now the sum of table(S) is A×(4^1978). Now the average of sum of the numbers of the table is S÷(4^1978)=(4^-9)×A Now if we have average < 1 then A< 4^9 and now done.