9.4. $N$ different natural numbers, not exceeding 1000, are written in a circle such that the sum of any two of them, standing one apart, is divisible by 3. Find the maximum possible value of $N$.

#
# Answer: 664.

Solution. Consider the remainders of the numbers when divided by 3. Divisibility by 3 means that in each pair of numbers standing one apart, either both numbers are divisible by 3, or one has a remainder of 1 and the other has a remainder of 2 when divided by 3. Among the numbers from 1 to 1000, 333 are divisible by 3, 334 give a remainder of 1, and 333 give a remainder of 2.

1) Suppose \( \mathrm{N} \) is odd. Then the remainders 1 and 2 cannot alternate throughout the circle, so all numbers in the circle will be divisible by 3, and there will be no more than 333 of them.
2) Suppose \( \mathrm{N} \) is even. The numbers are divided into two cycles of equal length \( \mathrm{N}/2 \): those in even positions and those in odd positions. In each of them, either all numbers are divisible by 3, or they alternate with remainders of 1 and 2.

A cycle of numbers divisible by 3 has a length of no more than 333. A cycle with alternating remainders has an even length, not exceeding 666.

If there are numbers divisible by 3 among the listed ones, then there is a cycle of such numbers with a length of no more than 333. The second cycle would then consist of no more than 333 even numbers with remainders of 1 and 2, i.e., no more than 332 numbers. Then the total number of numbers would be no more than 664. This number is achievable: one cycle contains numbers divisible by 3 from 3 to 996, and the second: all numbers from 1 to 498 that are not divisible by 3.

If there are no numbers divisible by 3, then the lengths of the cycles are equal and even, so the total number of numbers written should be no more than 667 and divisible by 4, i.e., no more than 664.

Criteria. Consider the case 1) \( \mathrm{N} \) is odd: 1 point. Consider the case 2) \( \mathrm{N} \) is even - the idea of two cycles: 1 point, estimating the length of each cycle: 1 and 2 points respectively. Constructing an example: 2 points.