9. (40 points) What is the maximum number of numbers that can be chosen among the natural numbers from 1 to 3000 such that the difference between any two of them is different from 1, 4, and 5?
Answer: 1000.

Solution. Let's provide an example. We can choose all numbers divisible by 3. Then the difference between any two numbers will also be divisible by 3, while the numbers 1, 4, and 5 are not divisible by 3.

The estimate is based on the consideration that among 6 consecutive numbers, 3 numbers cannot be chosen. Let's prove this statement. Take any chosen number and the five numbers following it. Then the second, fifth, and sixth numbers are definitely not chosen. The third and fourth numbers remain, but they cannot both be chosen at the same time. It is even more impossible to choose 3 numbers among five or fewer consecutive numbers.