Question

To each element of the set S = \left\\{ {1,{\text{ }}2,{\text{ }} \ldots .,{\text{ }}1000} \right\\} a colour is assigned. Suppose that for any two elements a, b of S, if $15$ divides $\left( {a + b} \right)$ then they are both assigned the same colour. What is the maximum possible number of distinct colours used?

Answer 1

As given in the question, the sum of a and b when divided by $15$ will assign the same colour, so all the multiples of $15$ will have the same colour. Also, see that it will form the ordered pair which keeps on repeating and forms a sequence.

Complete step-by-step answer:
According to the question, if a and b are both assigned the same colour, $\left( {a + b} \right)$ is divisible by $15$.
Therefore, we need to make combinations of a and b such that $\left( {a + b} \right) = 15$ . This can be achieved as shown below:
$1 + 14 = 15,{\text{ }}2 + 13 = 15,{\text{ }}3 + 12 = 15,{\text{ }}4 + 11 = 15,{\text{ }}5 + 10 = 15,{\text{ }}6 + 9 = 15,{\text{ }}7 + 8 = 15$
So, we infer from the above combinations that all of them give us $\left( {a + b} \right) = 15$ .
Therefore, these numbers contribute to $7$ distinct colours. Also, number $15$ will have a different colour.
Now, in order to generalise the above combinations for all the numbers we take $\left( {a + b} \right) = 15n$ , and it can be achieved as shown below-
$1 + 14:{\text{ }}\left( {1 + 15n{\text{ , }}14 + 15n} \right)$
$2 + 13:{\text{ }}\left( {2 + 15n{\text{ , }}13 + 15n} \right)$
$3 + 12:{\text{ }}\left( {3 + 15n{\text{ , }}12 + 15n} \right)$
$4 + 11:{\text{ }}\left( {4 + 15n{\text{ , }}11 + 15n} \right)$
$5 + 10:{\text{ }}\left( {5 + 15n{\text{ , }}10 + 15n} \right)$
$6 + 9:{\text{ }}\left( {6 + 15n{\text{ , }}9 + 15n} \right)$
$7 + 8:{\text{ }}\left( {7 + 15n{\text{ , }}8 + 15n} \right)$
$15 + 30:{\text{ }}\left( {15n + 15n} \right)$
Thus, \left( {a,{\text{ }}b} \right) = \left\\{ {\left( {1,{\text{ }}14} \right),\left( {2,{\text{ }}13} \right),....,\left( {7,{\text{ }}8} \right),(15,30)} \right\\} can have maximum $8$ possible distinct colours as seen.

Hence, the maximum possible numbers of distinct colours used is $8$.

Note: Write down all the combinations on paper so that you do not skip any pair. The number of elements in S does not matter for problems of this type as long as it exceeds the number that must divide $\left( {a + b} \right)$ .