## Task 4 - 300734

Someone wants to select as many different natural numbers from 1 to 1000 as possible according to the following rules:

The first number is to be chosen randomly from the numbers 1 to 6 by rolling a die and selecting the number shown on the die. The subsequent numbers are to be chosen such that the following applies:

When the selection of numbers is complete, any two of the overall selected numbers always have a sum that is divisible by 3.

Determine (depending on all possibilities of the first number) the maximum number of numbers that can be selected according to these rules!
1. If the first number was a 3 or a 6, then:

The additional numbers can be chosen such that they are also divisible by 3; because only then will any two of the selected numbers have a sum that is divisible by 3. Among the numbers from 1 to 1000, exactly the numbers \(1 \cdot 3 = 3, 2 \cdot 3 = 6, \ldots, 333 \cdot 3 = 999\) are divisible by 3. Therefore, in the case of the initial numbers 3, 6, the maximum number of selectable numbers is 333.

2. If the first number was one of the numbers 1, 4; 2, 5, then:

These numbers leave a remainder of 1 or 2 when divided by 3; that is, they are of the form \(3n + 1\) or \(3n + 2\) with a natural number \(n\). For the second number, there is then exactly the possibility of choosing a number of the form \(3m + 2\) or \(3m + 1\), because only in this case does the sum \(3(m + n) + 3\) become divisible by 3.

Any further number would violate this rule; it would be of one of the forms \(3k, 3k + 1\), \(3k + 2\), and then with \(h = n\) or with \(h = m\), the relevant sum

\(3h + 1 + 3k = 3(h + k) + 1, \quad 3h + 1 + 3k + 1 = 3(h + k) + 2, \quad 3h + 2 + 3k + 2 = 3(h + k + 1) + 1\)

would not be divisible by 3.

Therefore, in the case of the initial numbers 1, 4; 2, 5, the maximum number of selectable numbers is 2.