What is the maximum possible number of distinct colors used? To each element of set $S=\{1,2,..,1000\}$ a color is assigned.Suppose that for any two elements $a,b$ of $S$ , if $15$ divides $a+b$ then they are assigned both same color.What is the maximum possible number of distinct colors used?
My attempt
All the multiples of 15 will have same color.Also we see that ordered pair $(a,b)=\{(1,14),(2,13)..(7,8)\}$ can have distinct colors. Hence maximum possible color count is $7+1=8$.
Is this answer correct? Or I am missing something?  
 A: As you noticed, the key is the residue classes modulo $15$. Each member of $S$ is congruent to exactly one of the numbers $0,1,\ldots,14$ modulo $15$. Here’s one way to write it up carefully.
For each $n\in S$ let $a_n=n\bmod{15}$; then $n\equiv a_n\pmod{15}$, and $a_n\in\{0,\ldots,14\}$. Then if $m,n\in S$, $m$ and $n$ are the same color if and only if $15\mid m+n$, i.e., iff $m+n\equiv0\pmod{15}$. But $m+n\equiv a_m+a_n\pmod{15}$, so $m$ and $n$ are the same color iff $a_m+a_n\equiv0\pmod{15}$. This occurs precisely when either $a_m=a_n=0$, or $\{a_m,a_n\}$ is one of the seven pairs $\{1,14\}$, $\{2,13\}$, $\{3,12\}$, $\{4,11\}$, $\{5,10\}$, $\{6,9\}$, and $\{7,8\}$. Thus, we can have at most $1+7=8$ colors: 


*

*all multiples of $15$ in $S$ (i.e., those $n$ with $a_n=0$) get one color; and  

*for $1\le k\le 7$, all members of $S$ congruent to $k$ modulo $15$ must get the same color as the members of $S$ that are congruent to $15-k$ modulo $15$. 


The $7$ colors in the second point can be different from one another and from the color used for the multiples of $15$, but that’s it, so we get at most $8$ colors.
There actually is one subtlety that I slid over. How do we know that all of the members of $S$ congruent to $2$, say, modulo $15$ get the same color as one another? Let $m,n\in S$ both be congruent to $2$ modulo $15$. Then both $m$ and $n$ must get the same color as $15-2=13$, so they must get the same color as each other. If you want to be very careful (or have someone grading your answer who insists on very careful, thorough explanations), you should include an explanation along these lines for the non-zero residue classes.
