To each element of the set S = {1, 2, 3.....1000}, a colour is assigned. Suppose that for any two elements a, b of S, if 15 divides a + b they are both assigned the same colour. What is the maximum possible number of distinct colours used

Answer

To solve the problem, we need to determine how many distinct colors can be assigned to the elements of the set \( S = \{1, 2, 3, \ldots, 1000\} \) under the condition that if \( 15 \) divides \( a + b \) for any two elements \( a \) and \( b \) in \( S \), then \( a \) and \( b \) must be assigned the same color.

### Step-by-Step Solution:

1. **Understanding the Condition**:
We need to analyze the condition \( 15 \mid (a + b) \). This means that the sum of any two elements \( a \) and \( b \) must be divisible by \( 15 \).

2. **Modulo 15**:
We can consider the elements of \( S \) modulo \( 15 \). The possible remainders when dividing by \( 15 \) are \( 0, 1, 2, \ldots, 14 \). Therefore, we can represent each element \( a \) in \( S \) by its remainder when divided by \( 15 \).

3. **Pairs of Remainders**:
For two numbers \( a \) and \( b \) such that \( 15 \mid (a + b) \), we can express this condition in terms of their remainders:
\[ r_a + r_b \equiv 0 \mod 15 \]
This implies that \( r_b \equiv -r_a \mod 15 \).

4. **Finding Compatible Remainders**:
We can pair the remainders:
- \( (0, 0) \)
- \( (1, 14) \)
- \( (2, 13) \)
- \( (3, 12) \)
- \( (4, 11) \)
- \( (5, 10) \)
- \( (6, 9) \)
- \( (7, 8) \)

Each pair consists of two remainders that sum to \( 15 \).

5. **Counting Distinct Colors**:
From the pairs listed above, we can see that:
- The remainder \( 0 \) can only pair with itself.
- Each of the other pairs contributes one distinct color.

Therefore, we have:
- One color for the pair \( (0, 0) \)
- One color for each of the pairs \( (1, 14) \), \( (2, 13) \), \( (3, 12) \), \( (4, 11) \), \( (5, 10) \), \( (6, 9) \), and \( (7, 8) \).

This gives us a total of \( 1 + 7 = 8 \) distinct colors.

### Conclusion:
The maximum possible number of distinct colors that can be assigned to the elements of the set \( S \) is \( 8 \).