4. How many numbers at most can be chosen from the set $M=\{1,2, \ldots, 2018\}$ such that the difference of any two chosen numbers is not equal to a prime number?

The regional round of category B takes place

## on Tuesday, April 10, 2018

so that it starts no later than 10:00 AM and the contestants have 4 hours of pure time to solve the problems. Allowed aids are writing and drawing supplies and school MF tables. Calculators, laptops, and any other electronic aids are not allowed. Each problem can earn the contestant 6 points; the logical correctness and completeness of the written solution are also evaluated. The point threshold (higher than 7 points) for determining successful solvers will be centrally set after evaluating the statistics of results from all regions. This information will be communicated to the students before the competition begins.
4. Selecting 505 numbers $1,5,9,13,17, \ldots, 2017 \in \mathrm{M}$, which give a remainder of 1 when divided by four, clearly has the required property, because the difference between any two selected numbers is a multiple of four, thus a composite number. (Since 4 is the smallest composite number, it is not possible to select a larger number of numbers in a similar regular manner.)

We will show that it is not possible to select more numbers with the required property from the given set, regardless of the method used. To do this, we first verify the key statement that from any sequence of eight consecutive numbers, at most two numbers can be selected.

First, we prove that if we select some number $n$, from the next seven numbers $n+1, n+2, \ldots, n+7$ at most one can be selected. Indeed, we cannot then select any of the numbers $n+2, n+3, n+5, n+7$. And from the remaining trio $n+1, n+4, n+6$, only one number can be selected, because their differences are the prime numbers 2, 3, and 5. This proves the statement about the seven numbers that follow any selected number $n$. From this, it is clear that no sequence of eight consecutive numbers can contain more than two selected numbers, as we promised to verify.

The set $\mathrm{M}$ can be divided into the set $\{1,2, \ldots, 10\}$ and 251 subsequent eights. From the set $\{1,2, \ldots, 10\}$, at most three suitable numbers can be selected. If we were to select four suitable numbers from the first ten

$$
\{1,2, \ldots, 10\}=\{1,2\} \cup\{3,4, \ldots, 10\}=\{1,2, \ldots, 8\} \cup\{9,10\}
$$

according to the proven property of each sequence of eight consecutive numbers, we would have to select both numbers 1 and 2, as well as both numbers 9 and 10, but $9-2$ is a prime number. From the set $\mathrm{M}$, then, at most $2 \cdot 251+3=505$ numbers can be selected.

For a complete solution, award 6 points. 1 point for the idea that from a sequence of eight consecutive numbers, at most two can be selected, and 1 point for a correct proof of this idea. 1 point for correctly dividing the numbers into disjoint eights and "remainder". 1 point for correctly deriving that from such a division, at most 505 numbers can be selected. 1 point for constructing the required set itself, and 1 point for justifying that the constructed set meets the requirements.

In the case of a partial solution, award 1 point for constructing an example of 505 numbers that meet the requirements, and an additional point for proving that no additional number can be added to it.