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

Hint: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)\] .